New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Dual cover tree traverser is quite slow #235

Closed
rcurtin opened this Issue Dec 29, 2014 · 12 comments

Comments

Projects
None yet
2 participants
@rcurtin
Member

rcurtin commented Dec 29, 2014

Reported by rcurtin on 25 Oct 42625579 22:12 UTC
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).

@rcurtin rcurtin self-assigned this Dec 29, 2014

@rcurtin rcurtin added this to the mlpack 1.0.9 milestone Dec 29, 2014

@rcurtin rcurtin closed this Dec 29, 2014

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 15 Jun 42899215 14:50 UTC
For a simpler test case (reference = test_data_3_1000.csv, query = test_data_3_1000.csv), with k = 5, here are the number of base case computations:

  • mlpack, naive: 1000000
  • mlpack, single kd-tree: 49888
  • mlpack, dual kd-tree: 50442
  • mlpack, single cover tree: 127838
  • mlpack, dual cover tree: 189628
  • jl, dual cover tree: 83962

Also some other information:

  • jl, dual cover tree construction: 91600
  • mlpack, dual cover tree construction: 14290

Those numbers are the distance evaluations for both tree constructions (so, half that for the per-dataset cover tree construction evaluations).

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 15 Jun 42899215 14:50 UTC
For a simpler test case (reference = test_data_3_1000.csv, query = test_data_3_1000.csv), with k = 5, here are the number of base case computations:

  • mlpack, naive: 1000000
  • mlpack, single kd-tree: 49888
  • mlpack, dual kd-tree: 50442
  • mlpack, single cover tree: 127838
  • mlpack, dual cover tree: 189628
  • jl, dual cover tree: 83962

Also some other information:

  • jl, dual cover tree construction: 91600
  • mlpack, dual cover tree construction: 14290

Those numbers are the distance evaluations for both tree constructions (so, half that for the per-dataset cover tree construction evaluations).

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 29 Jun 42899840 07:39 UTC
Using a jl-code constructed cover tree on test_data_3_1000.csv and k = 5, as before, we get these numbers for the number of distance evaluations in the dual tree traversal:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 247537
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 189628 (as before)
  • jl-constructed cover tree, mlpack single-tree traversal: 136398
  • mlpack-constructed cover tree, mlpack single-tree traversal: 127838 (as before)

Therefore the issue is not with the actual way we are creating cover trees, but instead we know that the bug must be in the actual dual-tree traversal. The jl-to-mlpack cover tree converter is in contrib/rcurtin/jl-to-mlpack_cover_tree/ for posterity.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 29 Jun 42899840 07:39 UTC
Using a jl-code constructed cover tree on test_data_3_1000.csv and k = 5, as before, we get these numbers for the number of distance evaluations in the dual tree traversal:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 247537
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 189628 (as before)
  • jl-constructed cover tree, mlpack single-tree traversal: 136398
  • mlpack-constructed cover tree, mlpack single-tree traversal: 127838 (as before)

Therefore the issue is not with the actual way we are creating cover trees, but instead we know that the bug must be in the actual dual-tree traversal. The jl-to-mlpack cover tree converter is in contrib/rcurtin/jl-to-mlpack_cover_tree/ for posterity.

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 14 Jan 42915951 10:48 UTC
With some changes to how the bound is propagated in r13955 through r13959, the following numbers are produced:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 98201 (used to be 247537)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 112039 (used to be 189628)

We have some improvement, but I believe jl's implementation makes a few more opportunistic prunes than our implementation currently does. So this isn't quite done yet.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 14 Jan 42915951 10:48 UTC
With some changes to how the bound is propagated in r13955 through r13959, the following numbers are produced:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 98201 (used to be 247537)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 112039 (used to be 189628)

We have some improvement, but I believe jl's implementation makes a few more opportunistic prunes than our implementation currently does. So this isn't quite done yet.

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 14 Jul 42925871 04:14 UTC
This is the prune which is not being done by our tree:

