Probabilistic String Similarity Joins

Summary: Probabilistic string joins via expected edit distance (EED) for uncertain strings; two models: full string-level and compact character-level. Pruning enables efficient EED computation inside standard RDBMSs, with experiments showing order-of-magnitude gains over baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4256
Venue: SIGMOD
Year: 2010
Pagerank: 5.8365853e-05
Overall Rank: 4,907 | 65.90%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,729	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.2175463e-05
7,844	Set Similarity Join on Probabilistic Data	2010	VLDB	4.6330652e-05
8,146	Approximate Substring Matching over Uncertain Strings	2011	VLDB	4.5724134e-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 11 of 11 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
155	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00040666376
300	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028503742
322	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027523667
702	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017848789
718	Data Integration with Uncertainty	2007	VLDB	0.00017558942
1,203	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00013317317
1,232	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013133604
2,334	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.01132e-05
3,229	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.3390133e-05
4,941	Query language support for incomplete information in the MayBMS system	2007	VLDB	5.8129205e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,682	Approximate String Joins with Abbreviations	2018	VLDB	5.9949001e-05
4,033	Flexible String Matching Against Large Databases in Practice	2004	VLDB	6.5125692e-05
2,729	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.2175463e-05
1,232	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013133604
2,588	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4872437e-05
7,844	Set Similarity Join on Probabilistic Data	2010	VLDB	4.6330652e-05
4,215	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3464157e-05
9,563	Towards a Unified Framework for String Similarity Joins	2019	VLDB	4.3212967e-05
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044946098
11,987	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.1905499e-05