EUVIMEDEUVIMED entdecken
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 · 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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →