A Heterogeneous High-Dimensional Approximate Nearest Neighbor Algorithm
From MaRDI portal
Publication:2989754
DOI10.1109/TIT.2012.2204169zbMATH Open1364.62150arXiv0810.4188OpenAlexW1503158680MaRDI QIDQ2989754FDOQ2989754
Authors: Moshe Dubiner 
Publication date: 8 June 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: We consider the problem of finding high dimensional approximate nearest neighbors. Suppose there are d independent rare features, each having its own independent statistics. A point x will have x_{i}=0 denote the absence of feature i, and x_{i}=1 its existence. Sparsity means that usually x_{i}=0. Distance between points is a variant of the Hamming distance. Dimensional reduction converts the sparse heterogeneous problem into a lower dimensional full homogeneous problem. However we will see that the converted problem can be much harder to solve than the original problem. Instead we suggest a direct approach. It consists of T tries. In try t we rearrange the coordinates in decreasing order of (1-r_{t,i})frac{p_{i,11}}{p_{i,01}+p_{i,10}} lnfrac{1}{p_{i,1*}} where 0<r_{t,i}<1 are uniform pseudo-random numbers, and the p's are the coordinate's statistical parameters. The points are lexicographically ordered, and each is compared to its neighbors in that order. We analyze a generalization of this algorithm, show that it is optimal in some class of algorithms, and estimate the necessary number of tries to success. It is governed by an information like function, which we call bucketing forest information. Any doubts whether it is "information" are dispelled by another paper, where unrestricted bucketing information is defined.
Full work available at URL: https://arxiv.org/abs/0810.4188
Recommendations
- Approximate nearest neighbor search in high dimensions
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- scientific article; zbMATH DE number 1775451
- Exploiting lower bounds to accelerate approximate nearest neighbor search on high-dimensional data
- Approximate nearest neighbor: towards removing the curse of dimensionality
- Low-quality dimension reduction and high-dimensional approximate nearest neighbor
Cited In (1)
This page was built for publication: A Heterogeneous High-Dimensional Approximate Nearest Neighbor Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989754)
