Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial Networks
This paper considers <i>k</i>-farthest neighbor (<i>k</i>FN) join queries in spatial networks where the distance between two points is the length of the shortest path connecting them. Given a positive integer <i>k</i>, a set of query points <i>Q</i>, a...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-02-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2220-9964/11/2/123 |
| _version_ | 1797479466542301184 |
|---|---|
| author | Hyung-Ju Cho |
| author_facet | Hyung-Ju Cho |
| author_sort | Hyung-Ju Cho |
| collection | DOAJ |
| description | This paper considers <i>k</i>-farthest neighbor (<i>k</i>FN) join queries in spatial networks where the distance between two points is the length of the shortest path connecting them. Given a positive integer <i>k</i>, a set of query points <i>Q</i>, and a set of data points <i>P</i>, the <i>k</i>FN join query retrieves the <i>k</i> data points farthest from each query point in <i>Q</i>. There are many real-life applications using <i>k</i>FN 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 <i>k</i>FN queries required to perform the <i>k</i>FN 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. |
| first_indexed | 2024-03-09T21:46:19Z |
| format | Article |
| id | doaj.art-b6337bf7d7604e809902ebe4908c988f |
| institution | Directory Open Access Journal |
| issn | 2220-9964 |
| language | English |
| last_indexed | 2024-03-09T21:46:19Z |
| publishDate | 2022-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj.art-b6337bf7d7604e809902ebe4908c988f2023-11-23T20:16:11ZengMDPI AGISPRS International Journal of Geo-Information2220-99642022-02-0111212310.3390/ijgi11020123Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial NetworksHyung-Ju Cho0Department of Software, Kyungpook National University, 2559 Gyeongsang-daero, Sangju-si 37224, KoreaThis paper considers <i>k</i>-farthest neighbor (<i>k</i>FN) join queries in spatial networks where the distance between two points is the length of the shortest path connecting them. Given a positive integer <i>k</i>, a set of query points <i>Q</i>, and a set of data points <i>P</i>, the <i>k</i>FN join query retrieves the <i>k</i> data points farthest from each query point in <i>Q</i>. There are many real-life applications using <i>k</i>FN 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 <i>k</i>FN queries required to perform the <i>k</i>FN 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.https://www.mdpi.com/2220-9964/11/2/123cluster nested loop join<i>k</i>-farthest neighbor joinspatial networkshared execution |
| spellingShingle | Hyung-Ju Cho Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial Networks ISPRS International Journal of Geo-Information cluster nested loop join <i>k</i>-farthest neighbor join spatial network shared execution |
| title | Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial Networks |
| title_full | Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial Networks |
| title_fullStr | Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial Networks |
| title_full_unstemmed | Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial Networks |
| title_short | Cluster Nested Loop <i>k</i>-Farthest Neighbor Join Algorithm for Spatial Networks |
| title_sort | cluster nested loop i k i farthest neighbor join algorithm for spatial networks |
| topic | cluster nested loop join <i>k</i>-farthest neighbor join spatial network shared execution |
| url | https://www.mdpi.com/2220-9964/11/2/123 |
| work_keys_str_mv | AT hyungjucho clusternestedloopikifarthestneighborjoinalgorithmforspatialnetworks |