Hongjun Zhu, Jianwen Su, and Oscar H. Ibarra
Trajectory Queries and Octagons in Moving Object Databases
Proceedings of the ACM Conference on Information and Knowledge
Management (CIKM), McLean, VA, November 5-7, Pages 413-421,
2002
An important class of queries in moving object databases involves
trajectories. We propose to divide trajectory predicates into
topological and non-topological parts; extend the 9-intersection model
of Egenhofer-Franzosa to a 3-step evaluation strategy for trajectory
queries: a filter step, a refinement step, and a tracing step.
The filter and refinement steps are similar to region searches. As in
spatial databases, approximations of trajectories are typically used
in evaluating trajectory queries. In earlier studies, minimum
bounding boxes (MBRs) are used to approximate trajectory segments
which allow index structures to be built, e.g., TB-trees and R*-trees.
The use of MBRs hinders the efficiency since MBRs are very coarse
approximations especially for trajectory segments. To overcome this
problem, we propose a new type of approximations, "minimum bounding
octagon prism" (MBOP). We extend R*-tree to a new index structure
"Octagon-Prism tree" (OP-trees) for MBOPs of trajectory segments. We
conducted experiments to evaluate efficiency of OP-trees in performing
region searches and trajectory queries. The results show that
OP-treess improve region searches significantly over synthetic
trajectory data sets to TB-trees and R*-trees and can significantly
reduce the evaluation cost of trajectory queries compared to TB-trees.