uBlade: Efficient Batch Processing for Uncertainty Graph Queries
Proceedings of the ACM on Management of Data · 29.05.2024 · 2 (3) · 1-24
DOI: 10.1145/3654982 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2024. Verfasst von Siyuan Yao und 4 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
The study of uncertain graphs is crucial in diverse fields, including but not limited to protein interaction analysis, viral marketing, and network reliability. Processing queries on uncertain graphs presents formidable challenges due to the vast probabilistic space they encapsulate. While existing systems employ batch processing to address these challenges, their performance is often compromised by the suboptimal selection of parallel graph traversal methods, the excessive costs in random number generation, and additional workloads intrinsic to batch processing. In this paper, we introduce uBlade, an efficient batch-processing framework for uncertain graph queries on multi-core CPUs. uBlade utilizes the work-efficient graph traversal, achieving superior parallelism in the batch processing model. Additionally, our Quasi-Sampling technique reduces the random number generation cost by a factor of B, with O(B) denoting the batch size. We further examine the extra workload resulting from batch processing and introduce an efficient strategy to reorder possible worlds, minimizing this associated overhead. Through comprehensive evaluations, we showcase that uBlade achieves up to two orders of magnitude speedups against the state-of-the-art CPU and GPU-based solutions.
Zitieren
APA
Yao, S., Li, Y., Sun, S., Jiang, J., & He, B. (2024). uBlade: Efficient Batch Processing for Uncertainty Graph Queries. Proceedings of the ACM on Management of Data, 2(3), 1-24. https://doi.org/10.1145/3654982
Vancouver
Yao S, Li Y, Sun S, Jiang J, He B. uBlade: Efficient Batch Processing for Uncertainty Graph Queries. Proceedings of the ACM on Management of Data. 2024;2(3):1-24. doi:10.1145/3654982
BibTeX
@article{Yao2024,
author = {Yao, Siyuan and Li, Yuchen and Sun, Shixuan and Jiang, Jiaxin and He, Bingsheng},
title = {uBlade: Efficient Batch Processing for Uncertainty Graph Queries},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {3},
pages = {1--24},
doi = {10.1145/3654982}
}
EUVIMED