TR98-061 Authors: Robert H. Sloan, Ken Takata, György Turán

Publication: 13th October 1998 18:28

Downloads: 1785

Keywords:

Given a Boolean matrix and a threshold t, a subset of the

columns is frequent if there are at least t rows having a 1 entry in

each corresponding position. This concept is used in the algorithmic,

combinatorial approach to knowledge discovery and data mining. We

consider the complexity aspects of frequent sets. An explicit family

of subsets is given that requires exponentially many rows to be

represented as the family of frequent sets of a matrix, with any

threshold. Examples are given of families that can be represented by

a small matrix with threshold t, but that require a significantly

larger matrix if the threshold is less than t. We also discuss the

connections of these problems to circuit complexity and the existence

of efficient listing algorithms.