Abstract
One of the main limitations of image search based on bag-of-features is the memory usage per image. Only a few million images can be handled on a single machine in reasonable response time. In this paper, we first evaluate how the memory usage is reduced by using lossless index compression. We then propose an approximate representation of bag-of-features obtained by projecting the corresponding histogram onto a set of pre-defined sparse projection functions, producing several image descriptors. Coupled with a proper indexing structure, an image is represented by a few hundred bytes. A distance expectation criterion is then used to rank the images. Our method is at least one order of magnitude faster than standard bag-of-features while providing excellent search quality.
Introduction
In the late 2000s, the computer vision community faced a massive scalability wall. The "Bag-of-Features" (BoF) model—which treats an image like a collection of "visual words"—was the gold standard for image retrieval. However, as datasets grew from thousands to millions (and eventually billions) of images, the memory requirements for these representations became unsustainable. This paper introduces miniBOFs, a highly compressed image representation that reduces memory usage by two orders of magnitude compared to standard BoF, enabling web-scale search on a single commodity server.
Lossless Index Compression
The authors first address the memory bottleneck of the inverted file index. By treating BoF vectors as binary—simply recording the presence or absence of a visual word—and applying entropy-based compression (such as arithmetic coding) to the inverted lists, memory usage can be reduced significantly.
As shown in the figure above, while raw binary BoF memory usage grows linearly with vocabulary size $k$, compressed inverted files maintain a much lower memory footprint, achieving a reduction factor of approximately 4 without any loss in search quality.
The miniBOF Approach
To achieve extreme scalability, the paper introduces an approximate representation called miniBOFs. This involves two key components:
Sparse Projections
The high-dimensional BoF histogram is projected onto several "vocabulary aggregators." These are sparse matrices, denoted as $A$, that group visual words together into a smaller number of dimensions ($d$).
Fusion via Distance Expectation
Because each miniBOF is a lossy, partial view of the original image, multiple miniBOF indexes are queried in parallel. The results are fused using a "distance expectation" criterion. If a database image does not appear in a specific miniBOF lookup, it is assigned a default "expected" distance, allowing for robust ranking across the entire database even with missing matches.
Evaluation and Results
The approach was evaluated on benchmarks including INRIA Holidays (mAP), UKY (top-4 accuracy), and a distractor set of one million Flickr images.
- Massive Compression: Standard BoF requires ~10-12 KB per image, whereas miniBOFs shrink this to just 160-320 bytes.
- Speedup: On Flickr1M, a miniBOF query took 132ms, a 22x speedup over the 3,000ms required for standard BoF.
- Accuracy: On the Holidays dataset, miniBOFs with 16 aggregators achieved an mAP of 0.452, slightly outperforming standard BoF (0.446) despite the massive compression.
Conclusion
The miniBOF method represents a significant trade-off between precision and scale. While it does not reach the accuracy of more memory-intensive methods like Hamming Embedding (0.75 mAP), its ability to index hundreds of millions of images on a single 64GB server makes it a powerful tool for web-scale retrieval. Future work may focus on learning optimized projection matrices to further bridge the accuracy gap.
Summary updated