UCR

Computer Science and Engineering



Christian R. Shelton, Professor

Faster Cover Trees (2015)

by Mike Izbicki and Christian R. Shelton


Abstract: 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
  1. A simpler definition of the cover tree that reduces the number of nodes from O(n) to exactly n,
  2. An additional invariant that makes queries faster in practice,
  3. Algorithms for constructing and querying the tree in parallel on multiprocessor systems, and
  4. 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.

Download Information

Mike Izbicki and Christian R. Shelton (2015). "Faster Cover Trees." Proceedings of the Thirty-Second International Conference on Machine Learning. pdf          

Bibtex citation

@inproceedings{IzbShe15,
   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,
}

More Information

Address

University of California, Riverside
Chung Hall, room 327
Riverside, CA 92521
Tel: (951) 827-2554
E-mail: cshelton@cs.ucr.edu

 


Other Links