Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
From MaRDI portal
Publication:4507359
DOI10.1137/S0097539798347177zbMath0963.68078OpenAlexW2088101210MaRDI QIDQ4507359
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani
Publication date: 18 October 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539798347177
Related Items (34)
Sketching and Embedding are Equivalent for Norms ⋮ Binary vectors for fast distance and similarity estimation ⋮ Random-walk based approximate \(k\)-nearest neighbors algorithm for diffusion state distance ⋮ A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs ⋮ A strong lower bound for approximate nearest neighbor searching ⋮ Is the \(k\)-NN classifier in high dimensions affected by the curse of dimensionality? ⋮ The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite ⋮ Exploiting pseudo-locality of interchange distance ⋮ A Gaussian small deviation inequality for convex functions ⋮ Optimal (Euclidean) Metric Compression ⋮ Efficient clustering on Riemannian manifolds: a kernelised random projection approach ⋮ Longest common substring with approximately \(k\) mismatches ⋮ On approximate near-neighbors search under the (continuous) Fréchet distance in higher dimensions ⋮ Nearly optimal property preserving hashing ⋮ Database-friendly random projections: Johnson-Lindenstrauss with binary coins. ⋮ Unnamed Item ⋮ Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions ⋮ Unnamed Item ⋮ Indexability, concentration, and VC theory ⋮ Unnamed Item ⋮ Approximate range searching in higher dimension ⋮ One-Sided Error Communication Complexity of Gap Hamming Distance. ⋮ Comparison of Metric Spectral Gaps ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Dimension reduction by random hyperplane tessellations ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Cell-probe lower bounds for the partial match problem ⋮ Index structures for fast similarity search for symbol strings ⋮ The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics ⋮ Two Party Distribution Testing: Communication and Security ⋮ Fast dimension reduction using Rademacher series on dual BCH codes ⋮ Computing (and Life) Is All about Tradeoffs
This page was built for publication: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
