We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A time-efficient breadth-first level-wise lattice-traversal algorithm to discover rare itemsets.
- Authors
Troiano, Luigi; Scibelli, Giacomo
- Abstract
In this paper we face the problem of searching for rare itemsets. A main issue regards the strategy to adopt in exploring the power set lattice. Assuming a power set lattice with full set at the top and empty set at the bottom, the most of the algorithms adopt a bottom-up exploration, i.e. moving from smaller to larger sets. Although this approach is advantageous in the case of frequent itemsets, it might not be worth being used for rare itemsets, as they occur on the top of the lattice. We propose Rarity, a top-down breadth-first level-wise algorithm. Experimental results and comparisons are illustrated in order to provide a quantitative characterization of algorithm performances and complexity. Application to some UCI benchmark and real world datasets is provided. An algorithm parallelization is outlined. Experiments showed that this approach takes advantage of finding all rare non-zero itemsets in less time than other solutions, at expenses of higher memory demand.
- Subjects
LATTICE theory; COMPUTATIONAL complexity; PARALLEL algorithms; VIRTUAL reality; MACHINE learning
- Publication
Data Mining & Knowledge Discovery, 2014, Vol 28, Issue 3, p773
- ISSN
1384-5810
- Publication type
Article
- DOI
10.1007/s10618-013-0304-3