Processing Continual Range Queries over Moving Objects Using VCR-Based Query Indexes

This paper describes VCR-based (Virtual Construct Rectangle) query indexes for efficient processing of continual range queries over moving objects. A set of virtual construct rectangles (VCR) is predefined, each with a unique ID. One or more VCRs is used to strictly cover the entire region defined by a range query. The query index maintains a direct mapping from each VCR to the range queries that contain it. The use of VCRs provides an indirect and cost-effective way of pre-computing the search result for any object position, making possible efficient search operations. More importantly, it allows the processing of continual range queries to capitalize on incremental changes in object locations. Computation can be saved for objects that have not moved out of the VCR boundaries. We study different strategies to cover a query region with VCRs and conduct simulations to compare them.

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

Published in: Proceedings of MOBIQUITOUS 2004: The First Annual International Conference on Mobile and Ubiquitous Systems - Networking and Services. Los Alamitos, CA, , IEEE Computer Society. , p.226-35 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

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