Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2014) | last year (2013) | two years ago (2012) | Notes URL

Action:

login to update

Options:








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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Attachment SectionAttachment Section