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: h4e8818cd58cfa94d
Venue: SIGMOD
Year: 2010
Pagerank: 6.3809679e-05
Overall Rank: 4,849 | 67.40%
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,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
7,998	Set Similarity Join on Probabilistic Data	2010	VLDB	5.4104124e-05
8,294	Approximate Substring Matching over Uncertain Strings	2011	VLDB	5.3612871e-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 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
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
161	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00027718195
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023258672
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020621631
696	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00014697176
715	Data Integration with Uncertainty	2007	VLDB	0.00014559092
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
1,061	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012213729
2,082	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.0732581e-05
2,967	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.8029216e-05
4,742	Query language support for incomplete information in the MayBMS system	2007	VLDB	6.4401895e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,493	Approximate String Joins with Abbreviations	2018	VLDB
2	4,087	Flexible String Matching Against Large Databases in Practice	2004	VLDB
3	2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB
4	929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB
5	1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB
6	7,998	Set Similarity Join on Probabilistic Data	2010	VLDB
7	3,816	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
8	9,878	Towards a Unified Framework for String Similarity Joins	2019	VLDB
9	108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB
10	12,468	Similarity Joins for Uncertain Strings	2014	SIGMOD