Trajectory queries and octagons in moving object databases Hongjun Zhu, Jianwen Su, and Oscar H. Ibarra   View Paper (PDF)   Return to Spatial search and moving objects Abstract 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-tree) 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-trees 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. DiSC'03 © 2003 Association for Computing Machinery