Mining Statistically Significant Substrings using the Chi-Square Statistic

Summary: Presents an O(n^{3/2}) algorithm (with high probability) to locate the MSS by chi-square under a Bernoulli model. Covers MSS variants; analyzes asymptotics and experiments, with applications in cryptology, finance, and sports vs heuristics. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10344
Venue: VLDB
Year: 2012
Pagerank: 4.6642145e-05
Overall Rank: 7,737 | 46.18%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Mayank Sachan
2. Arnab Bhattacharya

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,572	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.005963e-05
7,597	Oracle Workload Intelligence	2015	SIGMOD	4.7007801e-05
9,580	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3234342e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,708	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6721808e-05
3,454	Traversing Itemset Lattices with Statistical Metric Pruning	2000	PODS	7.0778482e-05
4,307	Mining Periodic Patterns with Gap Requirement from Sequences	2005	SIGMOD	6.2885419e-05
5,813	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3170565e-05
9,580	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3234342e-05
5,245	Fast and Scalable Mining of Time Series Motifs with Probabilistic Guarantees	2022	VLDB	5.6067361e-05
8,306	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5435639e-05
11,039	Efficient Discovery of Significant Patterns with Few-Shot Resampling	2024	VLDB	4.1945683e-05
4,829	An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets	2009	PODS	5.8925807e-05
6,572	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.005963e-05