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: 10307
Venue: VLDB
Year: 2011
Pagerank: 4.5724134e-05
Overall Rank: 8,146 | 43.39%
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,300	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5392079e-05
11,912	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1905499e-05
11,987	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.1905499e-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.00044946098
4,907	Probabilistic String Similarity Joins	2010	SIGMOD	5.8365853e-05
6,351	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB	5.0956764e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05
9,933	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	4.245954e-05
4,878	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	5.8537044e-05
3,779	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7709545e-05
3,869	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	6.6776679e-05
5,825	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3119504e-05
8,300	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5392079e-05
11,987	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.1905499e-05
7,707	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6676985e-05