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: hdb8125d1790d5b35
Venue: VLDB
Year: 2011
Pagerank: 5.3612871e-05
Overall Rank: 8,294 | 44.24%
DOI: 10.14778/3402707.3402717

Incoming Non-self Citations Over Time

Authors

1. Tingjian Ge (University of Kentucky)
2. Zheng Li (University of Kentucky)

BibTeX Citation

@article{ge_vldb11,
        title = {{Approximate Substring Matching over Uncertain Strings}},
        author = {Ge, Tingjian and Li, Zheng},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {12},
        pages = {772--783},
        doi = {10.14778/3402707.3402717},
        url = {https://doi.org/10.14778/3402707.3402717},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,709	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	5.2905577e-05
12,396	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.9793485e-05
12,468	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.9793485e-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
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
4,849	Probabilistic String Similarity Joins	2010	SIGMOD	6.3809679e-05
6,848	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB	5.6658226e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
2	4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
3	10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD
4	4,439	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
5	3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
6	3,501	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD
7	6,952	Space-efficient Substring Occurrence Estimation	2011	PODS
8	8,709	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD
9	12,468	Similarity Joins for Uncertain Strings	2014	SIGMOD
10	7,842	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD