Mining Associations by Linear Inequalities
Tsay Young Lin · 2005
The main theorem is: generalized associations of a relational table can be found by a finite set of linear inequalities within polynomial time. It is derived from the following three results, which were established in ICDMO'02 and are re-developed here. They are: (1) isomorphic theorem: isomorphic relations have isomorphic patterns. Such an isomorphism classifies relational tables into isomorphic classes. (2) A variant of the classical bitmaps indexes uniquely exists in each isomorphic class. We take it as the canonical model of the class. (3) All possible attributes/features can be generated by a generalized procedure of the classical AOG (attribute oriented generalization). Then, (4) the main theorem for canonical model is established. By isomorphism theorem, we had the final result (5).