Graph compression cuts memory for fast nearest neighbor search
Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search
Information Retrieval
Summary
Finding the closest items in large collections often uses graphs that connect similar things, but saving these graphs takes up a lot of computer memory. The authors developed a way to shrink the memory used by these connection lists without slowing down how quickly searches happen. They rearranged the graph data offline so it compresses better and can be quickly unpacked when needed. Tests show their method saves over half the memory with almost no delay, and it’s already used at eBay to reduce storage without affecting speed.
What this means in practice
- •For search infrastructure engineers: Shrink memory needed for graph-based nearest neighbor indexes to reduce hosting costs without slowing queries.
- •For e-commerce data teams: Cut storage for similarity search graphs in product recommendation systems while keeping fast user responses.
Authors
Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini
Abstract
Graph-based Approximate Nearest Neighbor (ANN) indexes, such as HNSW, are the backbone of modern vector search. However, their massive memory footprint creates a severe infrastructure bottleneck. While vector quantization is widely adopted to reduce the memory required to store data vectors, the graph's edge structure increasingly dominates total memory usage. Compressing these adjacency lists for online search presents a critical system challenge: because decompression occurs during query processing, i.e., while navigating the graph, memory savings cannot come at the expense of query latency. In this paper, we present a compression technique explicitly tailored for live HNSW routing. By applying offline graph permutations to artificially induce structural locality, we enable the use of SIMD-accelerated integer compressors, such as Stream VByte, for rapid on-the-fly decompression. Evaluated across diverse real-world workloads, we significantly outperform the current state of the art in both compression ratio and query latency. Our experimental results show that we achieve compression ratios up to 52.7% with negligible penalties in latency compared to the uncompressed baseline. Furthermore, our technique has been effectively deployed in production at eBay, achieving up to 44.3% reduction in edge storage with no degradation in query latency.