apache / apache/lucene

Speed up ScalarQuantization by selecting quantiles together

Open
#13,918 0 comments 1 reaction 0 assignees View on GitHub
module:core/hnsw type:enhancement vector-based-search
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

Currently in `ScalarQuantizer`, `ScalarQuantizer.fromVectorsAutoInterval()` will issue 4 calls (per to scratch-batch, basically `len(vector)/20`) `Selector.select()` and `ScalarQuantizer.fromVectors()` will issue 2 calls. All of these 4/2 calls use the same vectors, just asking for different `k` values. If we use a `multi-select` algorithm, instead of separate `select` algorithms, we can speed up these calls, especially `ScalarQuantizer.fromVectorsAutoInterval()` which is repeating a lot of logic.

The size of the list to select from is practically `20*vector_dimensions`, so this greater speed ups will be observed with larger dimensionality. (Or if `ScalarQuantizer.SCRATCH_SIZE` is ever increased)

Contributor guide

Open the contributing guide

Research direction

Start with ScalarQuantizer.fromVectorsAutoInterval(), ScalarQuantizer.fromVectors(), and Selector.select(); compare how the repeated k selections are assembled. Done means using a multi-select approach for the shared vectors while preserving quantization behavior and validating the intended speedup.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
performance, search
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.