QR-tree: An efficient and scalable method for evaluation of continuous range queries

In this paper, we explore the problem of the scalable evaluation of continuous range queries (CRQs) over moving objects, each of which continually retrieves the moving objects that are currently within a given query region of interest. Most existing methods assume that moving objects continually communicate with the server to report their current locations and the server continuously updates the results of queries. However, such an assumption degrades the system performance, because the communication cost is huge and the server workload is increased when the number of moving objects and queries is enormous. In this paper, we propose a novel query indexing structure, referred to as the Query Region tree (QR-tree), which allows the server to cooperate with moving objects efficiently by leveraging the available computational resources of the moving objects to improve the overall system performance. In addition, we present another version of the QR-tree, called the Bit-vector Query Region tree (BQR-tree), for the evaluation of CRQs that specify additional non-spatial selections. The BQR-tree stores a summary of the non-spatial information specified by CRQs in the form of bit-vectors. Through a series of comprehensive simulations, we verify the efficiency of the QR-tree and the BQR-tree in terms of the communication cost and server workload.