--- title: "Improving efficiency of Apriori" subject: "Data Mining" chapter: 4 key: "semester_7/data_mining:apriori-efficiency" source: https://www.bctengineer.com/q/semester_7/data_mining/apriori-efficiency site: BCT Engineering --- # Improving efficiency of Apriori Data Mining · Chapter 4: Association Analysis - Asked in: year not given - Video: [Improving The Efficiency of Apriori - Frequent Pattern Mining- Data Mining and Business Intelligence](https://www.youtube.com/watch?v=As2uJlRzcYQ) — Ekeeda - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/data_mining/apriori-efficiency - Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4 ## Question Write a short note on improving the efficiency of apriori algorithm. ## Short answer Hash-based counting reduces 2-itemset candidates; transaction reduction skips barren transactions; partitioning scans only twice; sampling works on a subset. Dynamic itemset counting adjusts scans. Vertical data format (TID-lists) and FP-growth avoid candidate generation entirely. ## Answer The basic Apriori algorithm is slow because it scans the database many times and generates and counts a huge number of candidate itemsets. Several techniques improve its efficiency. 1. **Hash-based itemset counting (DHP)**: while counting 1-itemsets, hash every 2-itemset of each transaction into buckets of a hash table with bucket counts. A candidate 2-itemset whose bucket count is below min_sup cannot be frequent and is removed, which cuts C₂ greatly. 2. **Transaction reduction**: a transaction that contains no frequent k-itemset cannot contain any frequent (k+1)-itemset, so it is marked or removed from later scans. 3. **Partitioning**: divide the database into n partitions that fit in memory. Find the local frequent itemsets in each partition; any globally frequent itemset must be frequent in at least one partition. Only **two scans** of the database are needed (second scan counts the union of local frequent itemsets). 4. **Sampling**: mine a random sample with a lowered min_sup; verify with one scan of the whole database. It saves time but can miss some itemsets. 5. **Dynamic itemset counting (DIC)**: add new candidate itemsets at any start point during a scan, once all their subsets are known to be frequent, to reduce the number of scans. 6. **Vertical data format (Eclat)**: store the TID-list of each item and intersect TID-lists to get supports, so no repeated scans of the horizontal database are needed. 7. **Pattern-growth (FP-growth)**: avoid candidate generation by using an FP-tree. 8. Also: higher min_sup, better data structures (hash trees for candidate counting), and parallel/distributed implementation. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How does DHP reduce candidate 2-itemsets? A. Candidates whose bucket count is below min_sup are removed B. It deletes transactions with fewer than 2 items C. It hashes transactions into clusters D. It increases min_sup Answer: A. If the bucket count is less than min_sup, no pair in the bucket can be frequent. (Key point: Hash-based counting) 2. Why can a transaction be removed from later scans? A. It has already been counted twice B. It contains no frequent k-itemset, so it cannot contain a frequent (k+1)-itemset C. It contains frequent 1-itemsets D. It is the longest transaction Answer: B. Such transactions cannot contribute to larger frequent itemsets. (Key point: Transaction reduction) 3. Why does partitioning need only two scans? A. Each partition is scanned once while ignoring support B. It uses a sample only C. Any globally frequent itemset is frequent in at least one partition; second scan counts the union D. It builds an FP-tree Answer: C. Local frequent itemsets form candidates, which are verified in a second scan. (Key point: Partitioning) 4. What is a drawback of sampling? A. It needs many scans B. It generates more candidates C. It requires hash tables D. It may miss some frequent itemsets Answer: D. The sample may not represent the whole database, even with lowered support. (Key point: Sampling) ## Related in Data Mining - [Association analysis and Apriori pruning](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aassociation-apriori-pruning) — Data Mining, chapter 4, asked 2× - [Apriori on 8 transactions, 25% support](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-b65-transactions) — Data Mining, chapter 4 - [Apriori on four transactions, support 2](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-y63-min-support-2) — Data Mining, chapter 4 - [Short note: Apriori and its drawbacks](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-note-drawbacks) — Data Mining, chapter 4 - [Apriori advantages and disadvantages](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-pros-cons) — Data Mining, chapter 4 - [FP-Growth and Apriori disadvantage](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-growth-vs-apriori) — Data Mining, chapter 4 ## Related in other subjects - [Fast decoupled method approximations and algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Afast-decoupled-approximations) — Power System Analysis II, chapter 2 - [Efficiency of quick sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aquick-sort-efficiency) — Data Structure and Algorithm, chapter 7, asked 2× - [Efficiency of straight selection sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aselection-sort-efficiency) — Data Structure and Algorithm, chapter 7 - [Measures of efficiency with standard curves](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aefficiency-measures-curve) — Data Structure and Algorithm, chapter 9