Database Reference
In-Depth Information
Figure 10.3.
In (A), only point
a
has been processed and is thus the NN for both
SPs
s
and
e
. In (B), after processing point
b
, we update the NN of
e
and create a
new SP
s
1.
intervals (as well as time slices). However, it is not clear how SETI
compares to TB-tree for
combined queries
, in which the query is both
topological and navigational (mentioned in [66]), where processing may
be required to access different segments of the same trajectory (which
TB-tree does eciently). A similar approach was simultaneously devel-
oped by Song et al. [75] in which the authors split the space and time
dimensions.
In addition to the range query, nearest-neighbor and
k
-NN queries are
also fundamental for any spatiotemporal data management system. For
identifying nearby objects in the context of trajectory data, the contin-
uous nearest-neighbor (CNN) query has been proposed in which a se-
quence of nearest neighbors are returned such that the nearest-neighbor
(NN) is known for every time interval [27, 77]. Tao et al. [77] introduce
the CNN query and develop an ecient query processing algorithm.
The objective in processing a CNN is to identify, for every time range
within the query interval, the nearest object to the query trajectory.
The authors use a geometric approach in which a set of
split points
,lo-
cations at which the NN of the query trajectory changes, is maintained
and incrementally updated during processing. Trajectories are processed
by considering each line segment separately and aggregating the results
through post-processing. The algorithm starts with the end points of
the line segment being the two split points (SPs). Objects (i.e. spatial
points) in the database are processed sequentially. For each object, we
first check if it is the NN to any split points. This is done by maintaining
a circle centered at each split point such that the radius is the distance
to the closest (known) object. If a new object lies within this circle, then
we must update the SPs and adjust the radii. Updates to SPs are made
by computing the perpendicular bisector, the point at which this line
intersects the trajectory will become a new SP. This process is shown in
