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)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Manish Patil
- 2. Rahul Shah
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 |
|---|---|---|---|---|
| 125 | Approximate String Joins in a Database (Almost) for Free | 2001 | VLDB | 0.00044946098 |
| 149 | Trio: A System for Integrated Management of Data, Accuracy, and Lineage | 2005 | CIDR | 0.00041085859 |
| 264 | Efficient Exact Set-Similarity Joins | 2006 | VLDB | 0.00029950264 |
| 321 | Record Linkage: Similarity Measures and Algorithms | 2006 | SIGMOD | 0.00027524716 |
| 1,232 | Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints | 2008 | VLDB | 0.00013133604 |
| 2,334 | Orion 2.0: Native Support for Uncertain Data | 2008 | SIGMOD | 9.01132e-05 |
| 2,588 | Pass-Join: A Partition-based Method for Similarity Joins | 2012 | VLDB | 8.4872437e-05 |
| 4,330 | An Efficient Index Structure for String Databases | 2001 | VLDB | 6.2745131e-05 |
| 4,907 | Probabilistic String Similarity Joins | 2010 | SIGMOD | 5.8365853e-05 |
| 8,146 | Approximate Substring Matching over Uncertain Strings | 2011 | VLDB | 4.5724134e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,933 | Local Filtering: Improving the Performance of Approximate Queries on String Collections | 2015 | SIGMOD | 4.245954e-05 |
| 5,152 | String Similarity Measures and Joins with Synonyms | 2013 | SIGMOD | 5.6550754e-05 |
| 2,588 | Pass-Join: A Partition-based Method for Similarity Joins | 2012 | VLDB | 8.4872437e-05 |
| 2,729 | String Similarity Joins: An Experimental Evaluation | 2014 | VLDB | 8.2175463e-05 |
| 125 | Approximate String Joins in a Database (Almost) for Free | 2001 | VLDB | 0.00044946098 |
| 7,844 | Set Similarity Join on Probabilistic Data | 2010 | VLDB | 4.6330652e-05 |
| 8,146 | Approximate Substring Matching over Uncertain Strings | 2011 | VLDB | 4.5724134e-05 |
| 4,215 | Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints | 2010 | VLDB | 6.3464157e-05 |
| 9,563 | Towards a Unified Framework for String Similarity Joins | 2019 | VLDB | 4.3212967e-05 |
| 4,907 | Probabilistic String Similarity Joins | 2010 | SIGMOD | 5.8365853e-05 |