Approximate Substring Matching over Uncertain Strings

Summary: Proposes (k, tau)-matching semantics for approximate substring matching over uncertain strings modeled by probability distributions. Introduces multilevel filtering using signature-distance and two bound-based verification algorithms to reduce indexing and verification costs, validated on real and synthetic datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10306
Venue: VLDB
Year: 2011
Pagerank: 4.5768015e-05
Overall Rank: 8,143 | 43.36%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Tingjian Ge
2. Zheng Li

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,306	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5435639e-05
11,904	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1945683e-05
11,979	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
4,901	Probabilistic String Similarity Joins	2010	SIGMOD	5.8411648e-05
6,351	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB	5.1005697e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05
9,932	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	4.2500258e-05
4,988	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	5.783959e-05
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
3,868	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	6.6822543e-05
5,813	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3170565e-05
8,306	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5435639e-05
11,979	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.1945683e-05
7,708	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6721808e-05