Hongjun Zhu
http://www.cs.ucsb.edu/~hongjunz
Octagons, octagon trees, and moving objects trajectories
An important class of queries in moving object databases are queries over
their trajectories. In most cases, trajectories are modeled as chains of
line segments. Point search, line search, and polygon based region search
are fundamental operations in evaluation of trajectory queries. Similar
to searches in traditional spatial databases, these searches can be
performed in the following two steps: (1) a filter step that applies the
searches to the minimum bounding rectangles (MBRs) of the trajectories,
and (2) a refinement step that applies the queries on the trajectories
reported by the filter step. Unfortunately, MBRs are very coarse
approximations for trajectories. In this paper, we separate space and
time when approximating trajectories and focus on approximating the space
components of trajectories. In particular, we propose a new type of
approximations based on ``convex octagons''. A minimum bounding (convex)
octagon (MBO) of an object is an octagon with the smallest area where two
pairs of two opposite sides must be parallel to each axis. For linear
trajectories, our algorithm generates an MBO by cutting off the four
corners of the MBR. We develope a new index
structure, ``Octagon-trees'', for 2 dimensional objects and an extension,
``Octagon-trees with time'', for trajectories of 2 dimensional moving
points. Experiments show that Octagon-trees with time improve region
searches significantly over trajectories generated by the GSTD algorithm
and a network-based generator by Brinkhoff. In particular, both
the I/O cost and the CPU cost are reduced by about 30%.
In order to understand the impact of the octagon
index technique, we also compared Octagon-trees with 2-d R*-trees. The
results show that Octagon-trees out-perform R*-trees for point,
line, and window searches when the size of query windowes are small.