A breadth-first search algorithm for frequent itemsets based on vertical data layout

Abstract Frequent itemset mining, a pivotal technique in the field of data mining, is aimed at identifying items that frequently co-occur in transaction databases, thereby enabling the extraction of valuable patterns and associations within large datasets. Algorithms utilizing vertical data layout typically employ depth-first search for extracting frequent itemsets. However, leveraging anti-monotonicity property to constrain the search space poses challenges. Additionally, memory consumption can be substantial, particularly when using a low minimum support threshold. In this paper, we propose integrating hashmap and list data structures to store frequent itemsets and represent the search space more efficiently. Furthermore, we introduce a breadth-first search-based approach for generating candidate itemsets while simultaneously pruning them based on anti-monotonicity principles. Support counting is performed using bitwise operators within the concept and technique of vertical database representation. Building upon two formats of vertical databases (Tidset and Diffset), we present two novel algorithms: Tidset-BFS and Diffset-BFS respectively. To evaluate their performance, extensive experiments are conducted, comparing them with a prominent negFIN algorithm across various real-world and synthetic datasets. The experimental results demonstrate that our proposed algorithms exhibit significantly improved efficiency across most datasets.