{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:35Z","timestamp":1773481955426,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Natural Science Foundation","award":["NSF CCF-2217104"],"award-info":[{"award-number":["NSF CCF-2217104"]}]},{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U23A20496, 62072113"],"award-info":[{"award-number":["U23A20496, 62072113"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shanghai Science and Technology Innovation Action Plan","award":["21511100401"],"award-info":[{"award-number":["21511100401"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>As one of the most primitive operators in graph algorithms, such as the triangle counting, maximal clique enumeration, and subgraph listing, a set intersection operator returns common vertices between any two given sets of vertices in data graphs. It is therefore very important to accelerate the set intersection, which will benefit a bunch of tasks that take it as a built-in block. Existing works on the set intersection usually followed the merge intersection or galloping-search framework, and most optimization research focused on how to leverage the SIMD hardware instructions. In this paper, we propose a novel multi-level set intersection framework, namely hierarchical set partitioning and join (HERO), by using our well-designed set intersection bitmap tree (SIB-tree) index, which is independent of SIMD instructions and completely orthogonal to the merge intersection framework. We recursively decompose the set intersection task into small-sized subtasks and solve each subtask using bitmap and boolean AND operations. To sufficiently achieve the acceleration brought by our proposed intersection approach, we formulate a graph reordering problem, prove its NP-hardness, and then develop a heuristic algorithm to tackle this problem. Extensive experiments on real-world graphs have been conducted to confirm the efficiency and effectiveness of our HERO approach. The speedup over classic merge intersection achieves up to 188x and 176x for triangle counting and maximal clique enumeration, respectively.<\/jats:p>","DOI":"10.1145\/3639284","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-25","source":"Crossref","is-referenced-by-count":5,"title":["HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-3990-1634","authenticated-orcid":false,"given":"Boyu","family":"Yang","sequence":"first","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1200-7368","authenticated-orcid":false,"given":"Weiguo","family":"Zheng","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7681-3807","authenticated-orcid":false,"given":"Xiang","family":"Lian","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kent State University, Kent, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-7096-5328","authenticated-orcid":false,"given":"Yuzheng","family":"Cai","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9059-3713","authenticated-orcid":false,"given":"X. Sean","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007931"},{"key":"e_1_2_2_3_1","first-page":"679","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12--14, 2003","author":"Blandford D. K.","year":"2003","unstructured":"Blandford, D. K., Blelloch, G. E., and Kash, I. A. Compact representations of separable graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12--14, 2003, Baltimore, Maryland, USA (2003), ACM\/SIAM, pp. 679--688."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3186954"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_2_6_1","series-title":"RNTI","first-page":"37","volume-title":"Actes des 10e journ\u00e9es francophones sur les Entrep\u00f4ts de Donn\u00e9es et l'Analyse en Ligne, EDA","author":"Chambi S.","year":"2014","unstructured":"Chambi, S., Lemire, D., Godin, R., and Kaser, O. Roaring bitmap : nouveau mod\u00e8le de compression bitmap. In Actes des 10e journ\u00e9es francophones sur les Entrep\u00f4ts de Donn\u00e9es et l'Analyse en Ligne, EDA 2014, Vichy, France, 5--6 Juin, 2014 (2014), S. Bimonte, L. d'Orazio, and E. Negre, Eds., vol. B-10 of RNTI, Hermann-\u00c9ditions, pp. 37--50."},{"key":"e_1_2_2_7_1","first-page":"4","article-title":"A novel triangle count-based influence maximization method on social networks","volume":"12","author":"Chandran J.","year":"2021","unstructured":"Chandran, J., and V., M. V. A novel triangle count-based influence maximization method on social networks. Int. J. Knowl. Syst. Sci. 12, 4 (2021), 92--108.","journal-title":"Int. J. Knowl. Syst. Sci."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9--11, 2000","author":"Demaine E. D.","year":"2000","unstructured":"Demaine, E. D., L\u00f3pez-Ortiz, A., and Munro, J. I. Adaptive set intersections, unions, and differences. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9--11, 2000, San Francisco, CA, USA (2000), D. B. Shmoys, Ed., ACM\/SIAM, pp. 743--752."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939862"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1938545.1938550"},{"key":"e_1_2_2_13_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"Garey, M. R., and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196924"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2021.108103"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735518"},{"key":"e_1_2_2_17_1","volume-title":"WISA 2021, Kaifeng, China, September 24--26, 2021, Proceedings","volume":"12999","author":"Kang J.","year":"2021","unstructured":"Kang, J., Zhang, J., Song, W., and Yang, X. Friend relationships recommendation algorithm in online education platform. In Web Information Systems and Applications - 18th International Conference, WISA 2021, Kaifeng, China, September 24--26, 2021, Proceedings (2021), C. Xing, X. Fu, Y. Zhang, G. Zhang, and C. Borjigin, Eds., vol. 12999 of Lecture Notes in Computer Science, Springer, pp. 592--604."},{"key":"e_1_2_2_18_1","first-page":"1343","volume-title":"22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13--17, 2013, Companion","author":"Kunegis J. KONECT","unstructured":"Kunegis, J. KONECT: the koblenz network collection. In 22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13--17, 2013, Companion Volume (2013), L. Carr, A. H. F. Laender, B. F. L\u00f3scio, I. King, M. Fontoura, D. Vrandecic, L. Aroyo, J. P. M. de Oliveira, F. Lima, and E. Wilde, Eds., International World Wide Web Conferences Steering Committee \/ ACM, pp. 1343--1350."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2326"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2560"},{"key":"e_1_2_2_21_1","unstructured":"Leskovec J. and Krevl A. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2320716"},{"key":"e_1_2_2_23_1","first-page":"1","volume-title":"International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures - ADMS 2011","author":"Schlegel B.","year":"2011","unstructured":"Schlegel, B., Willhalm, T., and Lehner, W. Fast sorted-set intersection using SIMD instructions. In International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures - ADMS 2011, Seattle, WA, USA, September 2, 2011 (2011), R. Bordawekar and C. A. Lang, Eds., pp. 1--8."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw074"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018787"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_2_2_29_1","volume-title":"A. Statistical mechanics and its applications 415","author":"Yaozu","year":"2014","unstructured":"Yaozu, Cui, Junqiu, Li, Xingyuan, and Wang. Uncovering the overlapping community structure of complex networks by maximal cliques. Physica, A. Statistical mechanics and its applications 415 (2014), 398--406."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.3390\/a7020243"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467219"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639284","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:16:11Z","timestamp":1755789371000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639284"],"URL":"https:\/\/doi.org\/10.1145\/3639284","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}