Approximate Near Neighbors For General Symmetric Norms

Abstract

We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every \(n\), \(d = n^\{o(1)\}\), and every \(d\)-dimensional symmetric norm \(\|\cdot\|\), there exists a data structure for \(\mathrm\{poly\}(log log n)\)-approximate nearest neighbor search over \(\|\cdot\|\) for \(n\)-point datasets achieving \(n^\{o(1)\}\) query time and \(n^\{1+o(1)\}\) space. The main technical ingredient of the algorithm is a low-distortion embedding of a symmetric norm into a low-dimensional iterated product of top-\(k\) norms. We also show that our techniques cannot be extended to general norms.

Stats

• citations12
• S2 citations—
• github stars0
• HF likes0
• heat score8.35
• arxiv keyandoni2016approximate

Related papers

• Optimal Hashing-based Time-space Trade-offs For Approximate Near Neighbors (2016)11.29
• Approximate Nearest Neighbors Search Without False Negatives For \(l_2\) For \(c>\sqrt{\log\log{n}}\) (2017)0.00
• Sublinear Data Structures For Nearest Neighbor In Ultra High Dimensions (2025)0.00
• Worst-case Performance Of Popular Approximate Nearest Neighbor Search Implementations: Guarantees And Limitations (2023)5.84
• Optimal Las Vegas Locality Sensitive Data Structures (2017)6.77
• SVD Provably Denoises Nearest Neighbor Data (2026)0.00
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
• Learning Space Partitions For Nearest Neighbor Search (2019)0.00