Database Reference
In-Depth Information
More recently, Guting et al. [27] introduce algorithms that provide
more ecient query processing eciency of CNN queries. The authors
assume the trajectories are indexed using a 3
d
R-tree and they develop
a
filter-and-refine
approach for processing queries which uses geometric
pruning techniques. In the filtering step, we traverse the R-tree, pruning
nodes from the candidate set based on the geometrical properties of the
bounding box. The refinement step performs a modified plane-sweep
algorithm over the candidate set of trajectories to test over what time
intervals, if any, the trajectory is the nearest-neighbor to the query.
The authors experimentally show that their method offers significantly
faster query processing time and fewer disk accesses as both the size of
the database and the query range increase as compared to other CNN
processing algorithms.
Trajcevski et al. [81] also develop a query processing algorithm and
index structure for the CNN query, however, they address this query
when trajectories are uncertain. An uncertain trajectory is modeled
as a cylinder in which the mobile object may have traveled anywhere
within the enclosed area (i.e. the object's true location is assumed to
be uniformly distributed within the cylinder). Further details about the
uncertainty model for trajectories and how it is used in general query
processing is provided in [80, 82]. The authors first extend the earlier
work by allowing queries over pairs of objects in the database instead of
known regions of interest by specifying a query as an uncertain trajec-
tory [82]. The authors then show that they can order objects by their
probability of being the nearest neighbor to the query (at any given
time) by ranking objects according to their expected distances to the
query location for any symmetric distribution function. This provides
an ordering in which to process the objects (using a similar methodology
as introduced in [15]).
To identify which objects are the nearest neighbors over a given time
interval, the authors of [81] propose a hierarchical data structure such
that for each node in the tree, that object has the highest probability,
besides the parent, of being the nearest neighbor to the query within
the time interval bounded by the parent. That is, the first level of the
tree would be the nearest neighbors, each over its disjunct time interval.
The second level would be nodes that are second nearest neighbors over
disjunct time intervals bounded by their parent, and so on. They show
how to construct this structure and use it to answer the NN query and
several deviations.
In addition to range and nearest-neighbor queries, other, more com-
plicated, queries have been defined on spatiotemporal data [4, 29]. For
instance, Bakalov et al. [4] introduce a spatiotemporal join query that
