DBScholar

Back to papers

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
ha78273942f0f4b76
Venue
SIGMOD
Year
2014
Pagerank
4.9605343e-05
Overall Rank
12,517 | 16.10%
DOI
10.1145/2588555.2612178

Incoming Non-self Citations Over Time

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

Authors

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
Previous Page 1 / 1 Next

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
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00032945275
127 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR 0.00030337791
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027077763
264 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.0002276412
934 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00012973416
1,941 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 9.3141839e-05
2,096 Orion 2.0: Native Support for Uncertain Data 2008 SIGMOD 9.0406786e-05
4,878 Probabilistic String Similarity Joins 2010 SIGMOD 6.3569172e-05
4,921 An Efficient Index Structure for String Databases 2001 VLDB 6.3441964e-05
8,314 Approximate Substring Matching over Uncertain Strings 2011 VLDB 5.3410298e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,331 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD
2 5,233 String Similarity Measures and Joins with Synonyms 2013 SIGMOD
3 1,941 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB
4 2,235 String Similarity Joins: An Experimental Evaluation 2014 VLDB
5 108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB
6 8,019 Set Similarity Join on Probabilistic Data 2010 VLDB
7 8,314 Approximate Substring Matching over Uncertain Strings 2011 VLDB
8 3,822 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB
9 9,918 Towards a Unified Framework for String Similarity Joins 2019 VLDB
10 4,878 Probabilistic String Similarity Joins 2010 SIGMOD