A Batch Processing Algorithm for Moving k-Nearest Neighbor Queries in Dynamic Spatial Networks
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Location-based services (LBSs) are expected to process a large number of spatial queries, such as shortest path and k-nearest neighbor queries that arrive simultaneously at peak periods. Deploying more LBS servers to process these simultaneous spatial queries is a potential solution. However, this significantly increases service operating costs. Recently, batch processing solutions have been proposed to process a set of queries using shareable computation. In this study, we investigate the problem of batch processing moving k-nearest neighbor (MkNN) queries in dynamic spatial networks, where the travel time of each road segment changes frequently based on the traffic conditions. LBS servers based on one-query-at-a-time processing often fail to process simultaneous MkNN queries because of the significant number of redundant computations. We aim to improve the efficiency algorithmically by processing MkNN queries in batches and reusing sharable computations. Extensive evaluation using real-world roadmaps shows the superiority of our solution compared with state-of-the-art methods.
Abstract
Location-based services (LBSs) are expected to process a large number of spatial queries, such as shortest path and k-nearest neighbor queries that arrive simultaneously at peak periods. Deploying more LBS servers to process these simultaneous spatial queries is a potential solution. However, this significantly increases service operating costs. Recently, batch processing solutions have been proposed to process a set of queries using shareable computation. In this study, we investigate the problem of batch processing moving k-nearest neighbor (MkNN) queries in dynamic spatial networks, where the travel time of each road segment changes frequently based on the traffic conditions. LBS servers based on one-query-at-a-time processing often fail to process simultaneous MkNN queries because of the significant number of redundant computations. We aim to improve the efficiency algorithmically by processing MkNN queries in batches and reusing sharable computations. Extensive evaluation using real-world roadmaps shows the superiority of our solution compared with state-of-the-art methods.
참고문헌 (18)
- 김태이, "도로 네트워크에서 k-최원접 이웃 질의를 효율적으로 처리하는 방법", 한국컴퓨터정보학회논문지, 24(10), pp.79~89 (2019), 한국컴퓨터정보학회[DOI]
- F. M. Choudhury, "Batch processing of top-k spatial-textual queries", ACM Transactions on Spatial Algorithms and Systems, 3(4), pp.13~ (2018)
- K. C. K. Lee, "ROAD : a new spatial object search framework for road networks", IEEE Transactions on Knowledge and Data Engineering, 24(3), pp.547~560 (2012)
- D. Papadias, "Query processing in spatial network databases", Proc. of International Conference on Very Large Data Bases, pp.802~813 (2003)
- B. Shen, "V-tree : efficient knn search on moving objects with road-network constraints", Proc. of International Conference on Data Engineering, pp.609~620 (2017)
- R. Zhong, "G-tree : an efficient and scalable index for spatial search on road networks", IEEE Transactions on Knowledge and Data Engineering, 27(8), pp.2175~2189 (2015)
- Y. Xu, "Finding all nearest neighbors with a single graph traversal", Proc. of International Conference on Database Systems for Advanced Applications, pp.221~238 (2018)
- H. Samet, "Scalable network distance browsing in spatial databases", Proc. of International Conference on Mobile Data Management, pp.43~54 (2008)
- T. Abeywickrama, "Efficient landmark-based candidate generation for knn queries on road networks", Proc. of International Conference on Database Systems for Advanced Applications, pp.425~440 (2017)
- B. Cao, "SIMkNN : a scalable method for in-memory knn search over moving objects in road networks", IEEE Transactions on Knowledge and Data Engineering, 30(10), pp.1957~1970 (2018)
- T. Dong, "Direction-aware continuous moving k-nearest-neighbor query in road networks", ISPRS International Journal of Geo-Information, 8(9), pp.379~ (2019)
- S. Luo, "TOAIN : a throughput optimizing adaptive index for answering dynamic knn queries on road networks", PVLDB, 11(5), pp.594~606 (2018)
- Y. Yang, "A novel index method for k nearest object query over time-dependent road networks", Complexity, pp.4829164~ (2019)
- B. Zheng, "Keyword-aware continuous knn query on road networks", Proc. of International Conference on Data Engineering, pp.871~882 (2016)
- U. Demiryurek, "Efficient continuous nearest neighbor query in spatial networks using Euclidean restriction", Proc. of International Symposium on Advances in Spatial and Temporal Databases, pp.25~43 (2009)
- K. Mouratidis, "Continuous nearest neighbor monitoring in road networks", Proc. of International Conference on Very Large Data Bases, pp.43~54 (2006)
- "9th DIMACS Implementation Challenge: Shortest Paths"[URL]
- "Real Datasets for Spatial Databases"[URL]