Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2024

Abstract

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.

Keywords

Uncertain graphs, Graph algorithms, Parallel programming, Computing methodologies, Shared memory algorithms, network reliability

Discipline

Computer Sciences | Databases and Information Systems

Research Areas

Data Science and Engineering

Areas of Excellence

Digital transformation

Publication

Proceedings of the ACM SIGMOD/PODS Conference, Management of Data 2024 : Santiago, Chile, June 9-14

Volume

2

First Page

1

Last Page

24

Identifier

10.1145/3654982

Publisher

Association for Computing Machinery

City or Country

Santiago, Chile

Additional URL

https://doi.org/10.1145/3654982

Download

Share

COinS