Title 



Itemset frequency satisfiability : complexity and axiomatization
 
Author 


  
Abstract 



Computing frequent itemsets is one of the most prominent problems in data mining. We study the following related problem, called FREQSAT, in depth: given some itemsetinterval pairs, does there exist a database such that for every pair the frequency of the itemset falls into the interval? This problem is shown to be NPcomplete. The problem is then further extended to include arbitrary Boolean expressions over items and conditional frequency expressions in the form of association rules. We also show that, unless P equals NP, the related function problem  find the best interval for an itemset under some frequency constraints cannot be approximated efficiently. Furthermore, it is shown that FREQSAT is recursively axiomatizable, but that there cannot exist an axiomatization of finite arity. (C) 2007 Elsevier B.V. All rights reserved.   
Language 



English
 
Source (journal) 



Theoretical computer science.  Amsterdam  
Publication 



Amsterdam : 2008
 
ISSN 



03043975
 
Volume/pages 



394:12(2008), p. 84111
 
ISI 



000255221900004
 
Full text (Publishers DOI) 


  
Full text (open access) 


  
