On incremental processing of continual range queries for location-aware services and applications

Abstract

A set of continual range queries, each defining the geographical region of interest, can be periodically reevaluated to locate moving objects. Processing these continual queries efficiently and incrementally hence becomes important for location-aware services and applications. In this paper, we study a new query indexing method, called CES-based indexing, for incremental processing of continual range queries over moving objects. A set of containment-encoded squares (CES) are predefined, each with a unique ID. CES's are virtual constructs (VC) used to decompose query regions and to store indirectly precomputed search results. Compared with a prior VC-based approach, the number of VC's visited in an index search in CES-based indexing is reduced from (4L 2 - 1)/3 to log(L) + 1, where L is the maximal side length of a VC. Search time is hence significantly lowered. Moreover, containment encoding among the CES's makes it easy to identify all those VC's that need not he visited during an incremental query reevaluation. We study the performance of CES-based indexing and compare it with a prior VC-based approach. © 2005 IEEE.