{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:25Z","timestamp":1750220185958,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,5,31]],"date-time":"2022-05-31T00:00:00Z","timestamp":1653955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2022,5,31]]},"abstract":"<jats:p>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 computation of zeroth frequency moments (F0) for data streams.<\/jats:p>","DOI":"10.1145\/3542700.3542721","type":"journal-article","created":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T22:10:16Z","timestamp":1654121416000},"page":"87-94","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Model Counting Meets Distinct Elements in a Data Stream"],"prefix":"10.1145","volume":"51","author":[{"given":"A.","family":"Pavan","sequence":"first","affiliation":[{"name":"Iowa State University"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska, Lincoln"}]},{"given":"Arnab","family":"Bhattacharyya","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Kuldeep S.","family":"Meel","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]}],"member":"320","published-online":{"date-parts":[[2022,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_2_1_3_1","first-page":"623","volume-title":"Proc. of SODA","author":"Bar-Yossef Z.","year":"2002","unstructured":"Z. Bar-Yossef , R. Kumar , and D. Sivakumar . Reductions in streaming algorithms, with an application to counting triangles in graphs . In Proc. of SODA , pages 623 -- 632 . ACM\/SIAM , 2002 . Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proc. of SODA, pages 623--632. ACM\/SIAM, 2002."},{"key":"e_1_2_1_4_1","first-page":"106","volume-title":"Proceedings of the ninth annual ACM symposium on Theory of computing","author":"Carter J. L.","year":"1977","unstructured":"J. L. Carter and M. N. Wegman . Universal classes of hash functions . In Proceedings of the ninth annual ACM symposium on Theory of computing , pages 106 -- 112 . ACM, 1977 . J. L. Carter and M. N. Wegman. Universal classes of hash functions. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 106--112. ACM, 1977."},{"key":"e_1_2_1_5_1","volume-title":"Proc. of IJCAI","author":"Chakraborty S.","year":"2016","unstructured":"S. Chakraborty , K. S. Meel , and M. Y. Vardi . Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic SAT calls . In Proc. of IJCAI , 2016 . S. Chakraborty, K. S. Meel, and M. Y. Vardi. Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic SAT calls. In Proc. of IJCAI, 2016."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_16"},{"key":"e_1_2_1_7_1","volume-title":"Algorithms for distributed functional monitoring. ACM Transactions on Algorithms (TALG), 7(2):1--20","author":"Cormode G.","year":"2011","unstructured":"G. Cormode , S. Muthukrishnan , and K. Yi . Algorithms for distributed functional monitoring. ACM Transactions on Algorithms (TALG), 7(2):1--20 , 2011 . G. Cormode, S. Muthukrishnan, and K. Yi. Algorithms for distributed functional monitoring. ACM Transactions on Algorithms (TALG), 7(2):1--20, 2011."},{"key":"e_1_2_1_8_1","volume-title":"Continuous sampling from distributed streams. Journal of the ACM (JACM), 59(2):1--25","author":"Cormode G.","year":"2012","unstructured":"G. Cormode , S. Muthukrishnan , K. Yi , and Q. Zhang . Continuous sampling from distributed streams. Journal of the ACM (JACM), 59(2):1--25 , 2012 . G. Cormode, S. Muthukrishnan, K. Yi, and Q. Zhang. Continuous sampling from distributed streams. Journal of the ACM (JACM), 59(2):1--25, 2012."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315306"},{"key":"e_1_2_1_10_1","first-page":"271","volume-title":"Proc. of ICML","author":"Ermon S.","year":"2014","unstructured":"S. Ermon , C. P. Gomes , A. Sabharwal , and B. Selman . Low-density parity constraints for hashing-based discrete integration . In Proc. of ICML , pages 271 -- 279 , 2014 . S. Ermon, C. P. Gomes, A. Sabharwal, and B. Selman. Low-density parity constraints for hashing-based discrete integration. In Proc. of ICML, pages 271--279, 2014."},{"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":"W. Feng , T. P. Hayes , and Y. Yin . Distributed symmetry breaking in sampling (optimal distributed randomly coloring with fewer colors). arXiv preprint arXiv:1802.06953 , 2018 . W. Feng, T. P. Hayes, and Y. Yin. 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","volume-title":"Distributed Computing","author":"Feng W.","year":"2018","unstructured":"W. Feng , Y. Sun , and Y. Yin . What can be sampled locally ? Distributed Computing , pages 1 -- 27 , 2018 . W. Feng, Y. Sun, and Y. Yin. What can be sampled locally? Distributed Computing, pages 1--27, 2018."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212757"},{"key":"e_1_2_1_14_1","volume-title":"32nd International Symposium on Distributed Computing","author":"Fischer M.","year":"2018","unstructured":"M. Fischer and M. Ghaffari . A simple parallel and distributed sampling technique: Local glauber dynamics . In 32nd International Symposium on Distributed Computing , 2018 . M. Fischer and M. Ghaffari. A simple parallel and distributed sampling technique: Local glauber dynamics. In 32nd International Symposium on Distributed Computing, 2018."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/378580.378687","volume-title":"Proc. of SPAA","author":"Gibbons P. B.","year":"2001","unstructured":"P. B. Gibbons and S. Tirthapura . Estimating simple functions on the union of data streams. In A. L. Rosenberg, editor , Proc. of SPAA , pages 281 -- 291 . ACM, 2001 . P. B. Gibbons and S. Tirthapura. Estimating simple functions on the union of data streams. In A. L. Rosenberg, editor, Proc. of SPAA, pages 281--291. ACM, 2001."},{"key":"e_1_2_1_17_1","first-page":"2293","volume-title":"Proc. of IJCAI","author":"Gomes C. P.","year":"2007","unstructured":"C. P. Gomes , J. Hoffmann , A. Sabharwal , and B. Selman . From sampling to model counting . In Proc. of IJCAI , pages 2293 -- 2299 , 2007 . C. P. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman. From sampling to model counting. In Proc. of IJCAI, pages 2293--2299, 2007."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213596"},{"key":"e_1_2_1_19_1","first-page":"1","volume-title":"Constraints","author":"Ivrii A.","year":"2015","unstructured":"A. Ivrii , S. Malik , K. S. Meel , and M. Y. Vardi . On computing minimal independent support and its applications to sampling and counting . Constraints , pages 1 -- 18 , 2015 . A. Ivrii, S. Malik, K. S. Meel, and M. Y. Vardi. On computing minimal independent support and its applications to sampling and counting. Constraints, pages 1--18, 2015."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.35"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394809"},{"key":"e_1_2_1_24_1","volume-title":"In Proc. of FSTTCS","author":"Meel K. S.","year":"2017","unstructured":"K. S. Meel , A. A. Shrotri , and M. Y. Vardi . On hashing-based approaches to approximate dnf-counting . In In Proc. of FSTTCS , 2017 . K. S. Meel, A. A. Shrotri, and M. Y. Vardi. On hashing-based approaches to approximate dnf-counting. In In Proc. of FSTTCS, 2017."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/865"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643672"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453943"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186549.3186551"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011592"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808740"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213595"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214063"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3542700.3542721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3542700.3542721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:22Z","timestamp":1750186942000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3542700.3542721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,31]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,5,31]]}},"alternative-id":["10.1145\/3542700.3542721"],"URL":"https:\/\/doi.org\/10.1145\/3542700.3542721","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2022,5,31]]},"assertion":[{"value":"2022-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}