Randomized partition trees for exact nearest neighbor search

By Sanjoy Dasgupta, Kaushik Sinha. 2013

86 citations recorded by the source corpus.

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.

Subfields: Geography, Planning and Development, Ocean Engineering, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geography, Planning and Development

In Ocean Engineering

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering (2019, methodology): “…using SGTree (Zaheer et al., 2019) which has been shown to perform better than other exact k-NN strategies such as Cover Tree (Beygelz-imer et al., 2006), P-DCI (Li & Malik, 2017) and other approximate NN search techniques such as RP-Tree (Dasgupta & Sinha, 2013), HNSW (Malkov & Yashunin, 2018).”
Randomized Partition Trees for Nearest Neighbor Search (2015, background): “A preliminary abstract of this work appeared in [11].”