Skip to content
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

Implement faster RangeSearch #13

Open
minkezhang opened this issue Aug 7, 2022 · 0 comments
Open

Implement faster RangeSearch #13

minkezhang opened this issue Aug 7, 2022 · 0 comments

Comments

@minkezhang
Copy link
Member

minkezhang commented Aug 7, 2022

RangeSearch implements a recursive model for searching through a bounding box. In order to increase efficiency, RangeSearch runs the left and right recursion calls in parallel via a channel. This recursion becomes expensive as we near the bottom of the tree, and we should instead swap to using a serial execution model instead. However, we do not have a good heuristic as to how much data is left in the subtree to prune -- node.Data() []T only returns the data stored in each individual node and does not reflect child nodes. We will need to implement node.Depth() int or some other heuristic in order to make RangeSearch more efficient.

Overall, this makes RangeSearch of small N (< 10k) fairly slow as compared to the reference http://github.com/kyroy/kdtree implementation. For large N, RangeSearch is still overall faster, but the execution time can still be improved.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant