English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Finding All Minimal Infrequent Multi-dimensional Intervals

MPS-Authors
/persons/resource/persons44374

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
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: https://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.