Randomized Embeddings with Slack and High-Dimensional Approximate Nearest Neighbor

DOI10.1145/3178540zbMath1454.68037arXiv1412.1683OpenAlexW2963710502MaRDI QIDQ4554345

Ioannis Z. Emiris, Ioannis Psarros, Evangelos Anagnostopoulos

Publication date: 13 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

curse of dimensionalitydoubling dimensionexperimental studyJohnson-Lindenstrauss lemmaapproximate nearest neighborrandomized embeddings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20)

Related Items

Equivalent realisations of a rigid graph ⋮ Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1 ⋮ Unnamed Item ⋮ Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)

Uses Software

• FALCONN