search

asg017 / sqlite-vec

A vector search SQLite extension that runs anywhere!
Apache License 2.0
4.26k stars 135 forks source link

KD-Tree or Ball-Tree Algorithms for kNN search? #113

Open RayHackett opened 1 month ago

RayHackett commented 1 month ago

Thanks for developing the library. So far using to run a KNN on embedding vectors it has been pretty straight forward.
Are there any plans to speed up KNN search by introducing clever algorithms like a K-D tree or Ball-Tree? Running a brute force search on every query seems a bit wasteful for large data tables.
It would be amazing if create index ... ON Table(vector) was actually creating a K-D tree.

Best wishes!

mholt commented 1 month ago

Is this the same as #25? (I am new here, sorry if irrelevant!)

RayHackett commented 1 month ago

I suppose that depends on how you implement k-d or ball tree algorithms though they could be.
There seem to be some ANN implementations for SQLite. I was looking at this ticket #94 for alternatives.
This ticket was more aimed at faster exact kNN search algorithms before trying out approximate NNs. I realize implementing any of this is not at all trivial.