Randomized partition trees for nearest neighbor search

DOI10.1007/S00453-014-9885-5MaRDI QIDQ2345949zbMATH OpenOpenAlexFDO

Authors Sanjoy Dasgupta, Kaushik Sinha

Publication date 21 May 2015

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-d treeintrinsic dimensionnearest neighborrandom projectionspatial partition

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: The k-d tree was one of the first spatial data structures proposed for nearest neighbor search. Its efficacy is diminished in high-dimensional spaces, but several variants, with randomization and overlapping cells, have proved to be successful in practice. We analyze three such schemes. We show that the probability that they fail to find the nearest neighbor, for any data set and any query point, is directly related to a simple potential function that captures the difficulty of the point configuration. We then bound this potential function in two situations of interest: the first, when data come from a doubling measure, and the second, when the data are documents from a topic model.

Recommendations

• An Improved Algorithm Finding Nearest Neighbor Using Kd-trees
• scientific article; zbMATH DE number 1893569
• Simple and fast nearest neighbor search
• Analysis of range search for random \(k-d\) trees
• Refinements to nearest-neighbor searching in k-dimensional trees

Cites work

• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Consistent nonparametric regression. Discussion
• Finding nearest neighbors in growth-restricted metrics
• scientific article; zbMATH DE number 1559575 (Why is no real title available?)
• scientific article; zbMATH DE number 1830741 (Why is no real title available?)
• scientific article; zbMATH DE number 5485566 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• Learning multi-modal similarity
• Multidimensional binary search trees used for associative searching
• Nearest neighbor queries in metric spaces
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Randomized partition trees for nearest neighbor search
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors

Cited in

(8)

• Improved maximum inner product search with better theoretical guarantee using randomized partition trees
• Random projection-based auxiliary information can improve tree-based nearest neighbor search
• Randomized partition trees for nearest neighbor search
• Randomly-oriented k-d trees adapt to intrinsic dimension
• Analysis of range search for random \(k-d\) trees
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• Index structures for fast similarity search for real vectors. II
• Refinements to nearest-neighbor searching in k-dimensional trees

This page was built for publication: Randomized partition trees for nearest neighbor search

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