Similarity Joins for Uncertain Strings

Summary: First similarity-join for uncertain strings under possible-world semantics using edit distance; finds pairs with Pr(ed(R,S) ≤ k) > τ. Employs pruning bounds, indexing, and a shared-verification trie to avoid enumerating all worlds and speed practical joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4973
Venue: SIGMOD
Year: 2014
Pagerank: 5.093636e-05
Overall Rank: 12,177 | 16.46%
DOI: 10.1145/2588555.2612178

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Manish Patil (Louisiana State University)
2. Rahul Shah (Louisiana State University)

BibTeX Citation

@inproceedings{patil_sigmod14,
        title = {{Similarity Joins for Uncertain Strings}},
        author = {Patil, Manish and Shah, Rahul},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2612178},
        url = {https://dl.acm.org/doi/10.1145/2588555.2612178},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
125	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030932014
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
254	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00023199211
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
2,042	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.2691675e-05
4,743	Probabilistic String Similarity Joins	2010	SIGMOD	6.5268783e-05
4,776	An Efficient Index Structure for String Databases	2001	VLDB	6.513844e-05
8,114	Approximate Substring Matching over Uncertain Strings	2011	VLDB	5.484341e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD
2	10,085	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD
3	1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB
4	2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB
5	107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB
6	7,839	Set Similarity Join on Probabilistic Data	2010	VLDB
7	8,114	Approximate Substring Matching over Uncertain Strings	2011	VLDB
8	3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
9	9,702	Towards a Unified Framework for String Similarity Joins	2019	VLDB
10	4,743	Probabilistic String Similarity Joins	2010	SIGMOD