Randomized partition trees for nearest neighbor search
Dasgupta, Sanjoy Sinha, Kaushik
Dasgupta, Sanjoy
Sinha, Kaushik
Citations
Altmetric:
Authors
Other Names
Location
Time Period
Advisors
Original Date
Digitization Date
Issue Date
2015-05
Type
Article
Genre
Keywords
Nearest neighbor,Intrinsic dimension,Spatial partition,K-d tree,Random projection
Subjects (LCSH)
Citation
Dasgupta, Sanjoy; Sinha, Kaushik. Dasgupta, Sanjoy; Sinha, Kaushik. 2015. Randomized partition trees for nearest neighbor search. Algorithmica, May 2015:vol. 72:no. 1:pp 237-263
Abstract
The -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 several situations of interest: when the data are drawn from a doubling measure; when the data and query distributions are identical and are supported on a set of bounded doubling dimension; and when the data are documents from a topic model.
Table of Contents
Description
Click on the DOI link to access the article (may not be free).
Publisher
Springer International Publishing AG
Journal
Book Title
Series
Algorithmica;v.72:no.1
Digital Collection
Finding Aid URL
Use and Reproduction
Archival Collection
PubMed ID
DOI
ISSN
0178-4617