This PR introduces support for compressed edges representation in DiskANN implementation. For now, only 1bit quantization is supported with the corresponding index parameter: libsql_vector_idx(e, 'compress_neighbors=1bit').
In order to support compressed representation DiskANN search procedure were changed and now it supports 2 list of nodes:
aCandidates - list of unvisited candidates ordered by distance calculated with edge vector type (it will be compressed if index uses compression of edges)
aTopCandidates - list of top visited candidates ordered by the exact distance calculated with node vector type
This was done in order to always compare distances produced by the same vector representation: aCandidates ordered by distance between vector of "edge type" (potentially compressed, but not always) while aTopCandidates ordered by distance between vector of "node type" (exact)
Changes
Introduce vector index parameter: compress_neighbors=1bit
Implement basic vector1bit functions
For now 1BIT vectors is not exposed internally and can be used only inside the diskann
Extended DiskAnnSearchCtx with aTopCandidates list
Extend binary on-disk format to v2 to store distance from node to edges
penberg
commented
3 months ago
Context
This PR introduces support for compressed edges representation in DiskANN implementation. For now, only
1bitquantization is supported with the corresponding index parameter:libsql_vector_idx(e, 'compress_neighbors=1bit').In order to support compressed representation
DiskANNsearch procedure were changed and now it supports 2 list of nodes:aCandidates- list of unvisited candidates ordered by distance calculated with edge vector type (it will be compressed if index uses compression of edges)aTopCandidates- list of top visited candidates ordered by the exact distance calculated with node vector typeThis was done in order to always compare distances produced by the same vector representation:
aCandidatesordered by distance between vector of "edge type" (potentially compressed, but not always) whileaTopCandidatesordered by distance between vector of "node type" (exact)Changes
compress_neighbors=1bitvector1bitfunctionsDiskAnnSearchCtxwithaTopCandidateslistv2to store distance from node to edges