MPI-INF D1 Publications: Proceedings Article: Finding All Minimal Infrequent Multi-dimensional Intervals

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

Options:

Goto entry point

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

URL of the conference:
URL for downloading the paper:	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:


(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=([a₁,b₁], ..., [a_n,b_n]) 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

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

Attachment Section