kaivalnp opened a new pull request, #16506:
URL: https://github.com/apache/lucene/pull/16506
### Description
Add a scalar-quantized version of the de-duplicating vector format
`DedupHnswScalarQuantizedVectorsFormat` (follow-up to #15979), which stores
each distinct vector once in both raw and scalar quantized form: searches score
against the quantized vectors, while raw vectors remain available for exact
reads and re-scoring (same as Lucene 10.4 OSQ).
De-duplication works like the raw format: vectors of the same dimension and
encoding form a group, and each field maps its document ordinals onto shared
group ordinals through a `fieldOrdToGroupOrd` translation.
Files:
- `.vdd`: Raw vectors and per-field data (same as the flat de-duplicating
format).
- `.vdqm` (metadata): groups with their per-flavor block locations (each
block records its own `ScalarEncoding`), followed by per-field entries. See
below for "flavor".
- `.vdqd` (quantized records): one block per `FLOAT32` group and
quantization flavor in use, one record per distinct vector (quantized bytes +
corrective terms in-line with the Lucene 10.4 OSQ format).
Design choices:
1. Data-blind quantization: Vectors are quantized against a zero centroid
instead of a per-field data-derived centroid.
1. A quantized record is then a pure function of the raw vector and its
flavor (independent of the other vectors in the segment), allowing for sane
de-duplication between fields containing overlapping vectors.
2. This also gives merges a fast path: records from source segments in
this format are copied verbatim instead of re-reading raw vectors and
re-running the interval optimization (re-quantization only happens on flush, or
when a source has an incompatible encoding/flavor).
3. The tradeoff is accuracy on off-center data relative to
centroid-centered quantization.
2. Per-similarity "flavors": One record can't serve all similarity functions
(`EUCLIDEAN` needs the squared norm as its corrective term; `COSINE` needs
write-time normalization).
1. Each group therefore stores one block per flavor in use —
`EUCLIDEAN`, `DOT_PRODUCT` + `MAXIMUM_INNER_PRODUCT`, and `COSINE`, so fields
whose similarity functions map to the same flavor share records, and every
flavor scores through the stock `Lucene104ScalarQuantizedVectorScorer` with no
custom score math.
2. The scorer is a small subclass of the raw format's scorer: doc
operations on the field's values, vector operations delegated to the group
view, ordinals translated once per comparison (same as the flat format).
3. Quantized records are 1:1 with group ordinals: Since quantization is
lossy, distinct raw vectors can collapse to identical quantized bytes, so a
second level of de-duplication is possible in principle.
1. This was deliberately left out: it would require maintaining a second
ordinal mapping (`groupOrd → quantizedOrd`) off-heap, de-duplicating quantized
bytes (hash + equality checks on collision), splitting corrective terms into a
separate dense block, and writing temp files + read-back during merge for
proper de-duplication.
2. Keeping records 1:1 with group ordinals shares the existing
`fieldOrdToGroupOrd` map between raw and quantized data and keeps merges
streaming, at the cost of occasionally storing byte-identical quantized records
for distinct raw vectors.
**DISCLAIMER**: Much of this code was written by an AI, but I have reviewed
and refined most of it!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
