# DiskJoin: Large-scale Vector Similarity Join with SSD

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2025.

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

- [QVCache: A Query-Aware Vector Cache](https://mlsanity.com/paper/2602.02057/) (2026)
- [Qute: Towards Quantum-Native Database](https://mlsanity.com/paper/2602.14699/) (2026)

## Abstract (arXiv)

Similarity join--a widely used operation in data science--finds all pairs of items that have distance smaller than a threshold. Prior work has explored distributed computation methods to scale similarity join to large data volumes but these methods require a cluster deployment, and efficiency suffers from expensive inter-machine communication. On the other hand, disk-based solutions are more cost-effective by using a single machine and storing the large dataset on high-performance external storage, such as NVMe SSDs, but in these methods the disk I/O time is a serious bottleneck. In this paper, we propose DiskJoin, the first disk-based similarity join algorithm that can process billion-scale vector datasets efficiently on a single machine. DiskJoin improves disk I/O by tailoring the data access patterns to avoid repetitive accesses and read amplification. It also uses main memory as a dynamic cache and carefully manages cache eviction to improve cache hit rate and reduce disk retrieval time. For further acceleration, we adopt a probabilistic pruning technique that can effectively prune a large number of vector pairs from computation. Our evaluation on real-world, large-scale datasets shows that DiskJoin significantly outperforms alternatives, achieving speedups from 50x to 1000x.