Processing Moving Queries over Moving Objects Using Motion Adaptive Indexes

This paper describes a motion adaptive indexing scheme for efficient evaluation of moving queries (MQs) over moving objects. It uses the concept of motion-sensitive bounding boxes to model the dynamic behavior of both moving objects and moving queries. Instead of indexing frequently changing object positions, we index less frequently changing motion sensitive bounding boxes together with the motion functions of the objects. This significantly decreases the number of update operations performed on the indexes. We use predictive query results to optimistically precalculate query results, thus decreasing the number of search operations performed on the indexes. More importantly, we propose a motion adaptive indexing method. Instead of using fixed parameters for motion sensitive bounding boxes, we automatically adapt the sizes of the motion sensitive bounding boxes to the dynamic motion behaviors of the corresponding individual objects. As a result, the moving queries can be evaluated faster by performing fewer IOs. Furthermore, we introduce the concept of guaranteed safe radius and optimistic safe radius to extend our motion adaptive indexing scheme to evaluating moving continual k-nearest neighbor (kNN) queries. Our experiments show that the proposed motion adaptive indexing scheme is efficient for evaluation of both moving continual range queries and moving continual kNN queries