uBlade: efficient batch processing for uncertainty graph queries

• Main Authors: YAO, Siyuan, LI, Yuchen, SUN, Shixuan, JIANG, Jiaxin, HE, Bingsheng
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Uncertain graphs; Graph algorithms; Parallel programming; Computing methodologies; Shared memory algorithms; network reliability; Computer Sciences; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/9754; https://ink.library.smu.edu.sg/context/sis_research/article/10754/viewcontent/3654982.pdf
• Institution: Singapore Management University

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 sampling-loads 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 ��, with ��(��) denoting the batch size. We further examine the extra sampling-load 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.