Finding interesting associations without support pruning

By Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, Cheng Yang. Proceedings / International Conference on Data Engineering, 2000

494 citations recorded by the source corpus.

Association rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of interest are relationships that occur very frequently. However, there are a number of applications, such as data mining, identification of similar Web documents, clustering and collaborative filtering, where the rules of interest have comparatively few instances in the data. In these cases, we must look for highly correlated items, or possibly even causal relationships between infrequent items. We develop a family of algorithms for solving this problem, employing a combination of random sampling and hashing techniques. We provide an analysis of the algorithms developed and conduct experiments on real and synthetic data to obtain a comparative performance analysis.

Subfields: Computational Theory and Mathematics, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/8dc4edd931773be37410fe96fee46d22c913b099

How researchers see this paper

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

In Computational Theory and Mathematics

In Information Systems

In Signal Processing

Citations in the corpus

GPLAG: detection of software plagiarism by program dependence graph analysis (2006, background): “There are studies on detection of other kinds of plagiarism, such as plagiarized research papers, homework answers, and Web pages [3].”
Guilt by association: large scale malware detection by mining file-relation graphs (2014, background): “1) form a locality-sensitive function family for the Jaccard similarity measure [9].”
Sequential Event Prediction with Association Rules (2011, unknown): “Some work (Cohen et al., 2001; Wang et al., 2001) aims to find high confidence rules, ignoring the support altogether.”
Foundations and Advances in Data Mining (2005, methodology): “Rendl in their works [16, 17] on graph partitioning.”
LSH forest: self-tuning indexes for similarity search (2005, methodology): “In [22], a Web crawl is pre-processed to construct an LSH-based index [7, 11] that maps each page p to a set of pages S that are similar to p above a certain threshold parameter.”
Discovering data quality rules (2008, methodology): “Although there are techniques for pruning and aggregating association rules, such as using closed frequent itemsets [25], seeking highly correlated itemsets [8], and dimension hierarchies, these techniques can still return a larger number of rules than our method.”
Locality-sensitive hashing scheme based on p-stable distributions (2004, background): “([10]) that uses locality s ensitive hashing to find similar column pairs in market-basket data, w ith the similarity exceeding a certain user specified threshold .”
Efficient exact set-similarity joins (2006, methodology): “9 . we can verify that I 1 = [1 , 1] , I 8 = [8 , 8] , I 9 = [9 , 10] , I 13 = [17 , 18] , and I 14 = [19 , 21] .”
Google news personalization: scalable online collaborative filtering (2007, background): “It is easy to show ([8, 4, 9]) that for a random permutation, chosen uniformly over the set of all permutations over S , the probability that two users will have the same hash function is exactly equal to their similarity or Jaccard coefficient.”
Detecting near-duplicates for web crawling (2007, background): “Several experimental studies have tested the efficacy of min-hash in various settings (Cohen et al [21] for associationrule mining, Chen et al [18] for selectivity estimation of boolean queries, Gionis et al [30] for indexing set-value predicates and Haveliwala [33] for web-clustering).”
Similarity estimation techniques from rounding algorithms (2002, methodology): “This was exploited later in several experimental papers: Cohen et al [14] for association-rule mining, Haveliwala et al [27] for clustering web documents, Chen et al [13] for selectivity estimation of boolean queries, Chen et al [12] for twig queries, and Gionis et al [22] for indexing set value”
Learning theory analysis for association rules and sequential event prediction (2013, background): “Some recent work (Cohen et al., 2001; Wang et al., 2001) attempts to avoid the support measure altogether.”
b-Bit Minwise Hashing for Estimating Three-Way Similarities (2010, background): “, [14]), a number of such pruning techniques leverage minwise hashing to prune pairs of items, but in many contexts (e.”