Revisiting kd-tree for nearest neighbor search

No Thumbnail Available
Authors
Ram, Parikshit
Sinha, Kaushik
Issue Date
2019
Type
Conference paper
Language
en_US
Keywords
Nearest-neighbor search , Randomized algorithms , Similarity search , Space-partitioning trees
Research Projects
Organizational Units
Journal Issue
Alternative Title
Abstract

kd-tree [16] has long been deemed unsuitable for exact nearest-neighbor search in high dimensional data. The theoretical guarantees and the empirical performance of kd-tree do not show significant improvements over brute-force nearest-neighbor search in moderate to high dimensions. kd-tree has been used relatively more successfully for approximate search [36] but lack theoretical guarantees. In the article, we build upon randomized-partition trees [14] to propose kd-tree based approximate search schemes with O(d log d + log n) query time for data sets with n points in d dimensions and rigorous theoretical guarantees on the search accuracy. We empirically validate the search accuracy and the query time guarantees of our proposed schemes, demonstrating the significantly improved scaling for same level of accuracy.

Description
Click on the DOI link to access the article (may not be free).
Citation
Ram, Parikshit; Sinha, Kaushik. 2019. Revisiting kd-tree for nearest neighbor search. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 25 July 2019, Pages 1378-1388
Publisher
Association for Computing Machinery
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
EISSN