Itemset frequency satisfiability : complexity and axiomatization

T. Calders

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    16 Citaten (Scopus)
    1 Downloads (Pure)

    Samenvatting

    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 -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 equals , 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.
    Originele taal-2Engels
    Pagina's (van-tot)84-111
    TijdschriftTheoretical Computer Science
    Volume394
    Nummer van het tijdschrift1-2
    DOI's
    StatusGepubliceerd - 2008

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Itemset frequency satisfiability : complexity and axiomatization'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit