Processing continual range queries over moving objects using VCR-based query indexes

Abstract

This paper describes VCR-based 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 mapping from each VCR to the range queries that contain that VCR. 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 VCR boundaries. We study different strategies to cover a query region with VCRs and conduct simulations to compare them.