Business Intelligence

Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace

Free registration required

Executive Summary

As the monotone duality problem is equivalent to a number of problems in the areas of databases, data mining, and knowledge discovery, the results presented here yield new complexity results for those problems, too. For example, it follows from the authors' results that whenever for a Boolean-valued relation (whose attributes represent items), a number of maximal frequent item sets and a number of minimal infrequent item sets are known, then it can be decided in quadratic log space whether there exist additional frequent or infrequent set.

  • Format: PDF
  • Size: 461.46 KB