Best-first search–based approach for mining top-k closed frequent itemsets from uncertain databases

Abstract

Uncertain data mining has become critical due to data generated by sensor networks, RFID systems, and data integration platforms. Mining top-k closed frequent itemsets from uncertain databases is particularly challenging because probabilistic support evaluation is expensive and the search space grows exponentially. Most existing methods rely on depth-first search (DFS) traversal, which explores candidates in enumeration order and often discovers high-support patterns late, leading to weak pruning and costly closure verification. This paper proposes TUFCI, a best-first-search-based algorithm for mining top-k closed frequent itemsets from uncertain databases. TUFCI explores candidates in descending order of probabilistic support using a priority queue, enabling early discovery of strong patterns, rapid threshold elevation, and safe early termination. Support-ordered exploration also improves closure checking by prioritizing supersets most likely to violate the closure property, thereby reducing redundant superset examinations. Experimental results demonstrate that TUFCI significantly outperforms DFS-based approaches in runtime and reduces the number of closure checks, especially on dense datasets.