EUVIMEDSkopri EUVIMED
Crossref

DiskJoin: Large-scale Vector Similarity Join with SSD

Yanqi Chen, Xiao Yan, Alexandra Meliou, Eric Lo

Proceedings of the ACM on Management of Data · 2025-12-04 · 3 (6) · 1-27

DOI: 10.1145/3769780 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2025-12-05. Written by Yanqi Chen and 3 co-authors. Cited 4 times so far (Crossref); 65 references.

AstrattDettalji biblijografiċiCiteRelated studies

Abstract (original language)

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×.

Cite

APA

Chen, Y., Yan, X., Meliou, A., & Lo, E. (2025). DiskJoin: Large-scale Vector Similarity Join with SSD. Proceedings of the ACM on Management of Data, 3(6), 1-27. https://doi.org/10.1145/3769780

Vancouver

Chen Y, Yan X, Meliou A, Lo E. DiskJoin: Large-scale Vector Similarity Join with SSD. Proceedings of the ACM on Management of Data. 2025;3(6):1-27. doi:10.1145/3769780

BibTeX
@article{Chen2025,
  author = {Chen, Yanqi and Yan, Xiao and Meliou, Alexandra and Lo, Eric},
  title = {DiskJoin: Large-scale Vector Similarity Join with SSD},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2025},
  volume = {3},
  number = {6},
  pages = {1--27},
  doi = {10.1145/3769780}
}
Start for free →