Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases
Proceedings of the ACM on Management of Data · 26.05.2023 · 1 (1) · 1-27
DOI: 10.1145/3588908 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2023. Verfasst von Yun Peng und 4 weiteren Autor:innen. Die Arbeit wurde bisher 87-mal zitiert (Crossref) und nennt 60 Literaturangaben. Gefördert von: Hong Kong RGC, NSF of Hunan Province, NSF of Guangdong Province.
Abstract (Originalsprache)
Approximate nearest neighbor (ANN) search is a fundamental search in multi-dimensional databases, which has numerous real-world applications, such as image retrieval, recommendation, entity resolution, and sequence matching. Proximity graph (PG) has been the state-of-the-art index for ANN search. However, the search on existing PGs either suffers from a high time complexity or has no performance guarantee on the search result. In this paper, we propose a novel τ-monotonic graph (τ- MG) to address the limitations. The novelty of τ-MG lies in a τ-monotonic property. Based on this property, we prove that if the distance between a query q and its nearest neighbor is less than a constant τ, the search on τ-MG guarantees to find the exact nearest neighbor of q and the time complexity of the search is smaller than all existing PG-based methods. For index construction efficiency, we propose an approximate variant of τ-MG, namely τ-monotonic neighborhood graph (τ- MNG), which only requires the neighborhood of each node to be τ-monotonic. We further propose an optimization to reduce the number of distance computations in search. Our extensive experiments show that our techniques outperform all existing methods on well-known real-world datasets.
Förderung
- Hong Kong RGC
- NSF of Hunan Province
- NSF of Guangdong Province
- NSFC
Zitieren
APA
Peng, Y., Choi, B., Chan, T. N., Yang, J., & Xu, J. (2023). Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proceedings of the ACM on Management of Data, 1(1), 1-27. https://doi.org/10.1145/3588908
Vancouver
Peng Y, Choi B, Chan TN, Yang J, Xu J. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proceedings of the ACM on Management of Data. 2023;1(1):1-27. doi:10.1145/3588908
BibTeX
@article{Peng2023,
author = {Peng, Yun and Choi, Byron and Chan, Tsz Nam and Yang, Jianye and Xu, Jianliang},
title = {Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {1},
pages = {1--27},
doi = {10.1145/3588908}
}
EUVIMED