inline bool shell(float parent_query_dist, float child_parent_dist, float upper_bound)
{
  return parent_query_dist - child_parent_dist <= upper_bound;
  //    && child_parent_dist - parent_query_dist <= upper_bound;
}

It is called when descending the reference cover set. The bound can prune without evaluating the base case of a child.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 14 Jul 42925871 04:14 UTC
This is the prune which is not being done by our tree:

inline bool shell(float parent_query_dist, float child_parent_dist, float upper_bound)
{
  return parent_query_dist - child_parent_dist <= upper_bound;
  //    && child_parent_dist - parent_query_dist <= upper_bound;
}

It is called when descending the reference cover set. The bound can prune without evaluating the base case of a child.

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 4 Mar 42929546 20:06 UTC
Things are getting better with r13976:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 91626 (used to be 98201)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 111024 (used to be 112039)

The jl-constructed cover tree must have some interesting properties then. I believe there is still one prune with shell() that we are not getting.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 4 Mar 42929546 20:06 UTC
Things are getting better with r13976:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 91626 (used to be 98201)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 111024 (used to be 112039)

The jl-constructed cover tree must have some interesting properties then. I believe there is still one prune with shell() that we are not getting.

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 19 Nov 42931369 14:32 UTC
Some more improvements:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 77506 (used to be 98201)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 107544 (used to be 111024)

So we are now outperforming jl's implementation with his tree, but not with the mlpack-constructed tree. Fortunately I still have one more trick up my sleeve. The latest (somewhat hackish) improvements are committed in r13979.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 19 Nov 42931369 14:32 UTC
Some more improvements:

  • jl-constructed cover tree, jl dual-tree traversal: 83962 (as before)
  • jl-constructed cover tree, mlpack dual-tree traversal: 77506 (used to be 98201)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 107544 (used to be 111024)

