Database Paper Browser

Back to papers

Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme

Summary: Establishes tau+1 as the minimum signature size for exact edit-distance query processing and introduces asymmetric signature schemes that achieve this bound. Proposes fast query processing algorithms and DP-based pruning; empirically beats state-of-the-art across nine baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4453
Venue
SIGMOD
Year
2011
Pagerank
6.7709545e-05
Overall Rank
3,779 | 73.74%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
1,396 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012215253
2,729 String Similarity Joins: An Experimental Evaluation 2014 VLDB 8.2175463e-05
4,247 Local Similarity Search for Unstructured Text 2016 SIGMOD 6.3180334e-05
4,682 Approximate String Joins with Abbreviations 2018 VLDB 5.9949001e-05
5,152 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 5.6550754e-05
5,297 Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints 2020 VLDB 5.5772847e-05
6,080 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 5.219249e-05
6,730 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 4.9436522e-05
7,106 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 4.8250163e-05
7,142 Efficient Error-tolerant Query Autocompletion 2013 VLDB 4.8151659e-05
7,215 SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins 2023 VLDB 4.7939964e-05
9,566 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 4.3212967e-05
9,933 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 4.245954e-05
9,934 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.245954e-05
10,068 DiskJoin: Large-scale Vector Similarity Join with SSD 2026 SIGMOD 4.1905499e-05
10,714 Extensible and Robust Evaluation of Similarity Queries 2025 VLDB 4.1905499e-05
11,307 TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching 2023 VLDB 4.1905499e-05
11,730 ZigZag: Supporting Similarity Queries on Vector Space Models 2018 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032118946
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00051785122
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
248 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030888982
264 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029950264
1,203 VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams 2007 VLDB 0.00013317317
1,232 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013133604
2,077 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.6038296e-05
2,196 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.318552e-05
2,387 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 8.9075095e-05
3,583 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 6.944299e-05
4,215 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.3464157e-05
4,330 An Efficient Index Structure for String Databases 2001 VLDB 6.2745131e-05
4,370 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.2392118e-05
5,892 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2829767e-05
7,790 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 4.6458343e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,206 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3855924e-05
9,934 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.245954e-05
7,775 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.6494306e-05
5,624 A Scalable Index for Top-k Subtree Similarity Queries 2019 SIGMOD 5.4049016e-05
2,387 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 8.9075095e-05
1,232 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013133604
6,458 Reference-Based Indexing of Sequence Databases 2006 VLDB 5.0484248e-05
9,933 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 4.245954e-05
6,730 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 4.9436522e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05