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.00044847972 |
| 149 | Trio: A System for Integrated Management of Data, Accuracy, and Lineage | 2005 | CIDR | 0.00041101118 |
| 266 | Efficient Exact Set-Similarity Joins | 2006 | VLDB | 0.00029718727 |
| 322 | Record Linkage: Similarity Measures and Algorithms | 2006 | SIGMOD | 0.00027518768 |
| 1,234 | Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints | 2008 | VLDB | 0.00013122499 |
| 2,331 | Orion 2.0: Native Support for Uncertain Data | 2008 | SIGMOD | 9.018559e-05 |
| 2,592 | Pass-Join: A Partition-based Method for Similarity Joins | 2012 | VLDB | 8.4795761e-05 |
| 4,333 | An Efficient Index Structure for String Databases | 2001 | VLDB | 6.2805237e-05 |
| 4,901 | Probabilistic String Similarity Joins | 2010 | SIGMOD | 5.8411648e-05 |
| 8,143 | Approximate Substring Matching over Uncertain Strings | 2011 | VLDB | 4.5768015e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,151 | String Similarity Measures and Joins with Synonyms | 2013 | SIGMOD | 5.6609851e-05 |
| 9,932 | Local Filtering: Improving the Performance of Approximate Queries on String Collections | 2015 | SIGMOD | 4.2500258e-05 |
| 2,592 | Pass-Join: A Partition-based Method for Similarity Joins | 2012 | VLDB | 8.4795761e-05 |
| 2,740 | String Similarity Joins: An Experimental Evaluation | 2014 | VLDB | 8.1980628e-05 |
| 125 | Approximate String Joins in a Database (Almost) for Free | 2001 | VLDB | 0.00044847972 |
| 7,847 | Set Similarity Join on Probabilistic Data | 2010 | VLDB | 4.6365272e-05 |
| 8,143 | Approximate Substring Matching over Uncertain Strings | 2011 | VLDB | 4.5768015e-05 |
| 4,216 | Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints | 2010 | VLDB | 6.3521675e-05 |
| 9,563 | Towards a Unified Framework for String Similarity Joins | 2019 | VLDB | 4.3254416e-05 |
| 4,901 | Probabilistic String Similarity Joins | 2010 | SIGMOD | 5.8411648e-05 |