Distributed Processing Of Range Queries Over Large Scale Moving Objects

Given a set of moving objects and a query range with the center of query point q and the radius of query point r,the problem of continuous range query for large-scale moving objects refers to computing the moving objects in the query range in real time,and updating the moving objects in the query range continuously as the locations of the moving objects and the query point change.The continuous range query problem of large-scale moving objects is one of the basic problems that many location-based services need to deal with.To solve this problem,the existing works usually focus on the centralized moving object range query algorithm of a single computing node.Due to the limited storage and computing resources of a single computing node,it is difficult for these algorithms to respond to high concurrent range queries for massive moving objects in real time.Location-based services(LBS)is facing the challenge of solving large-scale concurrent query requests in a short time.In addition,the applications of location-based services pay more attention to the range query algorithm of distributed moving objects for road network,because moving objects such as people and vehicles usually move on the road network,and their location and moving direction are limited by the road.However,the existing strategies have a significant drawback,when the query range is large,there are a large number of vertices to be retrieved in the search range,which leads to a long query time.In order to solve the above problems,this paper proposes a distributed moving object range query algorithm for Euclidean space and a distributed moving object range query algorithm for road network.1)The moving object range query in Euclidean space is to determine whether the moving object is in the query range by the linear distance between the query point and the moving object.The core idea is to prune the search range of the Euclidean space,so as to improve the query efficiency.Therefore,this paper proposes a distributed index structure for moving objects,which is composed of a global grid index and a local elastic quadtree.The index structure can dynamically adjust the index granularity of different regions according to the distribution density of moving objects,so as to improve the precision pruning efficiency of query algorithm and reduce the maintenance cost effectively.In addition,the index structure is easy to maintain and deploy to the distributed environment,and it supports the query algorithm to decompose the same range query into multiple sub-queries processed by different computing nodes in parallel,so it has good scalability.Based on the index structure,this paper proposes an incremental continuous query algorithm.When processing large-scale concurrent queries in parallel,the algorithm proposes a shared computing strategy for multiple concurrent queries,and can incrementing the query results of moving object range queries according to the existing computing results,which effectively reduces the query cost.2)The range query for moving objects in road network starts from the query point and expands along the road network until the specified query range is detected,and then retrieves each road segment with moving objects in the range.In this paper,we first design an efficient partitioning subgraph algorithm to deal with road networks.It first divides the complete road network into multiple subgraphs and identifies each candidate subgraph that has intersection with the query range,and then retrives the moving objects within these candidate subgraphs.The key idea of the algorithm is to make the partitioned subgraphs have the boundary constraint property,which can help the query algorithm to filter out the subgraphs that must be in the query range and the subgraphs that intersect with the query range without checking the inside of the subgraph.Subsequently,graduation thesis proposes a distributed range query algorithm that can efficiently process the filtered subgraphs in parallel.Finally,based on six real road network datasets and four benchmark algorithms,experiments are carried out to verify the superiority of the algorithm.