Faster Cover Trees (2015)
The cover tree data structure speeds up exact nearest neighbor queries over arbitrary metric spaces [Beygelzimer et al. 2006]. This paper makes cover trees even faster. In particular, we provide
- A simpler definition of the cover tree that reduces the number of nodes from O(n) to exactly n,
- An additional invariant that makes queries faster in practice,
- Algorithms for constructing and querying the tree in parallel on multiprocessor systems, and
- A more cache efficient memory layout.
On standard benchmark datasets, we reduce the number of distance computations by 10-50%. On a large-scale bioinformatics dataset, we reduce the number of distance computations by 71%. On a large-scale image dataset, our parallel algorithm with 16 cores reduces tree construction time from 3.5 hours to 12 minutes.
|Mike Izbicki and Christian R. Shelton (2015). "Faster Cover Trees." Proceedings of the Thirty-Second International Conference on Machine Learning.
author = "Mike Izbicki and Christian R. Shelton",
title = "Faster Cover Trees",
booktitle = "Proceedings of the Thirty-Second International Conference on Machine Learning",
booktitleabbr = "ICML",
year = 2015,