MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Elbassioni, Khaled M.dblp
Editor(s):
Correa, José R.
Hevia, Alejandro
Kiwi, Marcos A.		dblp
dblp
dblp
Not MPII Editor(s):
Correa, José R.
Hevia, Alejandro
Kiwi, Marcos A.
BibTeX cite key*:
Elbassioni2006c
Title, Booktitle
Title*:
Finding All Minimal Infrequent Multi-dimensional Intervals
Booktitle*:
LATIN 2006: Theoretical Informatics, 7th Latin American Symposium
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/a33230160k820415/fulltext.pdf
Event Address*:
Valdivia, Chile
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
20 March 2006
Event End Date:
24 March 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Volume:
3887
Number:
Month:
Pages:
423-434
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
URL for the Abstract:
http://www.springerlink.com/content/a33230160k820415/
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2006c,
AUTHOR = {Elbassioni, Khaled M.},
 EDITOR = {Correa, Jos{\'e} R. and Hevia, Alejandro and Kiwi, Marcos A.},
 TITLE = {Finding All Minimal Infrequent Multi-dimensional Intervals},
 BOOKTITLE = {LATIN 2006: Theoretical Informatics, 7th Latin American Symposium},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {3887},
 PAGES = {423--434},
 ADDRESS = {Valdivia, Chile},
}

Entry last modified by Christine Kiesel, 05/02/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni		Created
04/05/2006 02:41:17 AM
Revisions
5.
4.
3.
2.
1.		Editor(s)
Christine Kiesel
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
02.05.2007 15:29:32
2007-04-11 11:17:10
07.02.2007 15:04:42
07.02.2007 15:00:27
04/05/2006 02:58:13 PM