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: 4317
Venue: SIGMOD
Year: 2010
Pagerank: 6.5268783e-05
Overall Rank: 4,743 | 67.46%
DOI: 10.1145/1807167.1807204

Incoming Non-self Citations Over Time

Authors

1. Jeffrey Jestes (Florida State University)
2. Feifei Li (Florida State University)
3. Zhepeng Yan (Hong Kong University of Science and Technology)
4. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{jestes_sigmod10,
        title = {{Probabilistic String Similarity Joins}},
        author = {Jestes, Jeffrey and Li, Feifei and Yan, Zhepeng and Yi, Ke},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807204},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807204},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB	9.0001436e-05
7,839	Set Similarity Join on Probabilistic Data	2010	VLDB	5.5340666e-05
8,114	Approximate Substring Matching over Uncertain Strings	2011	VLDB	5.484341e-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 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
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
158	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00028199923
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
331	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020936658
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
699	Data Integration with Uncertainty	2007	VLDB	0.0001487423
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
2,042	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.2691675e-05
2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.97814e-05
4,653	Query language support for incomplete information in the MayBMS system	2007	VLDB	6.5850987e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,396	Approximate String Joins with Abbreviations	2018	VLDB
2	4,009	Flexible String Matching Against Large Databases in Practice	2004	VLDB
3	2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB
4	911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB
5	1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB
6	7,839	Set Similarity Join on Probabilistic Data	2010	VLDB
7	3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
8	9,702	Towards a Unified Framework for String Similarity Joins	2019	VLDB
9	107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB
10	12,177	Similarity Joins for Uncertain Strings	2014	SIGMOD