On Incremental Processing of Continual Range Queries for Location-Aware Services and Applications

A set of continual range queries, each defining the geographical region of interest, can be periodically re-evaluated 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 pre-computed 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 (4L2 - 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 be visited during an incremental query reevaluation. We study the performance of CES-based indexing and compare it with a prior VC-based approach.

By: Kun-Lung Wu; Shyh-Kwei Chen; Philip S. Yu

Published in: RC23635 in 2005


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .