검색 상세

Efficient Processing of All-Nearest Spatial Queries in Road Networks

초록/요약

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 ridesharing 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.

more

목차

1 Introduction 1
1.1 Motivation 2
1.2 Contributions 3
1.2.1 All-Nearest Neighbor Queries on dynamic road networks 3
1.2.2 Distributed Processing of All-Nearest Neighbor Queries on road networks 4
1.3 Thesis Outline 5
2 Background 6
2.1 Spatial Databases 6
2.1.1 Representation 7
2.2 Spatial Queries 8
2.3 Related Work 11
3 Processing All-Nearest Neighbor Queries on Dynamic Road Networks 14
3.1 Overview 14
3.2 Preliminaries 17
3.2.1 Illustration of Dynamic Road Network 17
3.2.2 Classification of Nodes 18
3.2.2.1 Node Sequence and Segments 18
3.2.3 All Nearest Neighbor Query 19
3.3 Method of Clustering Query Objects 20
3.3.1 Methodology 20
3.3.2 Clustering Algorithm 22
3.4 SCL Design 24
3.4.1 Overview of SCL 24
3.4.2 Evaluation of SCL 29
3.4.3 Complexity Analysis 31
3.5 Evaluation of the SCL Framework 31
3.5.1 Experimental Settings 32
3.5.2 Performance Evaluation 33
3.5.3 Discussion 38
4 Distributed and Parallel SCL Framework 42
4.1 Overview 42
4.1.1 Preliminaries 45
4.2 ParSCL Design Architecture 46
4.2.1 Road Network Partitioning 46
4.2.2 Boundary nodes and edges 47
4.2.3 Embedded Graph Network 48
4.2.4 Distance Array Table 50
4.2.5 Query Procedure 52
4.2.5.1 Pruning Heuristics 56
4.2.6 Framework Design 56
4.2.6.1 Build Procedure 57
4.2.6.2 Query Procedure 60
4.2.7 Performance Analysis 60
4.3 Experimental Evaluation 61
4.3.1 Experimental Setup 61
4.3.1.1 Datasets 61
4.3.1.2 Experimental Settings 62
4.3.2 Experimental Results 63
4.3.2.1 Precomputation Time 63
4.3.2.2 Performance Evaluation 65
4.3.3 Discussions 71
5 Conclusions 74
Bibliography 76
A List of Publications 83
A.1 SCI/SCIE Journal Papers 83

more
반출 Meta View 목록