Title
Itemset frequency satisfiability : complexity and axiomatization Itemset frequency satisfiability : complexity and axiomatization
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Amsterdam ,
Subject
Computer. Automation
Source (journal)
Theoretical computer science. - Amsterdam
Volume/pages
394(2008) :1-2 , p. 84-111
ISSN
0304-3975
0304-3975
ISI
000255221900004
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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 itemset-interval 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 NP-complete. 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.
Full text (open access)
https://repository.uantwerpen.be/docman/irua/69720c/5632.pdf
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000255221900004&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000255221900004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000255221900004&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle