cockroachdb / cockroachdb/cockroach

sql/vecindex: use more precise RaBitQ error bounds

Open
#157,020 0 comments 0 reactions 1 assignee Claimed by @cthumuluru-crdb View on GitHub
A-vector-index C-enhancement P-2 T-specialized-indexing
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

Currently, the RaBitQ error bounds are calculated as +- 1/√dims. However, this is a rough estimate. The original paper gives a more precise formula (formula 14). We should switch to using that.

However, we'll have to experiment with the best value of `𝜖0`, which is a parameter that controls the probability that we'll fail to identify a potential nearest neighbor when scanning. If we set that too low, we'll return too many candidate results, slowing down the search and canceling out the benefits of quantization. If we that too high, we'll limit the accuracy of searches.

Also, it appears that the best value for `𝜖0` depends on the particular dataset and the beam size setting. So we need to do some analysis and thinking about how to derive a good value, perhaps based on the beam size.

Jira issue: CRDB-56350

Epic CRDB-66573

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.