- java.lang.Object
-
- org.apache.lucene.util.quantization.ScalarQuantizer
-
public class ScalarQuantizer extends java.lang.Object
Will scalar quantize float vectors into `int8` byte values. This is a lossy transformation. Scalar quantization works by first calculating the quantiles of the float vector values. The quantiles are calculated using the configured confidence interval. The [minQuantile, maxQuantile] are then used to scale the values into the range [0, 127] and bucketed into the nearest byte values.How Scalar Quantization Works
The basic mathematical equations behind this are fairly straight forward and based on min/max normalization. Given a float vector `v` and a confidenceInterval `q` we can calculate the quantiles of the vector values [minQuantile, maxQuantile].
byte = (float - minQuantile) * 127/(maxQuantile - minQuantile) float = (maxQuantile - minQuantile)/127 * byte + minQuantile
This then means to multiply two float values together (e.g. dot_product) we can do the following:
float1 * float2 ~= (byte1 * (maxQuantile - minQuantile)/127 + minQuantile) * (byte2 * (maxQuantile - minQuantile)/127 + minQuantile) float1 * float2 ~= (byte1 * byte2 * (maxQuantile - minQuantile)^2)/(127^2) + (byte1 * minQuantile * (maxQuantile - minQuantile)/127) + (byte2 * minQuantile * (maxQuantile - minQuantile)/127) + minQuantile^2 let alpha = (maxQuantile - minQuantile)/127 float1 * float2 ~= (byte1 * byte2 * alpha^2) + (byte1 * minQuantile * alpha) + (byte2 * minQuantile * alpha) + minQuantile^2
The expansion for square distance is much simpler:
square_distance = (float1 - float2)^2 (float1 - float2)^2 ~= (byte1 * alpha + minQuantile - byte2 * alpha - minQuantile)^2 = (alpha*byte1 + minQuantile)^2 + (alpha*byte2 + minQuantile)^2 - 2*(alpha*byte1 + minQuantile)(alpha*byte2 + minQuantile) this can be simplified to: = alpha^2 (byte1 - byte2)^2
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
ScalarQuantizer.FloatSelector
private static class
ScalarQuantizer.OnlineMeanAndVar
private static class
ScalarQuantizer.ScoreDocsAndScoreVariance
private static class
ScalarQuantizer.ScoreErrorCorrelator
This class is used to correlate the scores of the nearest neighbors with the errors in the scores.
-
Field Summary
Fields Modifier and Type Field Description private float
alpha
private byte
bits
private float
maxQuantile
private float
minQuantile
private static java.util.Random
random
static int
SCALAR_QUANTIZATION_SAMPLE_SIZE
private float
scale
(package private) static int
SCRATCH_SIZE
-
Constructor Summary
Constructors Constructor Description ScalarQuantizer(float minQuantile, float maxQuantile, byte bits)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private static float[]
candidateGridSearch(java.util.List<ScalarQuantizer.ScoreDocsAndScoreVariance> nearestNeighbors, java.util.List<float[]> vectors, float[] lowerCandidates, float[] upperCandidates, VectorSimilarityFunction function, byte bits)
(package private) void
deQuantize(byte[] src, float[] dest)
Dequantize a byte vector into a float vectorprivate static void
extractQuantiles(float[] confidenceIntervals, float[] quantileGatheringScratch, double[] upperSum, double[] lowerSum)
private static java.util.List<ScalarQuantizer.ScoreDocsAndScoreVariance>
findNearestNeighbors(java.util.List<float[]> vectors, VectorSimilarityFunction similarityFunction)
static ScalarQuantizer
fromVectors(FloatVectorValues floatVectorValues, float confidenceInterval, int totalVectorCount, byte bits)
This will read the float vector values and calculate the quantiles.(package private) static ScalarQuantizer
fromVectors(FloatVectorValues floatVectorValues, float confidenceInterval, int totalVectorCount, byte bits, int quantizationSampleSize)
static ScalarQuantizer
fromVectorsAutoInterval(FloatVectorValues floatVectorValues, VectorSimilarityFunction function, int totalVectorCount, byte bits)
private static void
gatherSample(FloatVectorValues floatVectorValues, float[] quantileGatheringScratch, java.util.List<float[]> sampledDocs, int i)
byte
getBits()
float
getConstantMultiplier()
float
getLowerQuantile()
(package private) static float[]
getUpperAndLowerQuantile(float[] arr, float confidenceInterval)
Takes an array of floats, sorted or not, and returns a minimum and maximum value.float
getUpperQuantile()
float
quantize(float[] src, byte[] dest, VectorSimilarityFunction similarityFunction)
Quantize a float vector into a byte vectorprivate float
quantizeFloat(float v, byte[] dest, int destIndex)
float
recalculateCorrectiveOffset(byte[] quantizedVector, ScalarQuantizer oldQuantizer, VectorSimilarityFunction similarityFunction)
Recalculate the old score corrective value given new current quantilesprivate static int[]
reservoirSampleIndices(int numFloatVecs, int sampleSize)
java.lang.String
toString()
-
-
-
Field Detail
-
SCALAR_QUANTIZATION_SAMPLE_SIZE
public static final int SCALAR_QUANTIZATION_SAMPLE_SIZE
- See Also:
- Constant Field Values
-
SCRATCH_SIZE
static final int SCRATCH_SIZE
- See Also:
- Constant Field Values
-
alpha
private final float alpha
-
scale
private final float scale
-
bits
private final byte bits
-
minQuantile
private final float minQuantile
-
maxQuantile
private final float maxQuantile
-
random
private static final java.util.Random random
-
-
Method Detail
-
quantize
public float quantize(float[] src, byte[] dest, VectorSimilarityFunction similarityFunction)
Quantize a float vector into a byte vector- Parameters:
src
- the source vectordest
- the destination vectorsimilarityFunction
- the similarity function used to calculate the quantile- Returns:
- the corrective offset that needs to be applied to the score
-
quantizeFloat
private float quantizeFloat(float v, byte[] dest, int destIndex)
-
recalculateCorrectiveOffset
public float recalculateCorrectiveOffset(byte[] quantizedVector, ScalarQuantizer oldQuantizer, VectorSimilarityFunction similarityFunction)
Recalculate the old score corrective value given new current quantiles- Parameters:
quantizedVector
- the old vectoroldQuantizer
- the old quantizersimilarityFunction
- the similarity function used to calculate the quantile- Returns:
- the new offset
-
deQuantize
void deQuantize(byte[] src, float[] dest)
Dequantize a byte vector into a float vector- Parameters:
src
- the source vectordest
- the destination vector
-
getLowerQuantile
public float getLowerQuantile()
-
getUpperQuantile
public float getUpperQuantile()
-
getConstantMultiplier
public float getConstantMultiplier()
-
getBits
public byte getBits()
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
reservoirSampleIndices
private static int[] reservoirSampleIndices(int numFloatVecs, int sampleSize)
-
fromVectors
public static ScalarQuantizer fromVectors(FloatVectorValues floatVectorValues, float confidenceInterval, int totalVectorCount, byte bits) throws java.io.IOException
This will read the float vector values and calculate the quantiles. If the number of float vectors is less thanSCALAR_QUANTIZATION_SAMPLE_SIZE
then all the values will be read and the quantiles calculated. If the number of float vectors is greater thanSCALAR_QUANTIZATION_SAMPLE_SIZE
then a random sample ofSCALAR_QUANTIZATION_SAMPLE_SIZE
will be read and the quantiles calculated.- Parameters:
floatVectorValues
- the float vector values from which to calculate the quantilesconfidenceInterval
- the confidence interval used to calculate the quantilestotalVectorCount
- the total number of live float vectors in the index. This is vital for accounting for deleted documents when calculating the quantiles.bits
- the number of bits to use for quantization- Returns:
- A new
ScalarQuantizer
instance - Throws:
java.io.IOException
- if there is an error reading the float vector values
-
fromVectors
static ScalarQuantizer fromVectors(FloatVectorValues floatVectorValues, float confidenceInterval, int totalVectorCount, byte bits, int quantizationSampleSize) throws java.io.IOException
- Throws:
java.io.IOException
-
fromVectorsAutoInterval
public static ScalarQuantizer fromVectorsAutoInterval(FloatVectorValues floatVectorValues, VectorSimilarityFunction function, int totalVectorCount, byte bits) throws java.io.IOException
- Throws:
java.io.IOException
-
extractQuantiles
private static void extractQuantiles(float[] confidenceIntervals, float[] quantileGatheringScratch, double[] upperSum, double[] lowerSum)
-
gatherSample
private static void gatherSample(FloatVectorValues floatVectorValues, float[] quantileGatheringScratch, java.util.List<float[]> sampledDocs, int i) throws java.io.IOException
- Throws:
java.io.IOException
-
candidateGridSearch
private static float[] candidateGridSearch(java.util.List<ScalarQuantizer.ScoreDocsAndScoreVariance> nearestNeighbors, java.util.List<float[]> vectors, float[] lowerCandidates, float[] upperCandidates, VectorSimilarityFunction function, byte bits)
-
findNearestNeighbors
private static java.util.List<ScalarQuantizer.ScoreDocsAndScoreVariance> findNearestNeighbors(java.util.List<float[]> vectors, VectorSimilarityFunction similarityFunction)
- Parameters:
vectors
- The vectors to find the nearest neighbors for each othersimilarityFunction
- The similarity function to use- Returns:
- The top 10 nearest neighbors for each vector from the vectors list
-
getUpperAndLowerQuantile
static float[] getUpperAndLowerQuantile(float[] arr, float confidenceInterval)
Takes an array of floats, sorted or not, and returns a minimum and maximum value. These values are such that they reside on the `(1 - confidenceInterval)/2` and `confidenceInterval/2` percentiles. Example: providing floats `[0..100]` and asking for `90` quantiles will return `5` and `95`.- Parameters:
arr
- array of floatsconfidenceInterval
- the configured confidence interval- Returns:
- lower and upper quantile values
-
-