New dynamics in geometric data structures
Joe Simons
We study geometric data structures for spatio-temporal data: geometric
objects which change over time. In particular, we design data
structures for fundamental geometric problems in the following four data
models:
-
In the retroactive model, we maintain a timeline for the historical
sequence of updates to the data structure, and every update has an
associated time stamp. Unlike the standard dynamic model, in which we
only allow query and update operations against the current state of the
data structure, in the retroactive model, we also allow operations to be
performed ``in the past''. We describe fully retroactive dynamic data
structures for approximate range reporting and approximate nearest
neighbor reporting.
-
In the windowed model, we take an event-based approach, where each
geometric object corresponds to an event that occurs at an instance in
time, and queries are performed with respect to an interval in the
timeline. We consider time-windowed queries for skylines in
$\mathbf{R}^d$, convex hulls in $\mathbf{R}^2$ and proximity based
queries in $\mathbf{R}^d$.
-
In the set-difference model, we maintain a dynamic set (or multiple
sets) of items such that two subsets can be efficiently compared. We
introduce the problem of performing set-difference range queries, where
answers to queries are set-theoretic symmetric differences between sets
of items in two geometric ranges. We describe a general framework for
answering such queries based on a novel use of data-streaming sketches
we call signed symmetric-difference sketches.
-
In the local-update model, we maintain a set of geometric objects such
that the speed of updates is parameterized by how dramatically the
update changes the object. When the updated object is similar to the old
object in size and location, we desire to surpass known lower bounds for
more general updates. We study planar point location in a collection of
disjoint fat regions, and investigate the complexity of local updates.
We design a linear size data structure that allows for insertions,
deletions, and queries in logarithmic time, and allows for local updates
in sub-logarithmic time on a pointer machine.