Finding All Minimal Infrequent Multi-dimensional Intervals

attribute specifies a (possibly empty) real closed interval
$I=[a,b]\subseteq \RR$. Given an integer threshold $t$, a multi-dimensional interval $I=([a_1,b_1],$ $\ldots, [a_n,b_n])$ is called $t$-{\em frequent}, if (every component interval of) $I$ is contained in (the corresponding component of) at least $t$ transactions of $\cD$ and otherwise, $I$ is said to be $t$-{\em infrequent}.
We consider the problem of finding all {\em minimal} $t$-infrequent multi-dimensional intervals, for a given database $\cD$ 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 {\em maximal} frequent intervals turns out to be NP-hard.