Using a knowledge cache for interactive discovery of association rules
Published 1 August 1999Open access
Biswadeep Nag, Prasad Deshpande, David J. DeWitt
Citations59
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proposes the use of a knowledge cache that can reduce the response time by several orders of magnitude and illustrates how the idea of caching can be readily extended to a broader class of problems such as the mining of generalized association rules.
Abstract
Association rule mining is a valuable decision support technique that can be used to analyze customer preferences, buying patterns, and product correlations. Current systems are however handicapped by the long processing times required by mining algorithms that make them unsuitable for interactive use. In this paper, we propose the use of a knowledge cache that can reduce the response time by several orders of magnitude. Most of the performance gain comes from the idea of guaranteed support that allows us to completely eliminate database accesses in a large number of cases. Using this cache, the time taken to answer a query is proportional to just the size of the result, rather than to the size of the database. Cache replacement is best done by a benefit-metric based strategy that can easily adapt to changing query patterns.
Keywords
Computer Science
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
Dynamic itemset counting and implication rules for market basket data
1,954 Citations1997Sergey Brin, Rajeev Motwani +2 more
A new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling and a new way of generating “implication rules” which are normalized based on both the antecedent and the consequent.
Future Generation Computer SystemsMining generalized association rules
1,617 Citations1997Ramakrishnan Srikant, Rakesh Agrawal
A new interest-measure for rules which uses the information in the taxonomy is presented, and given a user-specified “minimum-interest-level”, this measure prunes a large number of redundant rules.
An Efficient Algorithm for Mining Association Rules in Large Databases
1,598 Citations1995Ashoka Savasere, Edward Omiecinski +1 more
This paper presents an efficient algorithm for mining association rules that is fundamentally different from known algorithms and not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases.
An effective hash-based algorithm for mining association rules
1,412 Citations1995Jong Soo Park, Ming-Syan Chen⋆ +1 more
The number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck, and allows us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly.
Implementing data cubes efficiently
1,166 Citations1996Venky Harinarayan, Anand Rajaraman +1 more
This paper investigates the issue of which cells (views) to materialize when it is too expensive to materialized all views, and presents greedy algorithms that work off this lattice and determine a good set of views to materializing.
Sampling Large Databases for Association Rules
1,079 Citations1996Hannu Toivonen
New algorithms that reduce the database activity considerably by picking a Random sample, to find using this sample all association rules that probably hold in the whole database, and then to verify the results with the rest of the database.
Discovery of Multiple-Level Association Rules from Large Databases
920 Citations1995Jiawei Han, Yongjian Fu
A top-down progressive deepening method is developed for mining multiplelevel association rules from large transaction databases by extension of some existing association rule mining techniques.
Exploratory mining and pruning optimizations of constrained associations rules
713 Citations1998Raymond T. Ng, Laks V. S. Lakshmanan +2 more
An architecture that opens up the black-box, and supports constraint-based, human-centered exploratory mining of associations, and introduces and analyzes two properties of constraints that are critical to pruning: anti-monotonicity and succinctness.
Shoring up persistent applications
421 Citations1994Michael J. Carey, David J. DeWitt +10 more
The goals and motivation for SHORE are given, and some novel aspects of the SHORE architecture are described, including a symmetric peer-to-peer server architecture, server customization through an extensible value-added server facility, and support for scalability on multiprocessor systems.
Caching multidimensional queries using chunks
193 Citations1998Prasad Deshpande, Karthikeyan Ramasamy +2 more
Chunk-based caching allows fine granularity caching, and allows queries to partially reuse the results of previous queries with which they overlap, and a new organization for relational tables, which is called a “chunked file” is proposed.
ACM SIGMOD RecordTowards on-line analytical mining in large databases
149 Citations1998Jiawei Han
This article summarizes the research and development activities in the Intelligent Database Systems Research Lab in the last several years and shares the experiences and lessons with the readers.
Online generation of association rules
124 Citations2002Charų C. Aggarwal, Philip S. Yu
This work investigates the problem of online mining of association rules in a large database consisting of sales transactions and shows how to preprocess the data effectively in order to make it suitable for repeated online queries.
Online association rule mining
111 Citations1999Christian Hidber
Using a knowledge cache for interactive discovery of association rules
59 Citations1999Biswadeep Nag, Prasad Deshpande +1 more
This paper proposes the use of a knowledge cache that can reduce the response time by several orders of magnitude and illustrates how the idea of caching can be readily extended to a broader class of problems such as the mining of generalized association rules.