Approximate Nearest Neighbors Search Without False Negatives For \(l_2\) For \(c>\sqrt{\log\log{n}}\)

Abstract

In this paper, we report progress on answering the open problem presented by Pagh~[14], who considered the nearest neighbor search without false negatives for the Hamming distance. We show new data structures for solving the \(c\)-approximate nearest neighbors problem without false negatives for Euclidean high dimensional space \(\mathcal\{R\}^d\). These data structures work for any \(c = \omega(\sqrt\{log\{log\{n\}\}\})\), where \(n\) is the number of points in the input set, with poly-logarithmic query time and polynomial preprocessing time. This improves over the known algorithms, which require \(c\) to be \(Ω(\sqrt\{d\})\). This improvement is obtained by applying a sequence of reductions, which are interesting on their own. First, we reduce the problem to \(d\) instances of dimension logarithmic in \(n\). Next, these instances are reduced to a number of \(c\)-approximate nearest neighbor search instances in \(\big(\mathbb\{R\}^k\big)^L\) space equipped with metric \(m(x,y) = \ma

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keysankowski2017approximate

Related papers

• Optimal Las Vegas Locality Sensitive Data Structures (2017)6.77
• Optimal Hashing-based Time-space Trade-offs For Approximate Near Neighbors (2016)11.29
• Approximate Near Neighbors For General Symmetric Norms (2016)8.35
• Sublinear Data Structures For Nearest Neighbor In Ultra High Dimensions (2025)0.00
• Efficient Approximate Nearest Neighbor Search For Multiple Weighted \(l_{p\leq2}\) Distance Functions (2020)0.00
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44