Database Paper Browser

Back to papers

Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance

Summary: Bed-tree is a B+-tree index for evaluating all edit-distance and normalized edit-distance similarity queries. It introduces three string-to-integer mappings enabling pruning, delivering an all-purpose solution that surpasses n-gram methods under tight memory and frequent updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4305
Venue
SIGMOD
Year
2010
Pagerank
8.9075095e-05
Overall Rank
2,387 | 83.42%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 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,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
3,779 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7709545e-05
4,397 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.2142485e-05
5,939 Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning 2020 VLDB 5.2603518e-05
6,008 Compression of Uncertain Trajectories in Road Networks 2020 VLDB 5.2365238e-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,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05
9,566 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 4.3212967e-05
9,831 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 4.2710095e-05
9,934 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.245954e-05
11,307 TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching 2023 VLDB 4.1905499e-05
11,448 Learning Algorithms for Automatic Data Structure Design 2021 SIGMOD 4.1905499e-05
11,742 MSQL+: A Plugin Toolkit for Similarity Search under Metric Spaces in Distributed Relational Database Systems 2018 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
155 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00040666376
248 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030888982
264 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029950264
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
4,878 Incremental Maintenance of Length Normalized Indexes for Approximate String Matching 2009 SIGMOD 5.8537044e-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
6,458 Reference-Based Indexing of Sequence Databases 2006 VLDB 5.0484248e-05
4,215 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.3464157e-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
3,779 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7709545e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05
6,805 Indexing for Subtree Similarity-Search using Edit Distance 2013 SIGMOD 4.9170518e-05
4,330 An Efficient Index Structure for String Databases 2001 VLDB 6.2745131e-05
3,206 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3855924e-05