Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.47OpenAlexW2977465133MaRDI QIDQ5875504

Ioannis Z. Emiris, Vasilis Margonis, Ioannis Psarros

Publication date: 3 February 2023

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

zbMATH Keywords

Manhattan metricapproximate nearest neighborrandomized embedding

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• On approximate nearest neighbors under \(l_\infty\) norm
• Approximate nearest neighbor search for \(\ell_p\)-spaces \((2<p<\infty)\) via embeddings
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Searching dynamic point sets in spaces with bounded doubling dimension
• Dimension Reduction Techniques for l_p (1<p<2), with Applications
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Nearest-neighbor-preserving embeddings
• Randomized Embeddings with Slack and High-Dimensional Approximate Nearest Neighbor
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
• Approximate near neighbors for general symmetric norms
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Fast construction of nets in low dimensional metrics, and their applications