A Line Graph-Based Continuous Range Query Method for Moving Objects in Networks

Abstract

The rapid growth of location-based services has motivated the development of continuous range queries in networks. Existing query algorithms usually adopt an expansion tree to reuse the previous query results to get better efficiency. However, the high maintenance costs of the traditional expansion tree lead to a sharp efficiency decrease. In this paper, we propose a line graph-based continuous range (LGCR) query algorithm for moving objects in networks, which is characterized by a novel graph-based expansion tree (GET) structure used to monitor queries in an incremental manner. In particular, GET is developed based on the line graph model of networks and simultaneously supports offline pre-computation to better adapt our proposed algorithm to different sizes of networks. To improve performance, we create a series of related data structures, such as bridgeable edges and distance edges. Correspondingly, we develop several algorithms, including initialization, insertion of objects, filter and refinement and location update, to incrementally re-evaluate continuous range queries. Finally, we implement the GET and related algorithms in the native graph database Neo4J. We conduct experiments using real-world networks and simulated moving objects and compare the proposed LGCR with the existing classical algorithm to verify its effectiveness and demonstrate its greater efficiency.

Keywords

• moving objects
• continuous range queries
• network
• expansion tree