Randomized partition trees for nearest neighbor search

No Thumbnail Available
Issue Date
2015-05
Authors
Dasgupta, Sanjoy
Sinha, Kaushik
Advisor
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 Content
Description
Click on the DOI link to access the article (may not be free).
publication.page.dc.relation.uri
DOI