A Batch Processing Algorithm for Moving k-Nearest Neighbor Queries in Dynamic Spatial Networks

Hyung-Ju Cho (조형주)

doi:10.9708/jksci.2021.26.04.063

A Batch Processing Algorithm for Moving k-Nearest Neighbor Queries in Dynamic Spatial Networks

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2021, 26(4), pp.63-74
DOI : 10.9708/jksci.2021.26.04.063
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science
Received : February 18, 2021
Accepted : March 31, 2021
Published : April 30, 2021

Hyung-Ju Cho ¹

¹경북대학교

Accredited

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.

KEYWORDS

Spatial databases, Moving k-nearest neighbor query, Batch processing, Dynamic spatial network

Citation status

* References for papers published after 2023 are currently being built.

[journal] 김태이 / 2019 / Efficient Processing of k-Farthest Neighbor Queries for Road Networks / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 24(10) : 79~89

[journal] F. M. Choudhury / 2018 / Batch processing of top-k spatial-textual queries / ACM Transactions on Spatial Algorithms and Systems 3(4) : 13~

[journal] K. C. K. Lee / 2012 / ROAD : a new spatial object search framework for road networks / IEEE Transactions on Knowledge and Data Engineering 24(3) : 547~560

[confproc] D. Papadias / 2003 / Query processing in spatial network databases / Proc. of International Conference on Very Large Data Bases : 802~813

[confproc] B. Shen / 2017 / V-tree : efficient knn search on moving objects with road-network constraints / Proc. of International Conference on Data Engineering : 609~620

[journal] R. Zhong / 2015 / G-tree : an efficient and scalable index for spatial search on road networks / IEEE Transactions on Knowledge and Data Engineering 27(8) : 2175~2189

[confproc] Y. Xu / 2018 / Finding all nearest neighbors with a single graph traversal / Proc. of International Conference on Database Systems for Advanced Applications : 221~238

[confproc] H. Samet / 2008 / Scalable network distance browsing in spatial databases / Proc. of International Conference on Mobile Data Management : 43~54

[confproc] T. Abeywickrama / 2017 / Efficient landmark-based candidate generation for knn queries on road networks / Proc. of International Conference on Database Systems for Advanced Applications : 425~440

[journal] B. Cao / 2018 / SIMkNN : a scalable method for in-memory knn search over moving objects in road networks / IEEE Transactions on Knowledge and Data Engineering 30(10) : 1957~1970

[journal] T. Dong / 2019 / Direction-aware continuous moving k-nearest-neighbor query in road networks / ISPRS International Journal of Geo-Information 8(9) : 379~

[journal] S. Luo / 2018 / TOAIN : a throughput optimizing adaptive index for answering dynamic knn queries on road networks / PVLDB 11(5) : 594~606

[journal] Y. Yang / 2019 / A novel index method for k nearest object query over time-dependent road networks / Complexity : 4829164~

[confproc] B. Zheng / 2016 / Keyword-aware continuous knn query on road networks / Proc. of International Conference on Data Engineering : 871~882

[confproc] U. Demiryurek / 2009 / Efficient continuous nearest neighbor query in spatial networks using Euclidean restriction / Proc. of International Symposium on Advances in Spatial and Temporal Databases : 25~43

[confproc] K. Mouratidis / 2006 / Continuous nearest neighbor monitoring in road networks / Proc. of International Conference on Very Large Data Bases : 43~54

[web] / 9th DIMACS Implementation Challenge: Shortest Paths / http://www.dis.uniroma1.it/challenge9/download.shtml

[web] / Real Datasets for Spatial Databases / https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm

This paper was written with support from the National Research Foundation of Korea.

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

A Batch Processing Algorithm for Moving k-Nearest Neighbor Queries in Dynamic Spatial Networks

ABSTRACT

KEYWORDS

Citation status

* References for papers published after 2023 are currently being built.

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

A Batch Processing Algorithm for Moving k-Nearest Neighbor Queries in Dynamic Spatial Networks

ABSTRACT

KEYWORDS

Statistics

Tools

Issue List

Citation status

KCI Citation Counts (1)

REFERENCES (18) * References for papers published after 2023 are currently being built.

Search PDF

Citation

* References for papers published after 2023 are currently being built.