hide
Free keywords:
-
Abstract:
Let be a database of transactions on n attributes, where each attribute
specifies a (possibly empty) real closed interval . Given an integer threshold
t, a multi-dimensional interval I=([a1,b1], ..., [an,bn]) is called t-frequent,
if (every component interval of) I is contained in (the corresponding component
of) at least t transactions of and otherwise, I is said to be t-infrequent. We
consider the problem of generating all minimal t-infrequent multi-dimensional
intervals, for a given database and threshold t. This problem may arise, for
instance, in the generation of association rules for a database of
time-dependent transactions. We show that this problem can be solved in
quasi-polynomial time. This is established by developing a quasi- polynomial
time algorithm for generating maximal independent elements for a set of vectors
in the product of lattices of intervals, a result which may be of independent
interest. In contrast, the generation problem for maximal frequent intervals
turns out to be NP-hard.
