2015/02/09 by Slimane Oulad-Naoui, Oulad-Naoui, Slimane, Hadda Cherroun +3
Computer Science · #68Q25 #Advanced Algebra and Logic #Computational Complexity (cs.CC) #Data Mining Algorithms and Applications #Databases (cs.DB) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #H.2.8 #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.1502.02642
openalex publication_date 2015/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is generally well agreed that developing a unifying theory is one of the most important issues in Data Mining research. In the last two decades, a great deal of work has been devoted to the algorithmic aspects of the Frequent Itemset (FI) Mining problem. We are motivated by the need for formal modeling in the field. Thus, we introduce and analyze, in this theoretical study, a new model for the FI mining task. Indeed, we encode the itemsets as words over an ordered alphabet, and state this problem by a formal series over the counting semiring (ℕ,+,×,0,1), whose range constitutes the itemsets and the coefficients are their supports. This formalism offers many advantages in both fundamental and practical aspects: the introduction of a clear and unified theoretical framework through which we can express the main FI-approaches, the possibility of their generalization to mine other more complex objects, and their incrementalisation or parallelisation; in practice, we explain how this problem can be seen as that of word recognition by an automaton, allowing an efficient implementation in O(|Q|) space and O(|FL||Q|]) time, where Q is the set of states of the automaton used for representing the data, and FL the set of prefixial longest FI.