2015 FastandMemoryEfficientSignifica

• (Llinares-López et al., 2015) ⇒ Felipe Llinares-López, Mahito Sugiyama, Laetitia Papaxanthos, and Karsten Borgwardt. (2015). “Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783363

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Fast+and+Memory-Efficient+Significant+Pattern+Mining+via+Permutation+Testing
• http://dl.acm.org/citation.cfm?id=2783258.2783363&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; multiple hypothesis testing; p-value; significant pattern mining; westfall-young permutation

Abstract

We present a novel algorithm for significant pattern mining, Westfall-Young light. The target patterns are statistically significantly enriched in one of two classes of objects. Our method corrects for multiple hypothesis testing and correlations between patterns via the Westfall-Young permutation procedure, which empirically estimates the null distribution of pattern frequencies in each class via permutations.

In our experiments, Westfall-Young light dramatically outperforms the current state-of-the-art approach, both in terms of runtime and memory efficiency on popular real-world benchmark datasets for pattern mining. The key to this efficiency is that, unlike all existing methods, our algorithm does not need to solve the underlying frequent pattern mining problem a new for each permutation and does not need to store the occurrence list of all frequent patterns. Westfall-Young light opens the door to significant pattern mining on large datasets that previously involved prohibitive runtime or memory costs.

Our code is available from http://www.bsse.ethz.ch/mlcb/research/machine-learning/wylight.html

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 FastandMemoryEfficientSignifica	Karsten Borgwardt Felipe Llinares-López Mahito Sugiyama Laetitia Papaxanthos			Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing				10.1145/2783258.2783363		2015