FewRS speeds up statistical significance testing by 100x for data mining
New algorithm needs only a handful of resampled datasets instead of thousands.
A key bottleneck in knowledge discovery is evaluating whether data mining results are statistically significant or just noise. Traditional resampling-based approaches, while widely applicable, require generating and analyzing thousands of synthetic datasets, making them impractical for large data or complex analyses. In a new paper accepted to KDD 2026, Leonardo Pellegrina and Fabio Vandin (University of Padova) propose FewRS (Few-Shot Resampling), a method that slashes the number of resampled datasets needed while providing rigorous guarantees on the probability of false discoveries.
FewRS derives a novel bound on the supremum deviation of test statistics, which allows it to operate with an extremely small number of resamples — sometimes just a few dozen instead of thousands. The authors tested FewRS on pattern mining and network analysis tasks, demonstrating up to two orders of magnitude (100x) reduction in running time compared to state-of-the-art resampling methods, without sacrificing statistical power. This breakthrough makes statistically-sound data mining feasible on large-scale real-world datasets where it was previously computationally prohibitive.
- FewRS reduces the number of resampled datasets from thousands to an extremely small number using a novel supremum deviation bound.
- Up to 100x faster running time (two orders of magnitude) compared to existing resampling methods on pattern mining and network analysis.
- Provides rigorous statistical guarantees on false discovery probability while maintaining high statistical power.
Why It Matters
Enables scalable, statistically-valid data mining on huge datasets, saving compute while preventing false discoveries.