[mlpack-svn] [MLPACK] #243: Dual cover tree traverser is quite slow

MLPACK Trac trac at coffeetalk-1.cc.gatech.edu
Wed Aug 15 18:53:29 EDT 2012


#243: Dual cover tree traverser is quite slow
---------------------+------------------------------------------------------
 Reporter:  rcurtin  |        Owner:                                               
     Type:  defect   |       Status:  new                                          
 Priority:  major    |    Milestone:  mlpack 1.0.3                                 
Component:  mlpack   |     Keywords:  cover tree, dualtreetraverser, neighborsearch
 Blocking:           |   Blocked By:                                               
---------------------+------------------------------------------------------
 Using current sources (r13421), CoverTree<>::DualTreeTraverser performs
 particularly slow searches.  For example, running (and then profiling)
 allknn with query and reference sets equal to 50k points out of the
 covtype dataset (covtype_r-50k.csv), here are the number of base case
 computations:

  * jl's implementation: 22.5M
  * mlpack, single kd-tree: 9.1M
  * mlpack, dual kd-tree: 8.9M
  * mlpack, single cover tree: 37.9M
  * mlpack, dual cover tree: 411M

 So the problem is fairly clear.  When getting numbers for this, one must
 be careful to compile disabling inlining if using profiles to get the
 numbers (-fno-inline).

-- 
Ticket URL: <https://trac.research.cc.gatech.edu/fastlab/ticket/243>
MLPACK <www.fast-lab.org>
MLPACK is an intuitive, fast, and scalable C++ machine learning library developed by the FASTLAB at Georgia Tech under Dr. Alex Gray.


More information about the mlpack-svn mailing list