Computational Complexity of Itemset Frequency Satisfiability

Summary: FREQSAT: given interval constraints on itemset frequencies, decide existence of a transaction database realizing them; FREQSAT ≡ Probabilistic SAT and NP‑complete. Frequencies not finitely axiomatizable; conditional frequencies/confidence expressible; bounded-duplication variants are PP‑hard, with consequences for mining and privacy. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1316
Venue: PODS
Year: 2004
Pagerank: 5.4119882e-05
Overall Rank: 8,551 | 41.34%
DOI: 10.1145/1055558.1055580

Incoming Non-self Citations Over Time

Authors

1. Toon Calders (University of Antwerp)

BibTeX Citation

@inproceedings{calders_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Computational Complexity of Itemset Frequency Satisfiability}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055580},
        doi = {10.1145/1055558.1055580},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Calders, Toon},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,726	Differential Constraints	2005	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0006567919
70	Privacy-Preserving Data Mining	2000	SIGMOD	0.0003804755
886	Efficiently Mining Long Patterns from Databases	1998	SIGMOD	0.0001340645

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,882	Mining Frequent Itemsets Using Support Constraints	2000	VLDB
2	4,969	Optimization of Constrained Frequent Set Queries with 2-variable Constraints	1999	SIGMOD
3	122	Approximate Frequency Counts over Data Streams	2002	VLDB
4	7,657	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB
5	1,421	PrivBasis: Frequent Itemset Mining with Differential Privacy	2012	VLDB
6	7,926	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS
7	2,366	On Differentially Private Frequent Itemset Mining	2013	VLDB
8	4,683	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB
9	7,522	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS
10	9,212	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS