Abstract
The authors consider databases in which each attribute takes values from a partially ordered set (poset). This allows one to model a number of interesting scenarios arising in different applications, including quantitative databases, taxonomies, and databases in which each attribute is an interval representing the duration of a certain event occurring over time. A natural problem that arises in such circumstances is the following: given a database D and a threshold value t, find all collections of "generalizations" of attributes which are "supported" by less than t transactions from D. They call such collections infrequent elements. Due to monotonicity, they can reduce the output size by considering only minimal infrequent elements. We study the complexity of finding all minimal infrequent elements for some interesting classes of posets. The authors show how this problem can be applied to mining association rules in different types of databases, and to finding "sparse regions" or "holes" in quantitative data or in databases recording the time intervals during which a re-occurring event appears over time. Their main focus will be on these applications rather than on the correctness or analysis of the given algorithms.
| Original language | British English |
|---|---|
| Title of host publication | Rare Association Rule Mining and Knowledge Discovery |
| Subtitle of host publication | Technologies for Infrequent and Critical Event Detection |
| Pages | 98-116 |
| Number of pages | 19 |
| DOIs | |
| State | Published - 2009 |