DiskJoin: Large-scale Vector Similarity Join with SSD
Proceedings of the ACM on Management of Data · 04.12.2025 · 3 (6) · 1-27
DOI: 10.1145/3769780 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 05.12.2025. Verfasst von Yanqi Chen und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 65 Literaturangaben.
Abstract (Originalsprache)
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×.
Zitieren
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}
}
EUVIMED