150-char summary: First production Rust impl of FINGER (WWW 2023) β skips 80%+ of graph ANN distance computations using precomputed residual bases, reducing per-query cost in vector search pipelines.
Modern vector databases β Qdrant, Milvus, Weaviate, Pinecone β all rely on graph-based approximate nearest neighbor (ANN) algorithms like HNSW. The shared bottleneck: every graph edge traversal requires an O(D) exact distance computation against a D-dimensional embedding. At D=128 (SIFT, visual features) or D=1536 (GPT-4 text embeddings), over 80% of these computations are wasted β the neighbor is too far to ever enter the top-k result set.
FINGER (Chen et al., WWW 2023, arXiv:2206.11408) solves this by precomputing a K-dimensional orthonormal basis from each graph node's edge-residual vectors at build time. During beam search, it projects the query residual onto this K-dimensional subspace o