Model Counting meets F0 Estimation

Summary: Bridges CSP model counting and streaming F0 estimation, providing a recipe to translate F0 algorithms into new (including distributed) model-counting algorithms. Also casts F0 as #DNF counting, unifying streaming analyses and yielding a simpler state-of-the-art multidimensional range-efficient F0 estimator. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1838
Venue: PODS
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,631 | 20.21%
DOI: 10.1145/3452021.3458311

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. A. Pavan (Iowa State University)
2. N. V. Vinodchandran (University of Nebraska–Lincoln)
3. Arnab Bhattacharyya (National University of Singapore)
4. Kuldeep S. Meel (National University of Singapore)

BibTeX Citation

@inproceedings{pavan_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Model Counting meets F0 Estimation}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458311},
        doi = {10.1145/3452021.3458311},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Pavan, A. and Vinodchandran, N. V. and Bhattacharyya, Arnab and Meel, Kuldeep S.},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,528	Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size	2022	PODS	5.093636e-05
11,640	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
1,433	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.0001080304
1,752	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.8358116e-05
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
3,856	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	7.0690791e-05
4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.5226838e-05
11,640	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	885	Finding Frequent Items in Data Streams	2008	VLDB
2	5,516	Distributed Set-Expression Cardinality Estimation	2004	VLDB
3	12,669	A Simple and Efficient Estimation Method for Stream Expression Cardinalities	2007	VLDB
4	11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS
5	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
6	10,181	Representation Obliviousness and Pseudodeterminism in Streaming Algorithms	2026	PODS
7	10,156	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS
8	2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
9	11,640	Estimating the Size of Union of Sets in Streaming Models	2021	PODS
10	122	Approximate Frequency Counts over Data Streams	2002	VLDB