EUVIMEDEUVIMED entdecken
Crossref

Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search

Binhong Li, Xiao Yan, Shangqi Lu

Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-24

DOI: 10.1145/3786650 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Binhong Li und 2 weiteren Autor:innen. Die Arbeit nennt 77 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Approximate nearest neighbor (ANN) search in high-dimensional metric spaces is a fundamental problem with many applications. Over the past decade, proximity graph (PG)-based indexes have demonstrated superior empirical performance over alternatives. However, these methods often lack theoretical guarantees regarding the quality of query results, especially in the worst-case scenarios. In this paper, we introduce the α-convergent graph (α-CG), a new PG structure that employs a new carefully designed edge pruning rule. If the distance between the query point q and its exact nearest neighbor v * is at most τ for some constant τ > 0, our α-CG finds the exact nearest neighbor in poly-logarithmic time, assuming bounded intrinsic dimensionality for the dataset; otherwise, it can find an ANN in the same time. To enhance scalability, we develop the α-convergent neighborhood graph (α-CNG), a practical variant that applies the pruning rule locally within each point's neighbors. We also introduce optimizations to reduce the index construction time. Experimental results show that our α-CNG outperforms existing PGs on real-world datasets. For most datasets, α-CNG can reduce the number of distance computations and search steps by over 15% and 45%, respectively, when compared with the best-performing baseline.

Zitieren

APA

Li, B., Yan, X., & Lu, S. (2026). Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data, 4(1), 1-24. https://doi.org/10.1145/3786650

Vancouver

Li B, Yan X, Lu S. Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data. 2026;4(1):1-24. doi:10.1145/3786650

BibTeX
@article{Li2026,
  author = {Li, Binhong and Yan, Xiao and Lu, Shangqi},
  title = {Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {1},
  pages = {1--24},
  doi = {10.1145/3786650}
}
Kostenlos starten →