Nine-areas-tree-bit-patterns-based method for continuous range queries over moving objects

摘要

A continuous range query is defined to periodically re-evaluated to locate moving objects that are currently inside the boundary of the range query and is widely used to support the location-based services. However, the query processing becomes complicated because of frequent locations update of moving objects. The query indexing relies on incremental evaluation, building the index on range queries instead of moving objects and exploiting the relation between locations objects and queries. The cell-based query indexing method has been proved to have the better performance of query processing than that of the R??-tree-based query indexing method with the overlapping problem in internal nodes. However, it takes a lot of space and time for the cell-based method to maintain the index structure, when the number of range queries increases. The nine-areas (NA) tree has been proved to solve the overlapping problem in the R*-tree to minimise the number of disk accesses during a tree search for the range queries. In this study, the authors propose the NAtree- bit-patterns-based (NABP) query indexing method based on the NA-tree. We use the bit-patterns to denote the regions and to preserve the locality of range queries and moving objects. Therefore our NABP method can incrementally local update the affected range queries over moving objects by bit-patterns operations, especially with the increase of the number of range queries. From their simulation study, the authors show that their NABP method requires less CPU time and storage cost than the cell-based method for large number of range queries update. The authors also show that their NABP method requires less CPU time than the R*-tree-based method for large number of moving objects update.