What is it about?
Many search and recommendation systems represent texts, images or products as long lists of numbers and answer a query by finding the items whose numbers are closest to it. To do this quickly, they build a “map” that links each item to a few dozen similar items, and the search hops from item to item along these links. In many real systems these links take up more memory than the items themselves. We show how to store the links in much less space without losing any information. First, we renumber the items so that items linked to each other get close numbers. Then we store each list of links with a compression method that modern processors can decode in a few instructions while the search is running.
Featured Image
Photo by Logan Voss on Unsplash
Why is it important?
Memory is one of the main costs of running similarity search at scale, because these maps must stay in RAM to answer queries fast. On four public and industrial datasets, our method cuts the memory used by the links by up to 52.7% and returns exactly the same results, with search speed equal to or slightly better than the uncompressed version. At eBay, the approach reduced the size of the map used in product search by 44.3% with no measurable slowdown, which allowed this kind of search to be extended to more use cases. The code is released as open source in the kANNolo library.
Perspectives
Most work on reducing the memory of similarity search focuses on compressing the items, while the links between them are often overlooked. I hope this work shows that the links deserve the same attention, and that simple, hardware-friendly techniques can bring large savings in real systems.
Francesco Benocci
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - CNR
Read the Original
This page is a summary of: Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search, November 2026, ACM (Association for Computing Machinery),
DOI: 10.1145/3799682.3840116.
You can read the full text:
Contributors
The following have contributed to this page







