Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 1-27 |
Number of pages | 27 |
Journal | Proceedings of the ACM on Management of Data |
Volume | 1 |
Issue number | 1 |
DOIs | |
Publication status | Published - 30 May 2023 |
Event | ACM SIGMOD International Conference on Management of Data, SIGMOD/PODS 2023 - Seattle, United States Duration: 18 Jun 2023 → 23 Jun 2023 https://2023.sigmod.org/ https://dl.acm.org/doi/proceedings/10.1145/3555041 |