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

DOI10.1016/j.tcs.2022.11.031OpenAlexW4310497534MaRDI QIDQ2110372

Vasilis Margonis, Ioannis Z. Emiris, Ioannis Psarros

Publication date: 21 December 2022

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.11.031

zbMATH Keywords

dimensionality reductiondoubling dimensionCauchy distributionManhattan metricapproximate nearest neighborrandomized embedding

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• Approximate Greedy Clustering and Distance Selection for Graph Metrics
• 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
• Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1

This page was built for publication: Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)