On the complexity of generating maximal frequent and minimal infrequent sets

E. Boros, V. Gurvich, L. Khachiyan, K. Makino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

57 Scopus citations

Abstract

Let A be an m × n binary matrix, t ∈ {1,…,m} be a threshold, and ε > 0 be a positive parameter. We show that given a family of O(nε) maximal t-frequent column sets for A, it is NP-complete to decide whether A has any further maximal t-frequent sets, or not, even when the number of such additional maximal t-frequent column sets may be exponentially large. In contrast, all minimal t-infrequent sets of columns of A can be enumerated in incremental quasi-polynomial time. The proof of the latter result follows from the inequality α ≤ (m-t +1)β, where α and β are respectively the numbers of all maximal t-frequent and all minimal t-infrequent sets of columns of the matrix A. We also discuss the complexity of generating all closed t-frequent column sets for a given binary matrix.

Original languageEnglish (US)
Title of host publicationSTACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsHelmut Alt, Afonso Ferreira
PublisherSpringer Verlag
Pages133-141
Number of pages9
ISBN (Electronic)9783540432838
DOIs
StatePublished - 2002
Event19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 - Antibes - Juan les Pins, France
Duration: Mar 14 2002Mar 16 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2285

Other

Other19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002
Country/TerritoryFrance
CityAntibes - Juan les Pins
Period3/14/023/16/02

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Data mining
  • Dualization
  • Frequent sets
  • Hitting sets
  • Independent sets
  • Infrequent sets
  • Transversals

Fingerprint

Dive into the research topics of 'On the complexity of generating maximal frequent and minimal infrequent sets'. Together they form a unique fingerprint.

Cite this