Efficient Processing of k-Farthest Neighbor Queries for Road Networks (도로 네트워크에서 k-최원접 이웃 질의를 효율적으로 처리하는 방법)

Taelee， Kim (김태이); Hyung-Ju Cho (조형주); Hee Ju Hong (홍희주); Hyogeun Nam (남효근); Hyejun Cho (조혜준); Gyung Yoon Do (도경윤); Pilkyu Jeon (전필규)

doi:10.9708/jksci.2019.24.10.079

Efficient Processing of k-Farthest Neighbor Queries for Road Networks

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2019, 24(10), pp.79-89
DOI : 10.9708/jksci.2019.24.10.079
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science
Received : September 11, 2019
Accepted : October 7, 2019
Published : October 31, 2019

Taelee， Kim ¹, Hyung-Ju Cho ¹, Hee Ju Hong ², Hyogeun Nam ², Hyejun Cho ², Gyung Yoon Do ², Pilkyu Jeon ³

¹경북대학교
²대구과학고등학교
³대구과학교등학교

Accredited

ABSTRACT

While most research focuses on the k-nearest neighbors (kNN) queries in the database community, an important type of proximity queries called k-farthest neighbors (kFN) queries has not received much attention. This paper addresses the problem of finding the k-farthest neighbors in road networks. Given a positive integer k, a query object q, and a set of data points P, a kFN query returns k data objects farthest from the query object q. Little attention has been paid to processing kFN queries in road networks. The challenge of processing kFN queries in road networks is reducing the number of network distance computations, which is the most prominent difference between a road network and a Euclidean space. In this study, we propose an efficient algorithm called FANS for k-FArthest Neighbor Search in road networks. We present a shared computation strategy to avoid redundant computation of the distances between a query object and data objects. We also present effective pruning techniques based on the maximum distance from a query object to data segments. Finally, we demonstrate the efficiency and scalability of our proposed solution with extensive experiments using real-world roadmaps.

KEYWORDS

k-Farthest neighbor query, Road network, Minimum distance, Maximum distance

Citation status

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

[journal] R. R. Curtin / 2019 / Exploiting the Structure of Furthest Neighbor Search for Fast Approximate Results / Information Systems 80 : 124~135

[confproc] B. Yao / 2009 / Reverse Furthest Neighbors in Spatial Databases / Proceedings of International Conference on Data Engineering : 664~675

[journal] X. -J. Xu / 2017 / Reverse Furthest Neighbors Query in Road Networks / Journal of Computer Science and Technology 32(1) : 155~167

[confproc] J. Liu / 2012 / An Efficient Algorithm for Arbitrary Reverse Furthest Neighbor Queries / Proceedings of Asia-Pacific Web Conference : 60~72

[journal] Q. T. Tran / 2009 / Reverse k Nearest Neighbor and Reverse Farthest Neighbor Search on Spatial Networks / Transactions on Large-Scale Data-and Knowledge-Centered Systems I 5740 : 353~372

[confproc] H. Wang / 2014 / Efficient Aggregate Farthest Neighbour Query Processing on Road Networks / Proceedings of the Australasian Database Conference : 13~25

[confproc] D. Papadias / 2003 / Query Processing in Spatial Network Databases / Proceedings of International Conference on Very Large Data Bases : 802~813

[journal] C. Shahabi / 2003 / A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases / GeoInformatica 7(3) : 255~273

[confproc] M.R. Kolahdouzan / 2004 / Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases / Proceedings of International Conference on Very Large Data Bases : 840~851

[confproc] X. Huang / 2005 / The Islands Approach to Nearest Neighbor Querying in Spatial Networks / Proceedings of International Symposium on Spatial and Temporal Databases : 73~90

[confproc] H. Samet / 2008 / Scalable Network Distance Browsing in Spatial Databases / Proceedings of International Conference on Management of Data : 43~54

[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] N. Beckmann / 1990 / The R*-Tree : An Efficient and Robust Access Method for Points and Rectangles / Proceedings of International Conference on Management of Data : 322~331

[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

[journal] T. Abeywickrama / 2016 / k-Nearest Neighbors on Road Networks : A Journey in Experimentation and In-Memory Implementation / Proceedings of the VLDB Endowment 9(6) : 492~503

[confproc] Y. Gao / 2011 / Aggregate Farthest-Neighbor Queries over Spatial Data / Proceedings of International Conference on Database Systems for Advanced Applications : 149~163

[confproc] S. Wang / 2016 / Efficiently Computing Reverse k Furthest Neighbors / Proceedings of International Conference on Data Engineering : 1110~1121

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

[journal] L. Wu / 2012 / Shortest Path and Distance Queries on Road Networks : An Experimental Evaluation / Proceedings of the VLDB Endowment 5(5) : 406~417

[confproc] H. Bast / 2006 / TRANSIT : Ultrafast Shortest-Path Queries with Linear-Time Preprocessing / Proceedings of 9th DIMACS Implementation Challenge : 175~192

[journal] 유지현 / 2016 / CRM using short range location based technology / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 21(12) : 91~96

KJCKorea
Journal Central

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

Efficient Processing of k-Farthest Neighbor Queries for Road 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

Efficient Processing of k-Farthest Neighbor Queries for Road Networks

ABSTRACT

KEYWORDS

Statistics

Tools

Issue List

Citation status

KCI Citation Counts (1)

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

Search PDF

Citation

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