NDLI: Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees

Please wait, while we are loading the content...

Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees

Content Provider	ACM Digital Library
Author	Upfal, Eli Riondato, Matteo
Copyright Year	2014
Abstract	The tasks of extracting $(top-\textit{K})$ Frequent Itemsets (FIs) and Association Rules (ARs) are fundamental primitives in data mining and database applications. Exact algorithms for these problems exist and are widely used, but their running time is hindered by the need of scanning the entire dataset, possibly multiple times. High-quality approximations of FIs and ARs are sufficient for most practical uses. Sampling techniques can be used for fast discovery of approximate solutions, but works exploring this technique did not provide satisfactory performance guarantees on the quality of the approximation due to the difficulty of bounding the probability of under- or oversampling any one of an unknown number of frequent itemsets. We circumvent this issue by applying the statistical concept of Vapnik-Chervonenkis (VC) dimension to develop a novel technique for providing tight bounds on the sample size that guarantees approximation of the $(top-\textit{K})$ FIs and ARs within user-specified parameters. The resulting sample size is linearly dependent on the VC-dimension of a range space associated with the dataset. We analyze the VC-dimension of this range space and show that it is upper bounded by an easy-to-compute characteristic quantity of the dataset, the $\textit{d-index},$ namely, the maximum integer $\textit{d}$ such that the dataset contains at least $\textit{d}$ transactions of length at least $\textit{d}$ such that no one of them is a superset of or equal to another. We show that this bound is tight for a large class of datasets. The resulting sample size is a significant improvement over previous known results. We present an extensive experimental evaluation of our technique on real and artificial datasets, demonstrating the practicality of our methods, and showing that they achieve even higher quality approximations than what is guaranteed by the analysis.
Starting Page	1
Ending Page	32
Page Count	32
File Format	PDF
ISSN	15564681
e-ISSN	1556472X
DOI	10.1145/2629586
Volume Number	8
Issue Number	4
Journal	ACM Transactions on Knowledge Discovery from Data (TKDD)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-08-29
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Association rules VC-dimension Data mining Frequent itemsets Sampling
Content Type	Text
Resource Type	Article
Subject	Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient discovery of association rules and frequent itemsets through sampling with tight performance guarantees

Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees

AEfficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees1

Fast and memory efficient mining of frequent closed itemsets

TFP: an efficient algorithm for mining top-k frequent closed itemsets

An efficient algorithm for frequent itemsets in data mining

A transaction mapping algorithm for frequent itemsets mining

GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets

Mining top-K frequent itemsets through progressive sampling

Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees

Similar Documents

Efficient discovery of association rules and frequent itemsets through sampling with tight performance guarantees

Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees

AEfficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees1

Fast and memory efficient mining of frequent closed itemsets

TFP: an efficient algorithm for mining top-k frequent closed itemsets

An efficient algorithm for frequent itemsets in data mining

A transaction mapping algorithm for frequent itemsets mining

GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets

Mining top-K frequent itemsets through progressive sampling

Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees