Support range queries (neighbors within some distance)

[alexklibisz]

At least one of the datasets in the big-ann-benchmarks challenge will require support for range queries. This will take some rethinking of the existing query model and should be an interesting problem to solve.

[priamai]

Yes and also if we want give the ability to implement an external algorithm such as DBSCAN (and similars) which requires range queries, it's basically the epsilon parameter.

[priamai]

Just thinking out loud, I believe for the dense vector case we could use a structure such as a kd-tree during insertion time.
You can then use that to retrieve a portion of the entire search space and then within each partition do a check on the distance to filter the vectors.

[alexklibisz]

Hi @priamai, thanks for your input

Just thinking out loud, I believe for the dense vector case we could use a structure such as a kd-tree during insertion time.

Where exactly would the kd-tree reside? Everything we do in Elastiknn must be stored in Lucene indexes. That's what makes this problem pretty tough.

[robomotic]

Yes what about storing the KDTree as a nested document in a hidden index ? The tree will reference those points by their document id peraphs ?
One limitation will be if the tree becomes larger than the max document size (not sure what is the maximum allowed ) ?

[alexklibisz]

I'm not really sure how that would work. I would need the idea spelled out a bit more. Like, what exactly happens when a new vector is indexed? What exactly happens when we do a range query?

Another idea I've had is this: Given a vector and a distance, just internally re-run the standard nearest-neighbors query query several times with incrementally larger values of k. It's pretty wasteful, but would at least satisfy the API.

[priamai]

Yes I will mockup some code in python to get an idea.

Yes I like the second approach, it will not be efficient but at least we have an API we can replace eventually with a faster approach.

[alexklibisz]

I don't plan to implement this. Will happily review if someone else takes a pass at it.