Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Conference Paper

Finding All Minimal Infrequent Multi-dimensional Intervals


Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

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