Randomized embeddings with slack and high-dimensional approximate nearest neighbor

DOI10.1145/3178540MaRDI QIDQ4554345zbMATH OpenOpenAlexFDO

Authors Evangelos Anagnostopoulos, Ioannis Z. Emiris, Ioannis Psarros

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

approximate nearest neighborcurse of dimensionalitydoubling dimensionexperimental studyJohnson-Lindenstrauss lemmarandomized embeddings

Mathematics Subject Classification ID

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

Abstract: The approximate nearest neighbor problem ($epsilon$-ANN) in high dimensional Euclidean space has been mainly addressed by Locality Sensitive Hashing (LSH), which has polynomial dependence in the dimension, sublinear query time, but subquadratic space requirement. In this paper, we introduce a new definition of "low-quality" embeddings for metric spaces. It requires that, for some query point $q$, there exists an approximate nearest neighbor among the pre-images of the $k>1$ approximate nearest neighbors in the target space. Focusing on Euclidean spaces, we employ random projections in order to reduce the original problem to one in a space of dimension inversely proportional to $k$. The $k$ approximate nearest neighbors can be efficiently retrieved by a data structure such as BBD-trees. The same approach is applied to the problem of computing an approximate near neighbor, where we obtain a data structure requiring linear space, and query time in $O(d{n}^{ho})$, for $hoapprox1-epsilo{n}^2/log(1/epsilon)$. This directly implies a solution for $epsilon$-ANN, while achieving a better exponent in the query time than the method based on BBD-trees. Better bounds are obtained in the case of doubling subsets of $el{l}_2$, by combining our method with $r$-nets. We implement our method in C++, and present experimental results in dimension up to $500$ and $10^6$ points, which show that performance is better than predicted by the analysis. In addition, we compare our ANN approach to E2LSH, which implements LSH, and we show that the theoretical advantages of each method are reflected on their actual performance.

Recommendations

• Low-quality dimension reduction and high-dimensional approximate nearest neighbor
• Approximate nearest neighbor search for low-dimensional queries
• scientific article; zbMATH DE number 437552
• Approximate k-flat nearest neighbor search
• scientific article; zbMATH DE number 1775450

Cited in

(7)

• Equivalent realisations of a rigid graph
• Near-neighbor preserving dimension reduction via coverings for doubling subsets of _1
• Exploiting lower bounds to accelerate approximate nearest neighbor search on high-dimensional data
• scientific article; zbMATH DE number 7236441 (Why is no real title available?)
• Low-quality dimension reduction and high-dimensional approximate nearest neighbor
• Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1
• Moderate dimension reduction for k-center clustering

Describes a project that uses

Uses Software

• FALCONN

This page was built for publication: Randomized embeddings with slack and high-dimensional approximate nearest neighbor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554345)