{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T00:35:41Z","timestamp":1772930141555,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3654982","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-24","source":"Crossref","is-referenced-by-count":4,"title":["uBlade: Efficient Batch Processing for Uncertainty Graph Queries"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8243-3947","authenticated-orcid":false,"given":"Siyuan","family":"Yao","sequence":"first","affiliation":[{"name":"Singapore Management University &amp; National University of Singapore, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9646-291X","authenticated-orcid":false,"given":"Yuchen","family":"Li","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4060-9438","authenticated-orcid":false,"given":"Shixuan","family":"Sun","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8748-3225","authenticated-orcid":false,"given":"Jiaxin","family":"Jiang","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8618-4581","authenticated-orcid":false,"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"issue":"2","key":"e_1_2_1_1_1","first-page":"15","article-title":"Managing uncertainty in social networks","volume":"30","author":"Adar E.","year":"2007","unstructured":"E. Adar and C. Re. Managing uncertainty in social networks. IEEE Data Eng. Bull., 30(2):15--22, 2007.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_2_1","volume-title":"On a routing problem. Quarterly of applied mathematics, 16(1):87--90","author":"Bellman R.","year":"1958","unstructured":"R. Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87--90, 1958."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113362"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516438"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2015.109"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2535444"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490422.3502358"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.45"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOMW.2019.8845088"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335388"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218488513500074"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.201"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963192.1963217"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078447.3078452"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_1_21_1","first-page":"87","volume-title":"International Workshop of Algorithmic Aspects of Cloud Computing","author":"Kassiano V.","year":"2016","unstructured":"V. Kassiano, A. Gounaris, A. N. Papadopoulos, and K. Tsichlas. Mining uncertain graphs: An overview. In International Workshop of Algorithmic Aspects of Cloud Computing, pages 87--116. Springer, 2016."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324304"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_24_1","first-page":"535","volume-title":"Proceedings of the 17th International Conference on Extending Database Technology","author":"Khan A.","year":"2014","unstructured":"A. Khan, F. Bonchi, A. Gionis, and F. Gullo. Fast reliability search in uncertain graphs. In Proceedings of the 17th International Conference on Extending Database Technology, pages 535--546, 2014."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824133"},{"key":"e_1_2_1_26_1","volume-title":"Morgan & Claypool","author":"Khan A.","year":"2018","unstructured":"A. Khan, Y. Ye, and L. Chen. On uncertain graphs. synthesis lectures on data management. Morgan & Claypool, 2018."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.243"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04670"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565844"},{"key":"e_1_2_1_30_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0220-3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2485212"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00047"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807843"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794376"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457253"},{"key":"e_1_2_1_38_1","volume-title":"An indexing framework for queries on probabilistic graphs. ACM Transactions on Database Systems (TODS), 42(2):1--34","author":"Maniu S.","year":"2017","unstructured":"S. Maniu, R. Cheng, and P. Senellart. An indexing framework for queries on probabilistic graphs. ACM Transactions on Database Systems (TODS), 42(2):1--34, 2017."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593668"},{"key":"e_1_2_1_41_1","first-page":"06","article-title":"Interactive exploration of heterogeneous biological networks with biomine explorer","author":"V.","year":"2019","unstructured":"V. Podpe?an, ?. Ram?ak, K. Gruden, H. Toivonen, and N. Lavra?. Interactive exploration of heterogeneous biological networks with biomine explorer. Bioinformatics, 06 2019.","journal-title":"Bioinformatics"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450988"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476257"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_48_1","volume-title":"The complexity of enumeration and reliability problems. siam Journal on Computing, 8(3):410--421","author":"Valiant L. G.","year":"1979","unstructured":"L. G. Valiant. The complexity of enumeration and reliability problems. siam Journal on Computing, 8(3):410--421, 1979."},{"issue":"2","key":"e_1_2_1_49_1","first-page":"2019","article-title":"Scaleg: A distributed disk-based system for vertex-centric graph processing","volume":"35","author":"Wang X.","year":"2023","unstructured":"X. Wang, D. Wen, L. Qin, L. Chang, Y. Zhang, and W. Zhang. Scaleg: A distributed disk-based system for vertex-centric graph processing. IEEE Transactions on Knowledge and Data Engineering, 35(2):2019--2033, 2023.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639288"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3524059.3532379"},{"key":"e_1_2_1_52_1","first-page":"441","volume-title":"2018 USENIX Annual Technical Conference (USENIX ATC 18)","author":"Zhang Y.","year":"2018","unstructured":"Y. Zhang, X. Liao, H. Jin, L. Gu, L. He, B. He, and H. Liu. {CGraph}: A correlations-aware approach for efficient concurrent iterative graph processing. In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 441--452, 2018."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356143"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4304\/jnw.9.9.2353-2359"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.64"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.70"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654982","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:39:11Z","timestamp":1755787151000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654982"],"URL":"https:\/\/doi.org\/10.1145\/3654982","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}