BloomEclat: Efficient Eclat Algorithm based on Bloom filter

Document Type : Research Paper

Authors

1 Department of Algorithms and Computation, School of Engineering Science, College of Engineering, University of Tehran, Iran

2 Department of Algorithms and Computation, School of Engineering Science, College of Engineering, University of Tehran, Iran.

Abstract

Eclat is an algorithm that finds frequent itemsets. It uses a vertical database and calculates item's support by intersecting transactions. However, Eclat suffers from the exponential time complexity of calculating the intersection of transactions. In this paper, a randomized algorithm called BloomEclat based on Bloom filter is presented to improve the Eclat algorithm complexity in finding frequent itemsets. Through Bloom Filter, an element’s membership to a set, can be checked and set operations such as intersection and union of two sets can be executed in a time efficient manner. By using these capabilities, Eclat algorithm’s intersecting problem can significantly improve. In BloomEclat algorithm with slight false positive error, the speed of the intersecting transactions is increased, and consequently the execution time is reduced.

Keywords

Journal of Algorithms and Computation
Volume 53, Issue 1
Winter and Spring 2021
Pages 197-208

Files

Share

How to cite

Statistics