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

Add BK Tree implementation #295

Open
maxbachmann opened this issue Nov 30, 2022 · 2 comments
Open

Add BK Tree implementation #295

maxbachmann opened this issue Nov 30, 2022 · 2 comments
Labels
enhancement New feature or request performance

Comments

@maxbachmann
Copy link
Member

maxbachmann commented Nov 30, 2022

It would make sense to add a BK Tree implementation for scorers which full fill the triangle inequality. This would provide massive performance improvements for things like searches.

https://dl.acm.org/doi/10.1145/362003.362025

@maxbachmann maxbachmann added enhancement New feature or request performance labels Nov 30, 2022
@maxbachmann
Copy link
Member Author

A common use case for things like search engines is to generate the tree once and then use it for searches. For this reason this should support some kind of serialization / deserialization. This should be simple for the tree structure itself. However it is unclear how this should handle the user specified data, since they could be in pretty much any data format. Probably this part should be left up to the user to do (strings could be serialized automatically).

@maxbachmann
Copy link
Member Author

In the same context Levenshtein automatons could be interesting as well: https://dmice.ohsu.edu/bedricks/courses/cs655/pdf/readings/2002_Schulz.pdf

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request performance
Projects
None yet
Development

No branches or pull requests

1 participant