Finding all minimal infrequent multi-dimensional intervals

Let D be a database of transactions on n attributes, where each attribute specifies a (possibly empty) real closed interval I = [a,b] ⊆ ℝ. Given an integer threshold t, a multi-dimensional interval I = ([a₁, b₁], . . . ,[a_n, b_n]) is called t-frequent, if (every component interval of) I is contained in (the corresponding component of) at least t transactions of D 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 D 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.