Efficient Processing of All-Nearest Spatial Queries in Road Networks

Abstract

The rapid expansion of GPS-enabled smartphone usage has significantly boosted the_x000D_ <br>popularity of Location-Based Service (LBS) applications. This trend has led to an increase_x000D_ <br>in spatial query requests, that use spatial proximity, and compute the results based on the_x000D_ <br>closeness of the answer objects. One crucial category of these spatial queries is the All_x000D_ <br>Nearest Neighbor (ANN) queries. These queries are essential in identifying and returning_x000D_ <br>the nearest data objects to all query objects, based on their spatial proximity. However,_x000D_ <br>ANN queries inherently combine nearest neighbor and join operations, making them_x000D_ <br>computationally intensive._x000D_ <br>Most existing studies on ANN queries focus on Euclidean spaces or static road networks._x000D_ <br>Recognizing the limitations in these approaches, especially in dynamic road network_x000D_ <br>scenarios where traffic conditions can alter route weights, our research introduces the_x000D_ <br>Standard Clustered Loop (SCL) algorithm. This algorithm leverages a shared-execution_x000D_ <br>approach to efficiently process ANN queries on dynamic road networks. By reducing_x000D_ <br>redundant nearest neighbor query evaluations, SCL offers a significant improvement in_x000D_ <br>processing efficiency._x000D_ <br>Moreover, the widespread applications such as transportation optimization and ridesharing_x000D_ <br>demand handling of massive ANN query workloads demand distributed processing_x000D_ <br>for smooth operation. Addressing this need, we propose a distributed query_x000D_ <br>processing framework ParSCL. The proposed framework is designed to operate on a road_x000D_ <br>network and utilizes Apache Spark for distributed processing, ensuring scalability and_x000D_ <br>high performance. ParSCL advances the field by implementing a parallel and distributed_x000D_ <br>architecture, which significantly reduces query response time compared to existing methods._x000D_ <br>This framework is particularly adept at handling large datasets, demonstrating_x000D_ <br>superior performance in empirical evaluations using real-world road network maps. Our_x000D_ <br>research marks a significant advancement from specialized ANN algorithms tailored for_x000D_ <br>road networks to sophisticated distributed architectures. These architectures are pivotal in_x000D_ <br>enabling large-scale, efficient location-based services, catering to the modern demands of_x000D_ <br>spatial query processing in dynamic environments.