Abstract | ||
---|---|---|
We consider the problem of how one can estimate the support of Boolean queries given a collection of frequent itemsets. We describe an algorithm that truncates the inclusion-exclusion sum to include only the frequencies of known itemsets, give a bound for its performance on disjunctions of attributes that is smaller than the previously known bound, and show that this bound is in fact achievable. We also show how to generalize the algorithm to approximate arbitrary Boolean queries. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1007/11615576_16 | Constraint-Based Mining and Inductive Databases |
Keywords | Field | DocType |
frequent itemsets,approximate arbitrary boolean query,boolean formula,frequent set,inclusion-exclusion sum,known itemsets | Maximum satisfiability problem,Discrete mathematics,Constraint satisfaction,Conjunctive query,Computer science,Product term,Association rule learning,Boolean algebra,True quantified Boolean formula,Boolean expression | Conference |
ISBN | Citations | PageRank |
3-540-31331-1 | 1 | 0.36 |
References | Authors | |
9 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jouni K. Seppänen | 1 | 124 | 9.09 |
Heikki Mannila | 2 | 6595 | 1495.69 |