Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings

DOI10.1016/J.TCS.2018.07.011zbMath1410.68104arXiv1512.01775OpenAlexW2605369795MaRDI QIDQ1711830

Yair Bartal, Lee-Ad J. Gottlieb

Publication date: 18 January 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.01775

zbMATH Keywords

nearest neighbor search\(\ell_p\) spaces

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (3)

Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Isometric embedding in \(\ell_ p\)-spaces
• Embedding \(l_ p^ m\) into \(l_ 1^ n\)
• Approximate closest-point queries in high dimensions
• Approximate nearest neighbor queries revisited
• On Lipschitz extension from finite subsets
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Searching dynamic point sets in spaces with bounded doubling dimension
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Extensions of Lipschitz mappings into a Hilbert space
• Nearest-neighbor-preserving embeddings
• Oblivious string embeddings and edit distance approximations
• A Randomized Algorithm for Closest-Point Queries
• Comparison of Metric Spectral Gaps
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Approximating Minimization Diagrams and Generalized Proximity Search

This page was built for publication: Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings