A pattern-growth approach for mining maximal fault-tolerant frequent itemsets

Abstract Mining fault-tolerant (FT) frequent itemsets in noisy datasets is more challenging than conventional frequent itemset mining due to the high cost of evaluating fault-tolerance conditions. Consequently, mining maximal fault-tolerant frequent itemsets (FT-MFIs) is particularly important, as they provide a concise representation of all frequent patterns while eliminating redundancy, which is crucial in noisy datasets where error tolerance must be considered. Existing approaches for mining FT-MFIs are predominantly based on Apriori-style candidate generation and test, which suffer from exponential candidate growth, multiple dataset scans, and limited scalability. As a novel contribution, this work is the first to propose a pattern-growth framework for mining FT-MFIs. We introduce an algorithm that constructs a fault-tolerant FP-tree (FT-FP-tree) to compress transactions with common prefixes and evaluate tolerance conditions in a single pass. Additionally, new techniques for transaction mapping and conditional pattern extraction enhance the efficiency and scalability of the mining process. Experimental results on benchmark datasets demonstrate that the proposed approach achieves substantial reductions in execution time compared to all existing algorithms, while also showing improved memory efficiency relative to other pattern-growth based algorithms. This establishes pattern growth as a practical and scalable solution for fault-tolerant frequent itemset discovery.