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: 4255
Venue: SIGMOD
Year: 2010
Pagerank: 5.8411648e-05
Overall Rank: 4,901 | 65.91%
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,740	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.1980628e-05
7,847	Set Similarity Join on Probabilistic Data	2010	VLDB	4.6365272e-05
8,143	Approximate Substring Matching over Uncertain Strings	2011	VLDB	4.5768015e-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 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.00044847972
155	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00040637896
299	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028525071
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
706	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017845469
721	Data Integration with Uncertainty	2007	VLDB	0.00017570539
1,202	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00013326298
1,234	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013122499
2,331	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.018559e-05
3,226	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.3433307e-05
4,942	Query language support for incomplete information in the MayBMS system	2007	VLDB	5.8176224e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,684	Approximate String Joins with Abbreviations	2018	VLDB	6.0006406e-05
4,026	Flexible String Matching Against Large Databases in Practice	2004	VLDB	6.5169976e-05
2,740	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.1980628e-05
1,234	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013122499
2,592	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4795761e-05
7,847	Set Similarity Join on Probabilistic Data	2010	VLDB	4.6365272e-05
4,216	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3521675e-05
9,563	Towards a Unified Framework for String Similarity Joins	2019	VLDB	4.3254416e-05
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
11,979	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.1945683e-05