도로 네트워크에서 k-최원접 이웃 질의를 효율적으로 처리하는 방법
Efficient Processing of k-Farthest Neighbor Queries for Road Networks
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 연구에서는 도로 네트워크에서 k-최원접 이웃 검색을 위한 효율적인 FANS(k-FArthest Neighbor Search) 알고리즘을 제안한다. 양의 정수 k, 질의 객체 q, 일련의 데이터 객체 집합 P가 주어지면, k-최원접이웃 질의는 질의 객체 q에서 가장 멀리 있는 k개의 데이터 객체를 찾는다. 데이터베이스 분야에서대부분의 연구는 k-최근접 이웃 질의에 중점을 두고 있어서, k-최원접 이웃 질의라는 중요한 근접 질의유형은 별다른 관심을 받지 못했다. 이 논문에서는 도로 네트워크에서 가장 멀리 있는 이웃을 찾는문제를 다룬다. 도로 네트워크에서 k-최원접 이웃 질의를 처리하는 연구는 거의 없었다. 도로 네트워크에서k-최원접 이웃 질의를 처리해야 하는 문제는 최단 경로 거리를 계산하는 횟수를 줄이는 것인데, 이는도로 네트워크와 유클리드 공간의 질의 처리에서 가장 중요한 차이다. 질의 객체와 데이터 객체 사이의최단 경로 거리에 대한 중복 계산을 줄이기 위하여 공유 계산 전략을 사용한다. 질의 객체에서 데이터세그먼트까지 최대 거리를 기반으로 효과적으로 후보군을 제거하는 방법은 제시한다. 마지막으로 실제도로 지도를 사용한 광범위한 실험을 통해 제시된 방법의 효율성과 확장성을 보여준다.
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.
참고문헌 (21)
- R. R. Curtin, "Exploiting the Structure of Furthest Neighbor Search for Fast Approximate Results", Information Systems, 80, pp.124~135 (2019)
- B. Yao, "Reverse Furthest Neighbors in Spatial Databases", Proceedings of International Conference on Data Engineering, pp.664~675 (2009)
- X. -J. Xu, "Reverse Furthest Neighbors Query in Road Networks", Journal of Computer Science and Technology, 32(1), pp.155~167 (2017)
- J. Liu, "An Efficient Algorithm for Arbitrary Reverse Furthest Neighbor Queries", Proceedings of Asia-Pacific Web Conference, pp.60~72 (2012)
- Q. T. Tran, "Reverse k Nearest Neighbor and Reverse Farthest Neighbor Search on Spatial Networks", Transactions on Large-Scale Data-and Knowledge-Centered Systems I, 5740, pp.353~372 (2009)
- H. Wang, "Efficient Aggregate Farthest Neighbour Query Processing on Road Networks", Proceedings of the Australasian Database Conference, pp.13~25 (2014)
- D. Papadias, "Query Processing in Spatial Network Databases", Proceedings of International Conference on Very Large Data Bases, pp.802~813 (2003)
- C. Shahabi, "A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases", GeoInformatica, 7(3), pp.255~273 (2003)
- M.R. Kolahdouzan, "Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases", Proceedings of International Conference on Very Large Data Bases, pp.840~851 (2004)
- X. Huang, "The Islands Approach to Nearest Neighbor Querying in Spatial Networks", Proceedings of International Symposium on Spatial and Temporal Databases, pp.73~90 (2005)
- H. Samet, "Scalable Network Distance Browsing in Spatial Databases", Proceedings of International Conference on Management of Data, pp.43~54 (2008)
- 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)
- N. Beckmann, "The R*-Tree : An Efficient and Robust Access Method for Points and Rectangles", Proceedings of International Conference on Management of Data, pp.322~331 (1990)
- 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)
- T. Abeywickrama, "k-Nearest Neighbors on Road Networks : A Journey in Experimentation and In-Memory Implementation", Proceedings of the VLDB Endowment, 9(6), pp.492~503 (2016)
- Y. Gao, "Aggregate Farthest-Neighbor Queries over Spatial Data", Proceedings of International Conference on Database Systems for Advanced Applications, pp.149~163 (2011)
- S. Wang, "Efficiently Computing Reverse k Furthest Neighbors", Proceedings of International Conference on Data Engineering, pp.1110~1121 (2016)
- "Real datasets for spatial Databases"[URL]
- L. Wu, "Shortest Path and Distance Queries on Road Networks : An Experimental Evaluation", Proceedings of the VLDB Endowment, 5(5), pp.406~417 (2012)
- H. Bast, "TRANSIT : Ultrafast Shortest-Path Queries with Linear-Time Preprocessing", Proceedings of 9th DIMACS Implementation Challenge, pp.175~192 (2006)
- 유지현, "CRM using short range location based technology", 한국컴퓨터정보학회논문지, 21(12), pp.91~96 (2016), 한국컴퓨터정보학회