Journal
KDD'19: PROCEEDINGS OF THE 25TH ACM SIGKDD INTERNATIONAL CONFERENCCE ON KNOWLEDGE DISCOVERY AND DATA MINING
Volume -, Issue -, Pages 1378-1388Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3292500.3330875
Keywords
nearest-neighbor search; similarity search; randomized algorithms; space-partitioning trees
Ask authors/readers for more resources
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 logd + 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available