uBlade: Efficient Batch Processing for Uncertain Graph Queries

Summary: uBlade: batch processing for uncertain-graph queries on multicore CPUs, combining work-efficient parallel traversal with Quasi-Sampling to cut RNG cost by ~B and a possible-world reordering strategy to reduce extra sampling load. Yields up to 100x speedups over prior CPU/GPU systems. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 7004
Venue: SIGMOD
Year: 2024
Pagerank: 5.1915905e-05
Overall Rank: 9,948 | 31.75%
DOI: 10.1145/3654982

Incoming Non-self Citations Over Time

Authors

1. Siyuan Yao (National University of Singapore; Singapore Management University)
2. Yuchen Li (Singapore Management University)
3. Shixuan Sun (Shanghai Jiao Tong University)
4. Jiaxin Jiang (National University of Singapore)
5. Bingsheng He (National University of Singapore)

BibTeX Citation

@inproceedings{yao_sigmod24,
        title = {{uBlade: Efficient Batch Processing for Uncertain Graph Queries}},
        author = {Yao, Siyuan and Li, Yuchen and Sun, Shixuan and Jiang, Jiaxin and He, Bingsheng},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654982},
        url = {https://dl.acm.org/doi/10.1145/3654982},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,590	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	5.093636e-05
10,754	Community Detection in Heterogeneous Information Networks Without Materialization	2025	SIGMOD	5.093636e-05
10,758	Dupin: A Parallel Framework for Densest Subgraph Discovery in Fraud Detection on Massive Graphs	2025	SIGMOD	5.093636e-05
10,963	RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
1,254	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.0001147266
1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011141552
1,432	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.0001080346
2,199	Real-time Targeted Influence Maximization for Online Advertisements	2015	VLDB	8.9668012e-05
2,874	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	8.0094569e-05
2,977	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.9035901e-05
3,738	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.1602939e-05
5,612	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	6.1501992e-05
5,889	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	6.0496722e-05
5,890	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	6.0496722e-05
6,003	ThunderRW: An In-Memory Graph Random Walk Engine	2021	VLDB	6.0130964e-05
6,037	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.9990983e-05
9,281	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.2933125e-05
11,165	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,075	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB
2	3,723	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB
3	6,345	Clustering Uncertain Graphs	2018	VLDB
4	8,345	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD
5	8,884	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD
6	6,037	On Uncertain Graphs Modeling and Queries	2015	VLDB
7	3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB
8	6,895	QUBLE: Blending Visual Subgraph Query Formulation with Query Processing on Large Networks	2013	SIGMOD
9	11,165	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD
10	4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB