A distributed hybrid index for processing continuous range queries over moving objects

摘要

Central to many location-based services is the problem of processing concurrent continuous range queries over a large scale of moving objects. Most relevant works to this problem mainly investigate the centralized search algorithms based on a single server for handling range queries. However, due to the limited resources of a single server, these algorithms hardly can deal with an ocean of objects and extensive concurrent queries. Moreover, these approaches usually suppose either objects or queries are static but seldom consider the scenario that objects and queries are both moving simultaneously, restricting the practicability of these approaches. To resolve the above issues, we propose a distributed hybrid index (DHI) that consists of a global grid index and extensive local VR-tree indexes. DHI is apt to be deployed on a cluster of servers, and owns a good scalability to maintain numerous moving objects and concurrent range queries. Based on DHI, we further design a distributed incremental search approach, which organizes multiple servers with a publish/subscribe mechanism to calculate and monitor the results for continuous range queries in a distributed pattern. Finally, we conduct extensive experiments to fully evaluate the performance of our paper.