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

[BUG] CAGRA recall is very low for moderate to heavy pre-filtering #429

Open
cjnolet opened this issue Oct 28, 2024 · 0 comments
Open

[BUG] CAGRA recall is very low for moderate to heavy pre-filtering #429

cjnolet opened this issue Oct 28, 2024 · 0 comments
Labels
bug Something isn't working

Comments

@cjnolet
Copy link
Member

cjnolet commented Oct 28, 2024

CAGRA currently supports pre-filtering, but it doesn't support the most practical use-cases for filtering (where the filter itself is > 50% sparsity) because the recall drops so low that the results just aren't usable at all. It is believes this is largely because the hash table fills up during search, causing the algorithm to ignore any additional potential edges as its popagating through the graph. We need to verify this assumption, but also think of ways we might be able to improve the search space to increase recall.

This problem is obviously not unique to CAGRA, but heavy prefiltering is a hard problem in general. When the number of vectors not being filtered out is <=10% of the graph, it can be efficient to use pre-filtered brute-force, but that also won't scale particularly well as we hit indexes into the billions and 10's to 100's of billions. We need to find a good solution for improving the filtered search over the graph (or using another method altogether that is cheap to do on the fly but scalable).

cc @rhdong @lowener @achirkin

@cjnolet cjnolet added the bug Something isn't working label Oct 28, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
Status: In Progress
Development

No branches or pull requests

1 participant