So we are now outperforming jl's implementation with his tree, but not with the mlpack-constructed tree. Fortunately I still have one more trick up my sleeve. The latest (somewhat hackish) improvements are committed in r13979.

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 25 Oct 43028289 09:30 UTC
There were some errors I introduced with my modification (#264), so now with those fixed we are at:

  • jl-constructed cover tree, jl dual-tree traversal: 83962
  • jl-constructed cover tree, mlpack dual-tree traversal: 111225 (originally 247537)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 132341 (originally 189628)

This is not doing parent-child prunes, so I need to reimplement that now (safely).

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 25 Oct 43028289 09:30 UTC
There were some errors I introduced with my modification (#264), so now with those fixed we are at:

  • jl-constructed cover tree, jl dual-tree traversal: 83962
  • jl-constructed cover tree, mlpack dual-tree traversal: 111225 (originally 247537)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 132341 (originally 189628)

This is not doing parent-child prunes, so I need to reimplement that now (safely).

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 24 Oct 43044072 17:43 UTC
r14120 makes the bound a little tighter, giving

  • jl-constructed cover tree, jl dual-tree traversal: 83962
  • jl-constructed cover tree, mlpack dual-tree traversal: 98201 (was 111225)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 112039 (was 189628)

The parent-child prune has not been implemented safely yet.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 24 Oct 43044072 17:43 UTC
r14120 makes the bound a little tighter, giving

  • jl-constructed cover tree, jl dual-tree traversal: 83962
  • jl-constructed cover tree, mlpack dual-tree traversal: 98201 (was 111225)
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 112039 (was 189628)

The parent-child prune has not been implemented safely yet.

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 11 Jul 43761046 14:04 UTC
Realistically at this point, the CalculateBound() function probably needs to be rethought, with some assumptions on how cover trees and kd-trees are traversed. Moving to 1.0.8...

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 11 Jul 43761046 14:04 UTC
Realistically at this point, the CalculateBound() function probably needs to be rethought, with some assumptions on how cover trees and kd-trees are traversed. Moving to 1.0.8...

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 12 Jan 44029419 04:13 UTC
After some very time-consuming debugging, I discovered an invalid prune in the jl dual-tree traversal. Thus, we now have

  • jl-constructed cover tree, jl dual-tree traversal: 86818

Note that this is done with a base of 2.0.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 12 Jan 44029419 04:13 UTC
After some very time-consuming debugging, I discovered an invalid prune in the jl dual-tree traversal. Thus, we now have

  • jl-constructed cover tree, jl dual-tree traversal: 86818

Note that this is done with a base of 2.0.

@rcurtin

This comment has been minimized.

Show comment
Hide comment
@rcurtin

rcurtin Dec 30, 2014

Member

Commented by rcurtin on 15 Aug 44113956 00:40 UTC
Using the new TraversalInfo concept committed in r16217 through r16230, the child-parent prunes are now possible and the results are now (on test_data_3_1000.csv):

  • jl-constructed cover tree, jl dual-tree traversal: 86818
  • jl-constructed cover tree, mlpack dual-tree traversal: 86524
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 107561

And runtime results for the same dataset:

  • jl-constructed cover tree, jl dual-tree traversal: 0.021s
  • jl-constructed cover tree, mlpack dual-tree traversal: 0.091s
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 0.036s

Then, on a larger dataset, the corel dataset (32x37748) (one duplicate point had to be removed):

  • jl-constructed cover tree, jl dual-tree traversal: 157 792 508
  • jl-constructed cover tree, mlpack dual-tree traversal: 124 067 723
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 146 564 813

And runtimes:

  • jl-constructed cover tree, jl dual-tree traversal: 18.679s
  • jl-constructed cover tree, mlpack dual-tree traversal: 247.655s
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 75.117s

I am not sure the runtime numbers for the jl-constructed cover tree and mlpack dual-tree traversal are reasonable, because the tree needs to be reformatted and this is done inefficiently. Additional slowdown is probably present because the bound calculation (NeighborSearchRules::CalculateBound()) is slow to calculate and should be improved. But that is outside the scope of this ticket because this ticket is only about the traversal, so I can (finally) mark this resolved.

Member

rcurtin commented Dec 30, 2014

Commented by rcurtin on 15 Aug 44113956 00:40 UTC
Using the new TraversalInfo concept committed in r16217 through r16230, the child-parent prunes are now possible and the results are now (on test_data_3_1000.csv):

  • jl-constructed cover tree, jl dual-tree traversal: 86818
  • jl-constructed cover tree, mlpack dual-tree traversal: 86524
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 107561

And runtime results for the same dataset:

  • jl-constructed cover tree, jl dual-tree traversal: 0.021s
  • jl-constructed cover tree, mlpack dual-tree traversal: 0.091s
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 0.036s

Then, on a larger dataset, the corel dataset (32x37748) (one duplicate point had to be removed):

  • jl-constructed cover tree, jl dual-tree traversal: 157 792 508
  • jl-constructed cover tree, mlpack dual-tree traversal: 124 067 723
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 146 564 813

And runtimes:

  • jl-constructed cover tree, jl dual-tree traversal: 18.679s
  • jl-constructed cover tree, mlpack dual-tree traversal: 247.655s
  • mlpack-constructed cover tree, mlpack dual-tree traversal: 75.117s

I am not sure the runtime numbers for the jl-constructed cover tree and mlpack dual-tree traversal are reasonable, because the tree needs to be reformatted and this is done inefficiently. Additional slowdown is probably present because the bound calculation (NeighborSearchRules::CalculateBound()) is slow to calculate and should be improved. But that is outside the scope of this ticket because this ticket is only about the traversal, so I can (finally) mark this resolved.

@stinger0962

This comment has been minimized.

Show comment
Hide comment
@stinger0962

stinger0962 Sep 15, 2017

Great working process. Now we are facing the same issue as you once had. Our team is trying to figure out why MLPack's kd-tree is superior than ours.

stinger0962 commented Sep 15, 2017

Great working process. Now we are facing the same issue as you once had. Our team is trying to figure out why MLPack's kd-tree is superior than ours.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment