cockroachdb / cockroachdb/cockroach
sql/vecindex: use more precise RaBitQ error bounds
- 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
Assessment
This issue has not been assessed yet.