EUVIMEDEUVIMED entdecken
Crossref

Graph Based K-Nearest Neighbor Search Revisited

Jiadong Xie, Jeffrey Xu Yu, Yingfan Liu

ACM Transactions on Database Systems · 31.12.2025 · 50 (4) · 1-30

DOI: 10.1145/3736716 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 30.06.2025. Verfasst von Jiadong Xie und 2 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 66 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The problem of k -nearest neighbor ( k -NN) search is a fundamental problem to find the exact k nearest neighbor points for a user-given query point q in a d -dimensional large dataset D with n points, and the approximate k -NN ( k -ANN) search problem is to find the approximate k -NN. Both are extensively studied to support real applications. Among all approaches, the graph-based approaches have been seen as the best to support k -NN/ANN in recent studies. The state-of-the-art graph-based approach, τ-MG, finds 1-NN, \(\bar{p}_1\) , over a graph index G τ constructed for D based on a predetermined parameter τ where the distance between \(\bar{p}_1\) and q is less than τ, and finds k -ANN based on the approach taken for 1-NN. There are some main issues in τ-MG and other graph-based approaches. One is that it is difficult to predetermine τ which can ensure to find 1-NN and can do it efficiently. This is because the accuracy/efficiency is related to the size of the graph index G τ constructed. To achieve high accuracy is at the expense of efficiency. In addition, like all the other existing graph-based approaches, it does not have a theoretical guarantee to ensure k -NN for the same reason to use the same graph index, G τ , for both 1-NN and k -NN ( k > 1). In this article, we propose a new graph-based approach for k -NN with a theoretical guarantee. We construct a labeled graph, \(\mathcal {G}\) , and we do not need to predetermine τ. Instead, we find 1-NN over a subgraph, \(\mathcal {G}_{\dot{\tau }}\) , of \(\mathcal {G}\) , virtually constructed in a dynamic manner. Here, \(\dot{\tau }\) we use is query-dependent and can be smaller than τ, and the subgraph \(\mathcal {G}_{\dot{\tau }}\) is smaller than G τ when \(\dot{\tau }= \tau\) . We find k -NN in two phases. In the navigation phase, we find 1-NN, \(\bar{p}_1\) , of q over \(\mathcal {G}_{\dot{\tau }}\) . In the second refinement phase, for k > 1, we explore the neighbors within the vicinity region of \(\bar{p}_1\) in \(\mathcal {G}\) . Based on our solution for k -NN in theory, we propose new algorithms to support k -ANN efficiently in practice. We conduct extensive performance studies and confirm the effectiveness and efficiency of our new approach.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Xie, J., Yu, J. X., & Liu, Y. (2025). Graph Based K-Nearest Neighbor Search Revisited. ACM Transactions on Database Systems, 50(4), 1-30. https://doi.org/10.1145/3736716

Vancouver

Xie J, Yu JX, Liu Y. Graph Based K-Nearest Neighbor Search Revisited. ACM Transactions on Database Systems. 2025;50(4):1-30. doi:10.1145/3736716

BibTeX
@article{Xie2025,
  author = {Xie, Jiadong and Yu, Jeffrey Xu and Liu, Yingfan},
  title = {Graph Based K-Nearest Neighbor Search Revisited},
  journal = {ACM Transactions on Database Systems},
  year = {2025},
  volume = {50},
  number = {4},
  pages = {1--30},
  doi = {10.1145/3736716}
}
Kostenlos starten →