A breadth-first search algorithm for frequent itemsets based on vertical data layout
Preprint
- 12 August 2024
- preprint
- Published by Springer Nature in Research Square
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.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- A Bayesian method for the automatic extraction of meaningful clinical sequences from large clinical databasesComputer Methods and Programs in Biomedicine, 2023
- PartEclat: an improved Eclat-based frequent itemset mining algorithm on spark clusters using partition techniqueCluster Computing, 2022
- SR-Mine: Adaptive Transaction Compression Method for Frequent Itemsets MiningArabian Journal for Science and Engineering, 2021
- Data mining tools -a case study for network intrusion detectionMultimedia Tools and Applications, 2020
- An improved apriori algorithm based on support weight matrix for data mining in transaction databaseJournal of Ambient Intelligence and Humanized Computing, 2019
- Efficient frequent itemsets mining through sampling and information granulationEngineering Applications of Artificial Intelligence, 2017
- Consistently faster and smaller compressed bitmaps with RoaringSoftware: Practice and Experience, 2016
- DiffNodesets: An efficient structure for fast mining frequent itemsetsApplied Soft Computing, 2016
- Better bitmap performance with Roaring bitmapsSoftware: Practice and Experience, 2015
- Fast mining frequent itemsets using NodesetsExpert Systems with Applications, 2014