{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:17Z","timestamp":1740109217051,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U23A20496"],"award-info":[{"award-number":["U23A20496"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100018625","name":"Science and Technology Innovation Plan Of Shanghai Science and Technology Commission","doi-asserted-by":"publisher","award":["21511100401"],"award-info":[{"award-number":["21511100401"]}],"id":[{"id":"10.13039\/501100018625","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s00778-024-00881-w","type":"journal-article","created":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T12:44:02Z","timestamp":1733143442000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A powerful reducing framework for accelerating set intersections over graphs"],"prefix":"10.1007","volume":"34","author":[{"given":"Zheng","family":"Hu","sequence":"first","affiliation":[]},{"given":"Cong","family":"Xu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1200-7368","authenticated-orcid":false,"given":"Weiguo","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,2]]},"reference":[{"issue":"4","key":"881_CR1","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/3129246","volume":"42","author":"CR Aberger","year":"2017","unstructured":"Aberger, C.R., Lamb, A., Tu, S., N\u00f6tzli, A., Olukotun, K., R\u00e9, C.: Emptyheaded: a relational engine for graph processing. ACM Trans. Database Syst. 42(4), 20:1-20:44 (2017)","journal-title":"ACM Trans. Database Syst."},{"key":"881_CR2","first-page":"13","volume":"3772","author":"RA Baeza-Yates","year":"2005","unstructured":"Baeza-Yates, R.A., Salinger, A.: Experimental analysis of a fast intersection algorithm for sorted sequences. String Process. Inf. Retr. 3772, 13\u201324 (2005)","journal-title":"String Process. Inf. Retr."},{"key":"881_CR3","unstructured":"Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: SODA, pp. 679\u2013688"},{"key":"881_CR4","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The webgraph framework I: compression techniques. In: WWW, pp. 595\u2013602. ACM (2004)","DOI":"10.1145\/988672.988752"},{"issue":"9","key":"881_CR5","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph (algorithm 457). Commun. ACM 16(9), 575\u2013576 (1973)","journal-title":"Commun. ACM"},{"key":"881_CR6","doi-asserted-by":"crossref","unstructured":"Chang, L., Li, W., Zhang, W.: Computing a near-maximum independent set in linear time by reducing-peeling. In: SIGMOD, pp. 1181\u20131196 (2017)","DOI":"10.1145\/3035918.3035939"},{"issue":"4","key":"881_CR7","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2043652.2043654","volume":"36","author":"J Cheng","year":"2011","unstructured":"Cheng, J., Ke, Y., Fu, A.W., Yu, J.X., Zhu, L.: Finding maximal cliques in massive networks. ACM Trans. Database Syst. 36(4), 21:1-21:34 (2011)","journal-title":"ACM Trans. Database Syst."},{"key":"881_CR8","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., Raghavan, P.: On compressing social networks. In: SIGKDD, pp. 219\u2013228. ACM (2009)","DOI":"10.1145\/1557019.1557049"},{"key":"881_CR9","doi-asserted-by":"crossref","unstructured":"Chu, S., Cheng, J.: Triangle listing in massive networks and its applications. In: SIGKDD, pp. 672\u2013680 (2011)","DOI":"10.1145\/2020408.2020513"},{"issue":"10","key":"881_CR10","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367\u20131372 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"881_CR11","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Adaptive set intersections, unions, and differences. In: SODA, pp. 743\u2013752 (2000)"},{"key":"881_CR12","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Kabiljo, I., Karrer, B., Ottaviano, G., Pupyrev, S., Shalita, A.: Compressing graphs and indexes with recursive graph bisection. In: SIGKDD, pp. 1535\u20131544. ACM (2016)","DOI":"10.1145\/2939672.2939862"},{"key":"881_CR13","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: ISAAC, Lecture Notes in Computer Science, vol. 6506, pp. 403\u2013414. Springer (2010)","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"881_CR14","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"issue":"7","key":"881_CR15","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.14778\/3384345.3384358","volume":"13","author":"P Gera","year":"2020","unstructured":"Gera, P., Kim, H., Sao, P., Kim, H., Bader, D.: Traversing large graphs on gpus with unified memory. Proc. VLDB Endow. 13(7), 1119\u20131133 (2020)","journal-title":"Proc. VLDB Endow."},{"key":"881_CR16","doi-asserted-by":"crossref","unstructured":"Han, M., Kim, H., Gu, G., Park, K., Han, W.: Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In: SIGMOD, pp. 1429\u20131446 (2019)","DOI":"10.1145\/3299869.3319880"},{"key":"881_CR17","doi-asserted-by":"crossref","unstructured":"Han, S., Zou, L., Yu, J.X.: Speeding up set intersections in graph algorithms using SIMD instructions. In: SIGMOD, pp. 1587\u20131602 (2018)","DOI":"10.1145\/3183713.3196924"},{"key":"881_CR18","unstructured":"Han, W., Lee, J., Lee, J.: Turbo$$ _{\\text{iso}}$$: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD, pp. 337\u2013348"},{"issue":"3","key":"881_CR19","first-page":"293","volume":"8","author":"H Inoue","year":"2014","unstructured":"Inoue, H., Ohara, M., Taura, K.: Faster set intersection with SIMD instructions by reducing branch mispredictions. PVLDB 8(3), 293\u2013304 (2014)","journal-title":"PVLDB"},{"issue":"1","key":"881_CR20","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48(1), 96\u2013129 (1998)","journal-title":"J. Parallel Distrib. Comput."},{"key":"881_CR21","unstructured":"Katsov, I.: Fast intersection of sorted lists using SSE instructions. (2012)"},{"key":"881_CR22","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: KONECT: the Koblenz network collection. In: WWW, pp. 1343\u20131350 (2013)","DOI":"10.1145\/2487788.2488173"},{"issue":"4","key":"881_CR23","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1002\/spe.2560","volume":"48","author":"D Lemire","year":"2018","unstructured":"Lemire, D., Kaser, O., Kurz, N., Deri, L., O\u2019Hara, C., Saint-Jacques, F., Ssi-Yan-Kai, G.: Roaring bitmaps: implementation of an optimized software library. Softw. Pract. Exp. 48(4), 867\u2013895 (2018)","journal-title":"Softw. Pract. Exp."},{"key":"881_CR24","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data (2014)"},{"issue":"12","key":"881_CR25","doi-asserted-by":"publisher","first-page":"3077","DOI":"10.1109\/TKDE.2014.2320716","volume":"26","author":"Y Lim","year":"2014","unstructured":"Lim, Y., Kang, U., Faloutsos, C.: Slashburn: graph compression and mining beyond caveman communities. IEEE Trans. Knowl. Data Eng. 26(12), 3077\u20133089 (2014)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"881_CR26","doi-asserted-by":"crossref","unstructured":"Pan, M., Li, R., Zhang, Q., Dai, Y., Tian, Q., Wang, G.: Fairness-aware maximal clique enumeration. In: ICDE, pp. 259\u2013271 (2022)","DOI":"10.1109\/ICDE53745.2022.00024"},{"key":"881_CR27","doi-asserted-by":"crossref","unstructured":"Pandey, S., Li, X.S., Buluc, A., Xu, J., Liu, H.: H-index: Hash-indexing for parallel triangle counting on gpus. In: IEEE High Performance Extreme Computing Conference (HPEC), pp. 1\u20137 (2019)","DOI":"10.1109\/HPEC.2019.8916492"},{"key":"881_CR28","doi-asserted-by":"crossref","unstructured":"Patel, S., Sowmya, K.S.: Comparative analysis of vertex cover computation algorithms for varied graphs. In: ICCSP (2014)","DOI":"10.1109\/ICCSP.2014.6950106"},{"key":"881_CR29","unstructured":"Schlegel, B., Willhalm, T., Lehner, W.: Fast sorted-set intersection using SIMD instructions. In: ADMS, pp. 1\u20138 (2011)"},{"key":"881_CR30","unstructured":"Schlegel, B., Willhalm, T., Lehner, W.: Fast sorted-set intersection using simd instructions. ADMS@ VLDB 1(8). (2011)"},{"key":"881_CR31","unstructured":"Shun, J.: Shared-memory parallelism can be simple, fast, and scalable. In: Morgan & Claypool"},{"key":"881_CR32","doi-asserted-by":"crossref","unstructured":"Shun, J., Tangwongsan, K.: Multicore triangle computations without tuning. In: ICDE, pp. 149\u2013160 (2015)","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"881_CR33","doi-asserted-by":"crossref","unstructured":"Tatikonda, S., Junqueira, F., Cambazoglu, B.B., Plachouras, V.: On efficient posting list intersection with multicore processors. In: Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 738\u2013739 (2009)","DOI":"10.1145\/1571941.1572104"},{"key":"881_CR34","doi-asserted-by":"crossref","unstructured":"Wang, R.L., Tang, Z., Xu, X.S.: An efficient algorithm for minimum vertex cover problem. IEEJ Transactions on Electronics Information & Systems 124(7), 1494\u20131499","DOI":"10.1541\/ieejeiss.124.1494"},{"key":"881_CR35","doi-asserted-by":"crossref","unstructured":"Wei, H., Yu, J.X., Lu, C., Lin, X.: Speedup graph processing by graph ordering. In: SIGMOD, pp. 1813\u20131828 (2016)","DOI":"10.1145\/2882903.2915220"},{"key":"881_CR36","doi-asserted-by":"crossref","unstructured":"Ye, X., Li, R., Dai, Q., Chen, H., Wang, G.: Lightning fast and space efficient k-clique counting. In: The ACM Web Conference, pp. 1191\u20131202 (2022)","DOI":"10.1145\/3485447.3512167"},{"issue":"10","key":"881_CR37","first-page":"1058","volume":"12","author":"Y Yuan","year":"2019","unstructured":"Yuan, Y., Lian, X., Wang, G., Ma, Y., Wang, Y.: Constrained shortest path query in a large time-dependent graph. PVLDB 12(10), 1058\u20131070 (2019)","journal-title":"PVLDB"},{"key":"881_CR38","doi-asserted-by":"crossref","unstructured":"Yuan, Y., Ma, D., Zhang, A., Wang, G.: Consistent subgraph matching over large graphs. In: International Conference on Data Engineering, pp. 2536\u20132548 (2022)","DOI":"10.1109\/ICDE53745.2022.00235"},{"key":"881_CR39","doi-asserted-by":"crossref","unstructured":"Yuan, Z., Peng, Y., Cheng, P., Han, L., Lin, X., Chen, L., Zhang, W.: Efficient $$k-\\text{ clique }$$ listing with set intersection speedup. In: ICDE, pp. 1955\u20131968 (2022)","DOI":"10.1109\/ICDE53745.2022.00192"},{"issue":"5","key":"881_CR40","first-page":"488","volume":"12","author":"X Zhang","year":"2019","unstructured":"Zhang, X., \u00d6zsu, T.: Correlation constraint shortest path over large multi-relation graphs. PVLDB 12(5), 488\u2013501 (2019)","journal-title":"PVLDB"},{"key":"881_CR41","doi-asserted-by":"crossref","unstructured":"Zheng, W., Wang, Q., Xu Yu, J., Cheng, H., Zou, L.: Efficient computation of a near-maximum independent set over evolving graphs. In: ICDE, pp. 869\u2013880 (2018)","DOI":"10.1109\/ICDE.2018.00083"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00881-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-024-00881-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00881-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T05:53:07Z","timestamp":1737957187000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-024-00881-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["881"],"URL":"https:\/\/doi.org\/10.1007\/s00778-024-00881-w","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2024,12,2]]},"assertion":[{"value":"8 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}