Model Counting Meets F 0 Estimation
Open Access
- 9 August 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 48 (3) , 1-28
Abstract
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’s and computation of zeroth frequency moments ( F 0 ) for data streams. 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 F 0 computation. We design a recipe for translating algorithms developed for F 0 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 F 0 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 F 0 estimation with a simpler analysis.Keywords
Funding Information
- NSF (1934884, 1849048)
- National Research Foundation Singapore (NRF-NRFFAI1-2019-0002, NRF-NRFFAI1-2019-0004 and AISG-RP-2018-005)
- Amazon Research Award
- NUS ODPRT Grant (R-252-000-685-13)
- NSF Awards (CCF-184908, HDR:TRIPODS-1934884, CCF-2130608, CCF-1849053, HDR:TRIPODS-1934884, and CCF-2130536)
This publication has 53 references indexed in Scilit:
- Continuous sampling from distributed streamsJournal of the ACM, 2012
- Algorithms for distributed functional monitoringACM Transactions on Algorithms, 2011
- Two improved range-efficient algorithms for estimationTheoretical Computer Science, 2009
- SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONSInternational Journal of Computational Geometry & Applications, 2008
- Finding frequent items in data streamsTheoretical Computer Science, 2004
- Uniform Generation of NP-Witnesses Using an NP-OracleInformation and Computation, 2000
- An Optimal Algorithm for Monte Carlo EstimationSIAM Journal on Computing, 2000
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Monte-Carlo approximation algorithms for enumeration problemsJournal of Algorithms, 1989
- Probabilistic counting algorithms for data base applicationsJournal of Computer and System Sciences, 1985