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