EUVIMEDEUVIMED entdecken
Crossref

Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces

Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, Xiaofang Zhou

Proceedings of the VLDB Endowment · 2023-04 · 16 (8) · 1979-1991

DOI: 10.14778/3594512.3594527 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 22.06.2023. Verfasst von Xi Zhao und 4 weiteren Autor:innen. Die Arbeit wurde bisher 102-mal zitiert (Crossref) und nennt 47 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The approximate nearest neighbor (ANN) search in high-dimensional spaces is a fundamental but computationally very expensive problem. Many methods have been designed for solving the ANN problem, such as LSH-based methods and graph-based methods. The LSH-based methods can be costly to reach high query quality due to the hash-boundary issues, while the graph-based methods can achieve better query performance by greedy expansion in an approximate proximity graph (APG). However, the construction cost of these APGs can be one or two orders of magnitude higher than that for building hash-based indexes. In addition, they fail short in incrementally maintaining APGs as the underlying dataset evolves. In this paper, we propose a novel approach named LSH-APG to build APGs and facilitate fast ANN search using a lightweight LSH framework. LSH-APG builds an APG via consecutively inserting points based on their nearest neighbor relationship with an efficient and accurate LSH-based search strategy. A high-quality entry point selection technique and an LSH-based pruning condition are developed to accelerate index construction and query processing by reducing the number of points to be accessed during the search. LSH-APG supports fast maintenance of APGs in lieu of building them from scratch as dataset evolves. Its maintenance cost and query cost for a point is proven to be less affected by dataset cardinality. Extensive experiments on real-world and synthetic datasets demonstrate that LSH-APG incurs significantly less construction cost but achieves better query performance than existing graph-based methods.

Zitieren

APA

Zhao, X., Tian, Y., Huang, K., Zheng, B., & Zhou, X. (2023). Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces. Proceedings of the VLDB Endowment, 16(8), 1979-1991. https://doi.org/10.14778/3594512.3594527

Vancouver

Zhao X, Tian Y, Huang K, Zheng B, Zhou X. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces. Proceedings of the VLDB Endowment. 2023;16(8):1979-1991. doi:10.14778/3594512.3594527

BibTeX
@article{Zhao2023,
  author = {Zhao, Xi and Tian, Yao and Huang, Kai and Zheng, Bolong and Zhou, Xiaofang},
  title = {Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces},
  journal = {Proceedings of the VLDB Endowment},
  year = {2023},
  volume = {16},
  number = {8},
  pages = {1979--1991},
  doi = {10.14778/3594512.3594527}
}
Kostenlos starten →