Multi-HNSW graphs per segment?

[benwtrent]

Description

What do we think about clustering or grouping documents by centroids, or potentially in chunks of filters and allow multiple graphs per segment. If segments are random sub-samples, it is conceivable that clusters are of common distributions, consequently we can quit searching clusters early and only search a couple of the clusters at a time.

Seeing the optimistic query changes, makes me think we can maybe cluster, have one graph per cluster (or chunk of the ordered docs) and more eagerly enable early termination of the multi-graph searches.

This is a crazy idea, maybe it ain't worth doing.

[atris]

It's actually crazy - I was thinking of starting a discussion on this today.

One thing that I have been playing with is creating clusters with centroids that are at a certain range distance from a given reference point, and then using a triangulation method during search to "estimate" the distance of faraway clusters and only traverse their members if any point seems to be a viable candidate for topN.

This is especially useful for disconnected data sets, where some relevant points might be distributed far from each other and early termination tends to ignore them.

Are you actively working on this? Or would you like me to explore more?

[tteofili]

it is conceivable that clusters are of common distributions, consequently we can quit searching clusters early and only search a couple of the clusters at a time.

I think this idea is worth exploring. this would help in speeding up (parallel) query execution by not considering some graphs/clusters and, as per @atris 's comment, might also mitigate issues with sparsely connected graphs.

[benwtrent]

Are you actively working on this? Or would you like me to explore more?

I am not actively exploring it. A POC is definitely needed to explore if this is worth it at search time.

I expect it to be a fair amount of work to make it fully worth while (e.g. optimized kmean merging, hnsw merging, searching, etc.), but if its worth it at search time, maybe some costs are worth it :).

[navneet1v]

@benwtrent I was also thinking on similar lines and I created this GH issue which eventually wants to create more than 1 graph at the segment level: #14247 Please share your thoughts on the same.

[atris]

@navneet1v Skimming through the issue, I think they refer to different problem statements.

What you primarily want in the referenced GH issue is the ability to filter on more metadata during traversal vs doing a pre filter on the candidate documents themselves. As Adrien pointed out, this is better solved with more efficient filtering approaches (I wonder if the recent work on ACORN would help?)

This issue is more towards the niche use cases where multiple graphs for a given segment would work. Multi threaded queries and disjoint cluster representation seem to be the immediate choices.

@benwtrent I plan on publishing a draft approach for the disjoint clusters problem - maybe we can start with that and make the plumbing viable enough for general multi graph cases?

@jpountz @msokolov would like to get your thoughts here, please

[jpountz]

This idea sounds worth exploring to me too. Intuitively, it may help pre-filtering too. E.g. if I think of an e-commerce use-case with a filter on the category field, it is likely that some clusters will more densely match the filter than others, and we can likely take advantage of that.

[atris]

Cool. Assigning this to myself

[navneet1v]

What you primarily want in the referenced GH issue is the ability to filter on more metadata during traversal vs doing a pre filter on the candidate documents themselves. As Adrien pointed out, this is better solved with more efficient filtering approaches (I wonder if the recent work on ACORN would help?)

This issue is more towards the niche use cases where multiple graphs for a given segment would work. Multi threaded queries and disjoint cluster representation seem to be the immediate choices.

So what I have been thinking here is if at a segment level we add a capability of having multiple graphs and make the process of generating those graphs generic will solve the problem I mentioned in github issue. See overall, how you split your docs into multiple clusters can be a choice for the user who is configuring the codec. If user wants to use k-Means algo to do clustering then it can use it, but if there are lets say other parameters in the document then that can be used for clustering/building different HNSW graphs.