{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:01:34Z","timestamp":1740808894929,"version":"3.38.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:p>\n            Graph workloads pose a particularly challenging problem for query optimizers. They typically feature large queries made up of entirely many-to-many joins with complex correlations. This puts significant stress on traditional cardinality estimation methods which generally see catastrophic errors when estimating the size of queries with only a handful of joins. To overcome this, we propose COLOR, a framework for subgraph cardinality estimation which applies insights from graph compression theory to produce a compact summary that captures the global topology of the data graph. Further, we identify several key optimizations that enable tractable estimation over this summary even for large query graphs. We then evaluate several designs within this framework and find that they improve accuracy by up to 10\n            <jats:sup>3<\/jats:sup>\n            \u00d7 over all competing methods while maintaining fast inference, a small memory footprint, efficient construction, and graceful degradation under updates.\n          <\/jats:p>","DOI":"10.14778\/3705829.3705834","type":"journal-article","created":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:21:06Z","timestamp":1740784866000},"page":"130-143","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation"],"prefix":"10.14778","volume":"18","author":[{"given":"Kyle","family":"Deeds","sequence":"first","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diandre","family":"Sabale","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moe","family":"Kayali","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,28]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132921"},{"key":"e_1_2_1_4_1","unstructured":"Bradley R. Bebee Daniel Choi Ankit Gupta Andi Gutmans Ankesh Khandelwal Yigit Kiran Sainath Mallidi Bruce McGaughy Mike Personick Karthik Rajan Simone Rondelli Alexander Ryazanov Michael Schmidt Kunal Sengupta Bryan B. Thompson Divij Vaidya and Shawn Wang. 2018. Amazon Neptune: Graph Data Management in the Cloud. In Proceedings of the ISWC 2018 Posters & Demonstrations Industry and Blue Sky Ideas Tracks co-located with 17th International Semantic Web Conference (ISWC 2018) Monterey USA October 8th - to - 12th 2018 (CEUR Workshop Proceedings) Marieke van Erp Medha Atre Vanessa L\u00f3pez Kavitha Srinivas and Carolina Fortuna (Eds.) Vol. 2180. CEUR-WS.org. https:\/\/ceur-ws.org\/Vol-2180\/paper-79.pdf"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604932"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-019-00558-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3182392"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"key":"e_1_2_1_10_1","volume-title":"Lee","author":"Deutsch Alin","year":"2019","unstructured":"Alin Deutsch, Yu Xu, Mingxi Wu, and Victor E. Lee. 2019. TigerGraph: A Native MPP Graph Database. CoRR abs\/1901.08248 (2019). arXiv:1901.08248 http:\/\/arxiv.org\/abs\/1901.08248"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04329-1_21"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781139028868"},{"key":"e_1_2_1_14_1","volume-title":"Recent Advances on the Graph Isomorphism Problem. CoRR abs\/2011.01366","author":"Grohe Martin","year":"2020","unstructured":"Martin Grohe and Daniel Neuen. 2020. Recent Advances on the Graph Isomorphism Problem. CoRR abs\/2011.01366 (2020). arXiv:2011.01366 https:\/\/arxiv.org\/abs\/2011.01366"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372123"},{"key":"e_1_2_1_16_1","volume-title":"Review - Access Path Selection in a Relational Database Management System. ACM SIGMOD Digit. Rev. 1","author":"Haas Laura M.","year":"1999","unstructured":"Laura M. Haas. 1999. Review - Access Path Selection in a Relational Database Management System. ACM SIGMOD Digit. Rev. 1 (1999). https:\/\/dblp.org\/db\/journals\/dr\/Haas99a.html"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-55814-7_12"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186014"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"803","DOI":"10.14778\/3574245.3574264","article-title":"Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality","volume":"16","author":"Kayali Moe","year":"2022","unstructured":"Moe Kayali and Dan Suciu. 2022. Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality. Proc. VLDB Endow. 16, 4 (2022), 803--815. https:\/\/www.vldb.org\/pvldb\/vol16\/p803-kayali.pdf","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457246"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284551"},{"key":"e_1_2_1_24_1","volume-title":"Understanding the hardness of approximate query processing with joins. arXiv preprint arXiv:2010.00307","author":"Liu Tianyu","year":"2020","unstructured":"Tianyu Liu and Chi Wang. 2020. Understanding the hardness of approximate query processing with joins. arXiv preprint arXiv:2010.00307 (2020)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371319"},{"key":"e_1_2_1_26_1","volume-title":"Borgwardt","author":"Morris Christopher","year":"2021","unstructured":"Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt. 2021. Weisfeiler and Leman go Machine Learning: The Story so far. CoRR abs\/2112.09992 (2021). arXiv:2112.09992"},{"key":"e_1_2_1_27_1","unstructured":"Inc. Neo4j. 2007. https:\/\/neo4j.com\/"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23786-7_57"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00548-x"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313556"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"1697","DOI":"10.14778\/3654621.3654635","article-title":"Cardinality Estimation of Subgraph Matching","volume":"17","author":"Shin Wonseok","year":"2024","unstructured":"Wonseok Shin, Siwoo Song, Kunsoo Park, and Wook-Shin Han. 2024. Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach. Proc. VLDB Endow. 17, 7 (2024), 1697--1709. https:\/\/www.vldb.org\/pvldb\/vol17\/p1697-park.pdf","journal-title":"A Filtering-Sampling Approach. Proc. VLDB Endow."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186003"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526163"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_41_1","volume-title":"PRESTO: probabilistic cardinality estimation for RDF queries based on subgraph overlapping. arXiv preprint arXiv:1801.06408","author":"Wang Xin","year":"2018","unstructured":"Xin Wang, Eugene Siow, Aastha Madaan, and Thanassis Tiropanis. 2018. PRESTO: probabilistic cardinality estimation for RDF queries based on subgraph overlapping. arXiv preprint arXiv:1801.06408 (2018)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-023-00781-5"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3705829.3705834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:25:03Z","timestamp":1740785103000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3705829.3705834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10.14778\/3705829.3705834"],"URL":"https:\/\/doi.org\/10.14778\/3705829.3705834","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"2025-02-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}