{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:26Z","timestamp":1750219826418,"version":"3.41.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T00:00:00Z","timestamp":1691539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["1934884, 1849048"],"award-info":[{"award-number":["1934884, 1849048"]}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"crossref","award":["NRF-NRFFAI1-2019-0002, NRF-NRFFAI1-2019-0004 and AISG-RP-2018-005"],"award-info":[{"award-number":["NRF-NRFFAI1-2019-0002, NRF-NRFFAI1-2019-0004 and AISG-RP-2018-005"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Amazon Research Award"},{"name":"NUS ODPRT Grant","award":["R-252-000-685-13"],"award-info":[{"award-number":["R-252-000-685-13"]}]},{"name":"NSF awards","award":["CCF-184908, HDR:TRIPODS-1934884, CCF-2130608, CCF-1849053, HDR:TRIPODS-1934884, and CCF-2130536"],"award-info":[{"award-number":["CCF-184908, HDR:TRIPODS-1934884, CCF-2130608, CCF-1849053, HDR:TRIPODS-1934884, and CCF-2130536"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            Constraint satisfaction problems (CSPs) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP\u2019s and computation of zeroth frequency moments (\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            ) for data streams.\n          <\/jats:p>\n          <jats:p>\n            Our investigations lead us to observe a striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            computation. We design a recipe for translating algorithms developed for\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            estimation to model counting, resulting in new algorithms for model counting. We also provide a recipe for transforming sampling algorithm over streams to constraint sampling algorithms. We then observe that algorithms in the context of distributed streaming can be transformed into distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields an algorithm for multidimensional range efficient\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            estimation with a simpler analysis.\n          <\/jats:p>","DOI":"10.1145\/3603496","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T11:07:05Z","timestamp":1687259225000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Model Counting Meets\n            <i>F<\/i>\n            <sub>0<\/sub>\n            Estimation"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1665-5266","authenticated-orcid":false,"given":"A.","family":"Pavan","sequence":"first","affiliation":[{"name":"Iowa State University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7959-4662","authenticated-orcid":false,"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska, Lincoln"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3648-5957","authenticated-orcid":false,"given":"Arnab","family":"Bhattacharyya","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9423-5270","authenticated-orcid":false,"given":"Kuldeep S.","family":"Meel","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]}],"member":"320","published-online":{"date-parts":[[2023,8,9]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Ralph Abboud Ismail Ilkan Ceylan and Thomas Lukasiewicz. 2019. Learning to reason: Leveraging neural networks for approximate DNF counting. arXiv:1904.02688. Retrieved from https:\/\/arxiv.org\/abs\/1904.02688."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66263-3_1"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_10"},{"key":"e_1_3_2_6_2","volume-title":"LDPC Codes for Discrete Integration","author":"Asteris Megasthenis","year":"2016","unstructured":"Megasthenis Asteris and Alexandros G. Dimakis. 2016. LDPC Codes for Discrete Integration. Technical Report. UT Austin."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_3_2_9_2","first-page":"623","volume-title":"Proceedings of the SODA","author":"Bar-Yossef Ziv","year":"2002","unstructured":"Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the SODA. ACM\/SIAM, 623\u2013632."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2885"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_3_2_12_2","unstructured":"Vladimir Braverman and Rafail Ostrovsky. 2010. Recursive sketching for frequency moments. arXiv:1011.2571. Retrieved from https:\/\/arxiv.org\/abs\/1011.2571."},{"key":"e_1_3_2_13_2","first-page":"106","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing","author":"Carter J. Lawrence","year":"1977","unstructured":"J. Lawrence Carter and Mark N. Wegman. 1977. Universal classes of hash functions. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing. ACM, 106\u2013112."},{"key":"e_1_3_2_14_2","first-page":"689","volume-title":"Proceedings of the AAAI","author":"Chakraborty Supratik","year":"2015","unstructured":"Supratik Chakraborty, Dror Fried, Kuldeep S. Meel, and Moshe Y. Vardi. 2015. From weighted to unweighted model counting. In Proceedings of the AAAI. 689\u2013695."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_40"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40627-0_18"},{"key":"e_1_3_2_17_2","volume-title":"Proceedings of the IJCAI","author":"Chakraborty S.","year":"2016","unstructured":"S. Chakraborty, K. S. Meel, and M. Y. Vardi. 2016. Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic SAT calls. In Proceedings of the IJCAI."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46681-0_26"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2004.1320018"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7131-9"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_16"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921667"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160163"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315306"},{"key":"e_1_3_2_27_2","first-page":"334","volume-title":"Proceedings of the ICML","author":"Ermon Stefano","year":"2013","unstructured":"Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, and Bart Selman. 2013. Taming the curse of dimensionality: Discrete integration by hashing and optimization. In Proceedings of the ICML. 334\u2013342."},{"key":"e_1_3_2_28_2","first-page":"271","volume-title":"Proceedings of the ICML","author":"Ermon S.","year":"2014","unstructured":"S. Ermon, C. P. Gomes, A. Sabharwal, and B. Selman. 2014. Low-density parity constraints for hashing-based discrete integration. In Proceedings of the ICML. 271\u2013279."},{"key":"e_1_3_2_29_2","unstructured":"Weiming Feng Thomas P. Hayes and Yitong Yin. 2018. Distributed symmetry breaking in sampling (optimal distributed randomly coloring with fewer colors). arXiv:1802.06953. Retrieved from https:\/\/arxiv.org\/abs\/1802.06953."},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"Weiming Feng Yuxin Sun and Yitong Yin. 2018. What can be sampled locally? Distributed Computing 33 3 (2020) 227\u2013253.","DOI":"10.1007\/s00446-018-0332-8"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212757"},{"key":"e_1_3_2_32_2","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing","author":"Fischer Manuela","year":"2018","unstructured":"Manuela Fischer and Mohsen Ghaffari. 2018. A simple parallel and distributed sampling technique: Local glauber dynamics. In Proceedings of the 32nd International Symposium on Distributed Computing."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002520"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/7503.003.0065"},{"key":"e_1_3_2_37_2","first-page":"2293","volume-title":"Proceedings of the IJCAI","author":"Gomes Carla P.","year":"2007","unstructured":"Carla P. Gomes, Joerg Hoffmann, Ashish Sabharwal, and Bart Selman. 2007. From sampling to model counting. In Proceedings of the IJCAI. 2293\u20132299."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213596"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060621"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-015-9204-z"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/11534.11537"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","unstructured":"R. M. Karp and M. Luby. 1983. Monte-Carlo algorithms for enumeration and reliability problems. Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS) 55\u201364.","DOI":"10.1109\/SFCS.1983.35"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142507"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.102"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.68"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394809"},{"key":"e_1_3_2_50_2","volume-title":"Proceedings of the FSTTCS","author":"Meel Kuldeep S.","year":"2017","unstructured":"Kuldeep S. Meel, Aditya A. Shrotri, and Moshe Y. Vardi. 2017. On hashing-based approaches to approximate DNF-counting. In Proceedings of the FSTTCS."},{"key":"e_1_3_2_51_2","doi-asserted-by":"crossref","unstructured":"Kuldeep S. Meel Aditya A. Shrotri and Moshe Y. Vardi. 2019. Not all FPRASs are equal: demystifying FPRASs for DNF-counting. Constraints An Int. J. 24 3\u20134 (2019) 211\u2013233.","DOI":"10.1007\/s10601-018-9301-x"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/865"},{"key":"e_1_3_2_53_2","first-page":"1143","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"Monemizadeh Morteza","year":"2010","unstructured":"Morteza Monemizadeh and David P. Woodruff. 2010. 1-pass relative-error L \\({}_{\\mbox{p}}\\) -sampling with applications. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010. Moses Charikar (Ed.), SIAM, 1143\u20131160."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1137\/050643672"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458311"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453943"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186549.3186551"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31423-1_3"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.5555\/1980502.1980514"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53288-8_22"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011592"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02777-2_24"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808740"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.10.031"},{"key":"e_1_3_2_65_2","volume-title":"Proceedings of the PODS 2021","author":"Chakraborty Kuldeep S. Meel , N. V. Vinodchandran , Sourav","year":"2021","unstructured":"Kuldeep S. Meel , N. V. Vinodchandran , Sourav Chakraborty. 2021. Estimating size of union of sets in streaming model. In Proceedings of the PODS 2021."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213595"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214063"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0218-3"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2490"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9584-4"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3603496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:26Z","timestamp":1750178786000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,9]]},"references-count":70,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3603496"],"URL":"https:\/\/doi.org\/10.1145\/3603496","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2023,8,9]]},"assertion":[{"value":"2022-02-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-28","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}