{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:14Z","timestamp":1750219814641,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"9","license":[{"start":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T00:00:00Z","timestamp":1692748800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2023,9]]},"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 CSPs and the computation of the number of distinct elements in a data stream, also known as the zeroth frequency moment (\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            ) of a data stream.\n          <\/jats:p>\n          <jats:p>Our investigations lead us to observe striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and distinct elements computation. We design a recipe for the translation of algorithms developed for distinct elements estimation to that of model counting, resulting in new algorithms for model counting. 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 distinct elements 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.<\/jats:p>","DOI":"10.1145\/3607824","type":"journal-article","created":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T14:51:48Z","timestamp":1692802308000},"page":"95-102","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Model Counting Meets Distinct Elements"],"prefix":"10.1145","volume":"66","author":[{"given":"A.","family":"Pavan","sequence":"first","affiliation":[{"name":"Iowa State University, Ames, Iowa, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska-Lincoln, Lincoln, Nebraska, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnab","family":"Bhattacharyya","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kuldeep S.","family":"Meel","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,23]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","series-title":"Proceedings of RANDOM (2002)","volume-title":"Counting distinct elements in a data stream","author":"Bar-Yossef Z.","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D., Trevisan, L. Counting distinct elements in a data stream. In Volume 2483 of Proceedings of RANDOM (2002), Springer, Cambridge, USA, 1--10."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of SODA","author":"Bar-Yossef Z.","year":"2002","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of SODA (2002), ACM\/SIAM, NY, 623--632."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing","author":"Carter J.L.","year":"1977","unstructured":"Carter, J.L., Wegman, M.N. Universal classes of hash functions. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (1977), ACM, NY, 106--112."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of IJCAI","author":"Chakraborty","year":"2016","unstructured":"Chakraborty,, S., Meel, K.S., Vardi, M.Y. Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic SAT calls. In Proceedings of IJCAI (2016), IJCAI\/AAAI Press, New York, USA."},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/978-3-540-39658-1_16"},{"key":"e_1_2_1_7_1","volume-title":"Algorithms for distributed functional monitoring. ACM Trans. Algorithms (TALG) 7, 2","author":"Cormode G.","year":"2011","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K. Algorithms for distributed functional monitoring. ACM Trans. Algorithms (TALG) 7, 2 (2011), 1--20."},{"key":"e_1_2_1_8_1","volume-title":"Continuous sampling from distributed streams. J. ACM (JACM) 59, 2","author":"Cormode G.","year":"2012","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K., Zhang, Q. Continuous sampling from distributed streams. J. ACM (JACM) 59, 2 (2012), 1--25."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1137\/S0097539797315306"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of ICML","author":"Ermon S.","year":"2014","unstructured":"Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B. Low-density parity constraints for hashing-based discrete integration. In Proceedings of ICML (2014), JMLR, Beijing, China, 271--279."},{"key":"e_1_2_1_11_1","volume-title":"Distributed symmetry breaking in sampling (optimal distributed randomly coloring with fewer colors). arXiv preprint arXiv:1802.06953","author":"Feng W.","year":"2018","unstructured":"Feng, W., Hayes, T.P., Yin, Y. Distributed symmetry breaking in sampling (optimal distributed randomly coloring with fewer colors). arXiv preprint arXiv:1802.06953 (2018)."},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"What can be sampled locally?","volume":"33","author":"Feng W.","year":"2018","unstructured":"Feng, W., Sun, Y., Yin, Y. What can be sampled locally? Distrib. Comput. 33 (2018), 1--27.","journal-title":"Distrib. Comput."},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/3212734.3212757"},{"volume-title":"32nd International Symposium on Distributed Computing (2018)","author":"Fischer M.","unstructured":"Fischer, M., Ghaffari, M. A simple parallel and distributed sampling technique: Local glauber dynamics. In 32nd International Symposium on Distributed Computing (2018) Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, New Orleans, USA.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_16_1","first-page":"291","article-title":"Estimating simple functions on the union of data streams. In Proceedings of SPAA. A. L. Rosenberg, ed. ACM","volume":"281","author":"Gibbons P.B.","year":"2001","unstructured":"Gibbons, P.B., Tirthapura, S. Estimating simple functions on the union of data streams. In Proceedings of SPAA. A. L. Rosenberg, ed. ACM, NY, 2001, 281--291.","journal-title":"NY"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of IJCAI","author":"Gomes C.P.","year":"2007","unstructured":"Gomes, C.P., Hoffmann, J., Sabharwal, A., Selman, B. From sampling to model counting. In Proceedings of IJCAI (2007), IJCAI\/AAAI Press, Hyderabad, India, 2293--2299."},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/2213556.2213596"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1007\/s10601-015-9204-z"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/1807085.1807094"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1109\/SFCS.1983.35"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/0196-6774(89)90038-2"},{"volume-title":"Proceedings of LICS (2020)","author":"Meel K.S.","unstructured":"Meel, K.S., Akshay, S. Sparse hashing for scalable approximate model counting: Theory and practice. In Proceedings of LICS (2020) ACM, Saarbr\u00fccken, Germany.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of FSTTCS (2017)","author":"Meel K.S.","unstructured":"Meel, K.S., Shrotri, A.A., Vardi, M.Y. On hashing-based approaches to approximate dnf-counting. In Proceedings of FSTTCS (2017) Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Kanpur, India.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","series-title":"Proceedings of IJCAI (2019)","volume-title":"Not all fprass are equal: Demystifying fprass for dnf-counting (extended abstract)","author":"Meel K.S.","unstructured":"Meel, K.S., Shrotri, A.A., Vardi, M.Y. Not all fprass are equal: Demystifying fprass for dnf-counting (extended abstract). In Volume 8 of Proceedings of IJCAI (2019), IJCAI, Macau, China."},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1137\/050643672"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.14778\/1453856.1453943"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/3186549.3186551"},{"volume-title":"Proceedings of AAAI Conference on Artificial Intelligence (AAAI) (2019)","author":"Soos M.","unstructured":"Soos, M., Meel, K.S. Bird: Engineering an efficient cnf-xor sat solver and its applications to approximate model counting. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI) (2019) AAAI Press, Honolulu, USA.","key":"e_1_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/800061.808740"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/2213556.2213595"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1137\/0208032"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/2213977.2214063"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607824","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607824","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607824","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:05Z","timestamp":1750178765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607824"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,23]]},"references-count":33,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["10.1145\/3607824"],"URL":"https:\/\/doi.org\/10.1145\/3607824","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2023,8,23]]},"assertion":[{"value":"2023-08-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}