文章基本信息

标题：Cluster Nested Loop k-Farthest Neighbor Join Algorithm for Spatial Networks
本地全文：下载
作者：Hyung-Ju Cho
期刊名称：ISPRS International Journal of Geo-Information
电子版ISSN：2220-9964
出版年度：2022
卷号：11
期号：2
页码：123
DOI：10.3390/ijgi11020123
语种：English
出版社：MDPI AG
摘要：This paper considers k-farthest neighbor (kFN) join queries in spatial networks where the distance between two points is the length of the shortest path connecting them. Given a positive integer k, a set of query points Q, and a set of data points P, the kFN join query retrieves the k data points farthest from each query point in Q. There are many real-life applications using kFN join queries, including artificial intelligence, computational geometry, information retrieval, and pattern recognition. However, the solutions based on the Euclidean distance or nearest neighbor search are not suitable for our purpose due to the difference in the problem definition. Therefore, this paper proposes a cluster nested loop join (CNLJ) algorithm, which clusters query points (data points) into query clusters (data clusters) and reduces the number of kFN queries required to perform the kFN join. An empirical study was performed using real-life roadmaps to confirm the superiority and scalability of the CNLJ algorithm compared to the conventional solutions in various conditions.