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: 10497
Venue: VLDB
Year: 2011
Pagerank: 5.484341e-05
Overall Rank: 8,114 | 44.34%
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,542	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	5.4119882e-05
12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	5.093636e-05
12,177	Similarity Joins for Uncertain Strings	2014	SIGMOD	5.093636e-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
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
4,743	Probabilistic String Similarity Joins	2010	SIGMOD	6.5268783e-05
6,716	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB	5.7958663e-05

Semantically Similar Papers

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