8000 Fibonacci Heaps for Ball Tree · Issue #597 · scikit-learn/scikit-learn · GitHub
[go: up one dir, main page]
Skip to content

Fibonacci Heaps for Ball Tree #597

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.

Sign up for GitHub

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

Jump to bottom
Closed
jakevdp opened this issue Jan 29, 2012 · 7 comments
Closed

Fibonacci Heaps for Ball Tree #597

jakevdp opened this issue Jan 29, 2012 · 7 comments
Labels
help wanted Moderate Anything that requires some knowledge of conventions and best practices module:tree New Feature

Comments

@jakevdp
Copy link
Member
jakevdp commented Jan 29, 2012

The Ball Tree neighbor search could potentially be sped up greatly (especially for large n_neighbors and n_features) by using Fibonacci heaps instead of the binary heap/priority queue structures used currently. There is a fast cython Fibonacci heap in sklearn/utils/graph_nearest_neighbor.pyx. This should be factored out so that it can also be used in the Ball Tree.
@larsmans
Copy link
Member

Pairing heaps are faster than Fibonacci heaps, take less space, and are easier to implement.

@karane
Copy link
karane commented Aug 8, 2014

@jakevdp @larsmans Is this still an issue?

@jakevdp
Copy link
Member Author
jakevdp commented Aug 8, 2014

It's still a possible enhancement. I wouldn't call it an issue per se, though github's nomenclature is not very flexible on that front... 😄

@karane
Copy link
karane commented Aug 8, 2014

Currently I am working on an issue in metrics.
As soon as I finish that, I'd like to take this one.

I have some experience implementing trees for my masters, I think I can help.

@jnothman jnothman added Moderate Anything that requires some knowledge of conventions and best practices Need Contributor labels Sep 29, 2016
@vyasr vyasr mentioned this issue Jul 15, 2018
Closed
@vyasr
Copy link
vyasr commented Jul 15, 2018

This issue is currently being tackled in Pull Request #11541. @jakevdp did you intend to use this heap in place of the NeighborsHeap or the NodeHeap? Since one of them resizes and one does not (and one appears to be a min heap while the other is a max heap), there's probably some overhead to just replacing, even if the Fibonacci heap was reimplemented to support either min or max heaps.

@rth rth mentioned this issue Jul 19, 2018
Merged
@RiyasatTalukder
Copy link

Is this issue still active? Would it be possible to share more information regarding which files/methods to look at? Thanks!

@jjerphan
Copy link
Member
jjerphan commented Aug 1, 2022

I am closing this issue for the reasons given in #11541 (comment).

@jjerphan jjerphan closed this as completed Aug 1, 2022
@jjerphan jjerphan closed this as not planned Won't fix, can't repro, duplicate, stale Aug 1, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
help wanted Moderate Anything that requires some knowledge of conventions and best practices module:tree New Feature
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
9 participants
@jnothman @larsmans @jakevdp @vyasr @cmarmo @lesteve @karane @jjerphan @RiyasatTalukder
0