How to Quickly Find a Witness

Summary: Introduce the "witness" concept to decouple traversal from pruning in constrained itemset mining, enabling existing algorithms to handle arbitrary, non-(anti)monotone/convertible constraints. Provide efficient witness-finding for stable functions and variance constraints (var(S) ≤ c, ≥ c) with heuristics to accelerate mining. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1298
Venue: PODS
Year: 2003
Pagerank: 5.093636e-05
Overall Rank: 12,812 | 12.10%
DOI: 10.1145/773153.773180

Incoming Non-self Citations Over Time

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

Authors

1. Daniel Kifer (Cornell University)
2. Johannes Gehrke (Cornell University)
3. Cristian Bucila (Cornell University)
4. Walker White (University of Dallas)

BibTeX Citation

@inproceedings{kifer_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{How to Quickly Find a Witness}},
        url = {https://dl.acm.org/doi/10.1145/773153.773180},
        doi = {10.1145/773153.773180},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kifer, Daniel and Gehrke, Johannes and Bucila, Cristian and White, Walker},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
1,535	Exploratory Mining and Pruning Optimizations of Constrained Association Rules	1998	SIGMOD	0.00010463058
4,969	Optimization of Constrained Frequent Set Queries with 2-variable Constraints	1999	SIGMOD	6.4201643e-05
6,578	Data mining, Hypergraph Transversals, and Machine Learning	1997	PODS	5.8364579e-05
6,719	Exploratory Mining via Constrained Frequent Set Queries	1999	SIGMOD	5.7944032e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,366	On Differentially Private Frequent Itemset Mining	2013	VLDB
2	7,657	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB
3	1,421	PrivBasis: Frequent Itemset Mining with Differential Privacy	2012	VLDB
4	12,150	Beyond Itemsets: Mining Frequent Featuresets over Structured Items	2015	VLDB
5	4,969	Optimization of Constrained Frequent Set Queries with 2-variable Constraints	1999	SIGMOD
6	1,535	Exploratory Mining and Pruning Optimizations of Constrained Association Rules	1998	SIGMOD
7	6,719	Exploratory Mining via Constrained Frequent Set Queries	1999	SIGMOD
8	5,179	An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets	2009	PODS
9	9,212	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS
10	12,882	Mining Frequent Itemsets Using Support Constraints	2000	VLDB