Show simple item record

dc.contributor.authorRam, Parikshit
dc.contributor.authorSinha, Kaushik
dc.identifier.citationRam, 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-1388en_US
dc.descriptionClick on the DOI link to access the article (may not be free).en_US
dc.description.abstractkd-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.en_US
dc.publisherAssociation for Computing Machineryen_US
dc.relation.ispartofseriesACM SIGKDD International Conference on Knowledge Discovery and Data Mining;2019
dc.subjectNearest-neighbor searchen_US
dc.subjectRandomized algorithmsen_US
dc.subjectSimilarity searchen_US
dc.subjectSpace-partitioning treesen_US
dc.titleRevisiting kd-tree for nearest neighbor searchen_US
dc.typeConference paperen_US
dc.rights.holder© 2019 Association for Computing Machineryen_US

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record