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: h1933a5f71c46a25b
Venue: PODS
Year: 2004
Pagerank: 5.2905577e-05
Overall Rank: 8,718 | 41.39%
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
13,016	Differential Constraints	2005	PODS	4.9793485e-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.00064420972
68	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037958605
912	Efficiently Mining Long Patterns from Databases	1998	SIGMOD	0.00013115246

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,172	Mining Frequent Itemsets Using Support Constraints	2000	VLDB
2	5,084	Optimization of Constrained Frequent Set Queries with 2-variable Constraints	1999	SIGMOD
3	124	Approximate Frequency Counts over Data Streams	2002	VLDB
4	7,810	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB
5	1,453	PrivBasis: Frequent Itemset Mining with Differential Privacy	2012	VLDB
6	8,094	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS
7	2,416	On Differentially Private Frequent Itemset Mining	2013	VLDB
8	4,778	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB
9	7,668	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS
10	9,390	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS