Show simple item record

dc.contributor.authorDasgupta, Sanjoy
dc.contributor.authorSinha, Kaushik
dc.identifier.citationDasgupta, Sanjoy; Sinha, Kaushik. Dasgupta, Sanjoy; Sinha, Kaushik. 2015. Randomized partition trees for nearest neighbor search. Algorithmica, May 2015:vol. 72:no. 1:pp 237-263en_US
dc.descriptionClick on the DOI link to access the article (may not be free).en_US
dc.description.abstractThe -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.en_US
dc.description.sponsorshipNational Science Foundation for support under grant IIS-1162581.en_US
dc.publisherSpringer International Publishing AGen_US
dc.subjectNearest neighboren_US
dc.subjectIntrinsic dimensionen_US
dc.subjectSpatial partitionen_US
dc.subjectK-d treeen_US
dc.subjectRandom projectionen_US
dc.titleRandomized partition trees for nearest neighbor searchen_US
dc.rights.holderCopyright Springer 2015

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record