Apriori algorithm: Difference between revisions

Revision as of 15:00, 26 October 2020

Revision as of 13:09, 18 January 2021

Line 133:

Apriori, while historically significant, suffers from a number of inefficiencies or trade-offs, which have spawned other algorithms. Candidate generation generates large numbers of subsets (The algorithm attempts to load up the candidate set, with as many as possible subsets before each scan of the database). Bottom-up subset exploration (essentially a breadth-first traversal of the subset lattice) finds any maximal subset S only after all <math>2^{|S|}-1</math> of its proper subsets.

The algorithm scans the database too many times, which reduces the overall performance. Due to this, the algorithm assumes that the database is Permanentpermanently in the memory.

Also, both the time and space complexity of this algorithm are very high: <math>O(2^{|D|})</math>, thus exponential, where <math>|D|</math> is the horizontal width (the total number of items) present in the database.