# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Finding All Minimal Infrequent Multi-dimensional Intervals

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Elbassioni, K. (2006). Finding All Minimal Infrequent Multi-dimensional Intervals.
In *LATIN 2006: Theoretical Informatics, 7th Latin American Symposium* (pp. 423-434). Berlin,
Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-22DE-C

##### 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.