Lune

SIGMOD2026Top-tier venue

DiskJoin: Large-scale Vector Similarity Join with SSD

Yanqi Chen, Xiao Yan, Alexandra Meliou, Eric Lo

Abstract

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 50× to 1000×.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint cites SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search
  • An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint cites SONG: Approximate Nearest Neighbor Search on GPU
  • Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment cites SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search
  • Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment cites An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on10

  1. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood SearchQi Chen, Bing Zhao, Haidong Wang, Mingqin Li et al.NeurIPS 2021 · 219 citations
  2. SONG: Approximate Nearest Neighbor Search on GPUWeijie Zhao, Shulong Tan, Ping LiICDE 2020 · 103 citations
  3. An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute ConstraintMengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang et al.NeurIPS 2023 · 70 citations
  4. Similarity search in the blink of an eye with compressed indicesCecilia Aguerrebere, Ishwar Singh Bhati, Mark Hildebrand, Mariano Tepper et al.VLDB 2023 · 64 citations
  5. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data SegmentMengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu et al.SIGMOD 2024 · 63 citations

Related papers

  1. MetricJoin: Leveraging Metric Properties for Robust Exact Set Similarity JoinsManuel Widmoser, Daniel Kocher, Nikolaus Augsten, Willi MannICDE 2023 · 4 citations
  2. Fast Approximate Similarity Join in Vector DatabasesJiadong Xie, Jeffrey Xu Yu, Yingfan LiuSIGMOD 2025 · 6 citations
  3. TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based PruningYitong Song, Pengcheng Zhang, Chao Gao, Bin Yao et al.SIGMOD 2026 · 1 citation
  4. DISK: A Distributed Framework for Single-Source SimRank with Accuracy GuaranteeYue Wang, Ruiqi Xu, Zonghao Feng, Yulin Che et al.VLDB 2021 · 7 citations
  5. Out-of-Core Parallel Spatial Join Outperforming In-Memory Systems: A BFS-DFS Hybrid ApproachLyuheng Yuan, Da Yan, Akhlaque Ahmad, Jiao Han et al.HPDC 2025
Dusk over the sea between two cliffs drawn in fine vertical lines