# Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing

arXiv: https://arxiv.org/abs/1502.04315 · HTML: https://mlsanity.com/paper/1502.04315/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2015.

## Built on by (most cited first, 8 of 8)

- [Label-Descriptive Patterns and Their Application to Characterizing Classification Errors](https://mlsanity.com/paper/2110.09599/) (2021)
- [Finding Interpretable Class-Specific Patterns through Efficient Neural Search](https://mlsanity.com/paper/2312.04311/) (2023)
- [Differentially Describing Groups of Graphs](https://mlsanity.com/paper/2201.04064/) (2021)
- [Efficient Discovery of Significant Patterns with Few-Shot Resampling](https://mlsanity.com/paper/2406.11803/) (2024)
- [Alice and the Caterpillar: A more descriptive null model for assessing data mining results](https://mlsanity.com/paper/2506.09764/) (2025)
- [Learning High-Order Interactions via Targeted Pattern Search](https://mlsanity.com/paper/2102.12974/) (2021)
- [Few-Shot Resampling for Scalable Statistically-Sound Data Mining](https://mlsanity.com/paper/2606.11235/) (2026)
- [NxN E-valuation: Hypothesis Certification via a Conformal CRT Null](https://mlsanity.com/paper/2608.06621/) (2026)

## Abstract (arXiv)

We present a novel algorithm, Westfall-Young light, for detecting patterns, such as itemsets and subgraphs, which are statistically significantly enriched in one of two classes. Our method corrects rigorously for multiple hypothesis testing and correlations between patterns through 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 in terms of both 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 neither needs to solve the underlying frequent itemset mining problem anew for each permutation nor needs to store the occurrence list of all frequent patterns. Westfall-Young light opens the door to significant pattern mining on large datasets that previously led to prohibitive runtime or memory costs.