Turbo-charging vertical mining of large databases

By Pradeep Shenoy, Jayant R. Haritsa, S. Sudarshan, Gaurav Bhalotia, Mayank Bawa, Devavrat Shah. ACM SIGMOD Conference, 2000

337 citations recorded by the source corpus.

In a vertical representation of a market-basket database, each item is associated with a column of values representing the transactions in which it is present. The association-rule mining algorithms that have been recently proposed for this representation show performance improvements over their classical horizontal counterparts, but are either efficient only for certain database sizes, or assume particular characteristics of the database contents, or are applicable only to specific kinds of database schemas. We present here a new vertical mining algorithm called VIPER, which is general-purpose, making no special requirements of the underlying database. VIPER stores data in compressed bit-vectors called “snakes” and integrates a number of novel optimizations for efficient snake generation, intersection, counting and storage. We analyze the performance of VIPER for a range of synthetic database workloads. Our experimental results indicate significant performance gains, especially for large databases, over previously proposed vertical and horizontal mining algorithms. In fact, there are even workload regions where VIPER outperforms an optimal, but practically infeasible, horizontal mining algorithm.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

View Paper: https://www.semanticscholar.org/paper/de4b8191e2bcd56b9d2abebff2373a88bae46c76

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

MAFIA: a maximal frequent itemset algorithm (2005, methodology): “The VIPER algorithm has shown that a method based on a vertical layout can sometimes outperform even the optimal method using a horizontal layout [25].”
Association mining (2006, methodology): “DFT trie construction Novel accrual techniques Pre.x-based equivalence relations Maximal cliques Maximal cliques Novel accrual Inclusion of diffsets AprioriHybrid Hybrid VIPER DCI kDCI Apriori-Brave Pattern Growth Algorithms Agrawal & Srikant Hipp et al. Shenoy et al. Orlando et al. Lucchese e”
MAFIA: a maximal frequent itemset algorithm for transactional databases (2001, methodology): “There is much research on methods for generating all frequent itemsets efficiently [4, 5, 6, 10, 11, 13, 19, 25, 26, 28, 31] or just the set of maximal frequent itemsets [1, 7, 12, 16, 32].”
Frequent substructure-based approaches for classifying chemical compounds (2003, methodology): “For every candidate, FSG takes the intersection of TID-lists of its parents, and performs the subgraph isomorphism only on the transactions contained in the resulting TID-list.”
Frequent sub-structure-based approaches for classifying chemical compounds (2005, methodology): “Finally, for determining the actual frequency of each subgraph, FSG reduces the number of subgraph isomorphism operations by using TID-lists [29], [ 74 ], [83], [84] to keep track of the set of transactions that supported the frequent patterns discovered at the previous level of the lattice.”
Efficient algorithms for mining closed itemsets and their lattice structure (2005, methodology): “Mining algorithms using the vertical format have been shown to be very effective and usually outperform horizontal approaches [8], [18], [19], [22].”
DATA MINING TECHNIQUES (2003, methodology): “One of the first efficient approach was the Apriori algorithm [3], which inspired the development of many other efficient algorithms[14,35, 50, 58, 71, 73, 81].”
Survey on Frequent Pattern Mining (2003, background): “Note that for both layouts, it is also possible to use the exact bit-strings from the binary matrix [34, 29].”
Fast vertical mining using diffsets (2003, methodology): “We compare the new dEclat method against Eclat [22], the classic Apriori [1] and recent Viper [20] algorithm.”
Frequent subgraph discovery (2001, methodology): “For this reason, FSG instead uses Transaction ID (TID) lists, proposed by [8, 19, 27, 25, 26].”
Efficiently mining frequent trees in a forest (2002, background): “idlists (which can be further compressed [2, 9 ]).”
CHARM: An Efficient Algorithm for Closed Itemset Mining (2002, methodology): “For cases where even the memory requirement of depth-first search and diffsets exceed available memory, it is straightforward to modify CHARM to write/read temporary diffsets to/from disk, as in [17].”
An efficient algorithm for discovering frequent subgraphs (2004, methodology): “For this reason, FSG instead uses transaction identifier (TID) lists, proposed by [13], [40], [47].”
Maintaining Data Privacy in Association Rule Mining (2002, methodology): “For this purpose, in principle we could use, after the modi(cid:12)cations described below, any of the numerous association rule mining algorithms proposed in the literature (e.g. [3, 13, 9, 16]).”