# Bolt: Accelerated Data Mining with Fast Vector Compression

arXiv: https://arxiv.org/abs/1706.10283 · HTML: https://mlsanity.com/paper/1706.10283/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2017.

## Built on by (most cited first, 7 of 7)

- [Multiplying Matrices Without Multiplying](https://mlsanity.com/paper/2106.10860/) (2021)
- [LUT-NN: Empower Efficient Neural Network Inference with Centroid Learning and Table Lookup](https://mlsanity.com/paper/2302.03213/) (2023)
- [TOD: GPU-accelerated Outlier Detection via Tensor Operations](https://mlsanity.com/paper/2110.14007/) (2021)
- [Binary Embedding-based Retrieval at Tencent](https://mlsanity.com/paper/2302.08714/) (2023)
- [ARM 4-BIT PQ: SIMD-based Acceleration for Approximate Nearest Neighbor Search on ARM](https://mlsanity.com/paper/2203.02505/) (2022)
- [Stella Nera: A Differentiable Maddness-Based Hardware Accelerator for Efficient Approximate Matrix Multiplication](https://mlsanity.com/paper/2311.10207/) (2023)
- [LeanStream: A Speculate-and-Refine Streaming Framework for Efficient on-Device LLM Inference](https://mlsanity.com/paper/2609.03079/) (2026)

## Abstract (arXiv)

Vectors of data are at the heart of machine learning and data mining. Recently, vector quantization methods have shown great promise in reducing both the time and space costs of operating on vectors. We introduce a vector quantization algorithm that can compress vectors over 12x faster than existing techniques while also accelerating approximate vector operations such as distance and dot product computations by up to 10x. Because it can encode over 2GB of vectors per second, it makes vector quantization cheap enough to employ in many more circumstances. For example, using our technique to compute approximate dot products in a nested loop can multiply matrices faster than a state-of-the-art BLAS implementation, even when our algorithm must first compress the matrices. In addition to showing the above speedups, we demonstrate that our approach can accelerate nearest neighbor search and maximum inner product search by over 100x compared to floating point operations and up to 10x compared to other vector quantization methods. Our approximate Euclidean distance and dot product computations are not only faster than those of related algorithms with slower encodings, but also faster than Hamming distance computations, which have direct hardware support on the tested platforms. We also assess the errors of our algorithm's approximate distances and dot products, and find that it is competitive with existing, slower vector quantization algorithms.