{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:33Z","timestamp":1775638473344,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT)","award":["NRF-2021R1A2B5B03001551"],"award-info":[{"award-number":["NRF-2021R1A2B5B03001551"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3457246","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:39Z","timestamp":1624036959000},"page":"964-976","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation"],"prefix":"10.1145","author":[{"given":"Kyoungmin","family":"Kim","sequence":"first","affiliation":[{"name":"Pohang University of Science and Technology, Pohang, Republic of Korea"}]},{"given":"Hyeonji","family":"Kim","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology, Pohang, Republic of Korea"}]},{"given":"George","family":"Fletcher","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}]},{"given":"Wook-Shin","family":"Han","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology, Pohang, Republic of Korea"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.60"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_3_2_2_3_1","volume-title":"VLDB","volume":"1","author":"Aboulnaga Ashraf","year":"2001","unstructured":"Ashraf Aboulnaga , Alaa R Alameldeen , and Jeffrey F Naughton . 2001 . Estimating the selectivity of XML path expressions for internet scale applications . In VLDB , Vol. 1 . Citeseer, 591--600. Ashraf Aboulnaga, Alaa R Alameldeen, and Jeffrey F Naughton. 2001. Estimating the selectivity of XML path expressions for internet scale applications. In VLDB , Vol. 1. Citeseer, 591--600."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0287-3"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_3_2_2_6_1","volume-title":"10th Innovations in Theoretical Computer Science Conference, ITCS 2019","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi , Michael Kapralov , and Sanjeev Khanna . 2019 . A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling . In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019 , January 10 --12 , 2019, San Diego, California, USA (LIPIcs, Vol. 124), Avrim Blum (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 6:1--6:20. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.6 10.4230\/LIPIcs.ITCS.2019.6 Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. 2019. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10--12, 2019, San Diego, California, USA (LIPIcs, Vol. 124), Avrim Blum (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 6:1--6:20. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.6"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_3_2_2_9_1","volume-title":"Mining Graphlet Counts in Online Social Networks. In IEEE 16th International Conference on Data Mining, ICDM 2016, December 12--15, 2016","author":"Chen Xiaowei","year":"2016","unstructured":"Xiaowei Chen and John C. S. Lui . 2016 . Mining Graphlet Counts in Online Social Networks. In IEEE 16th International Conference on Data Mining, ICDM 2016, December 12--15, 2016 , Barcelona, Spain , , Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, and Xindong Wu (Eds.). IEEE Computer Society, 71--80. https:\/\/doi.org\/10.1109\/ICDM. 2016 .0018 10.1109\/ICDM.2016.0018 Xiaowei Chen and John C. S. Lui. 2016. Mining Graphlet Counts in Online Social Networks. In IEEE 16th International Conference on Data Mining, ICDM 2016, December 12--15, 2016, Barcelona, Spain , , Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, and Xindong Wu (Eds.). IEEE Computer Society, 71--80. https:\/\/doi.org\/10.1109\/ICDM.2016.0018"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188810"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2007.74"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.06.005"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888912000331"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809985"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_3_2_2_20_1","unstructured":"Viktor Leis Bernhard Radke Andrey Gubichev Alfons Kemper and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling.. In Cidr .  Viktor Leis Bernhard Radke Andrey Gubichev Alfons Kemper and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling.. In Cidr ."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093754.3093763"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68234-9_38"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083638"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_3_2_2_30_1","first-page":"187","article-title":"Population based establishment sample surveys: The Horvitz-Thompson estimator","volume":"25","author":"Sirken Monroe","year":"1999","unstructured":"Monroe Sirken and Iris Shimizu . 1999 . Population based establishment sample surveys: The Horvitz-Thompson estimator . Survey Methodology , Vol. 25 , 2 (1999), 187 -- 192 . Monroe Sirken and Iris Shimizu. 1999. Population based establishment sample surveys: The Horvitz-Thompson estimator. Survey Methodology , Vol. 25, 2 (1999), 187--192.","journal-title":"Survey Methodology"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186003"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2008.06.001"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_3_2_2_37_1","volume-title":"GSI: GPU-friendly Subgraph Isomorphism. In 36th IEEE International Conference on Data Engineering, ICDE 2020","author":"Zeng Li","year":"2020","unstructured":"Li Zeng , Lei Zou , M. Tamer \u00d6 zsu, Lin Hu , and Fan Zhang . 2020 . GSI: GPU-friendly Subgraph Isomorphism. In 36th IEEE International Conference on Data Engineering, ICDE 2020 , Dallas, TX, USA, April 20--24 , 2020 . IEEE, 1249--1260. https:\/\/doi.org\/10.1109\/ICDE48307.2020.00112 10.1109\/ICDE48307.2020.00112 Li Zeng, Lei Zou, M. Tamer \u00d6 zsu, Lin Hu, and Fan Zhang. 2020. GSI: GPU-friendly Subgraph Isomorphism. In 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20--24, 2020 . IEEE, 1249--1260. https:\/\/doi.org\/10.1109\/ICDE48307.2020.00112"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1830252.1830274"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457246","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3457246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:06Z","timestamp":1750195686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":39,"alternative-id":["10.1145\/3448016.3457246","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3457246","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}