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
4304
Venue
SIGMOD
Year
2010
Pagerank
8.9424361e-05
Overall Rank
2,376 | 83.48%
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.00012204748
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
3,774 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7757301e-05
4,402 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.2195162e-05
5,936 Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning 2020 VLDB 5.2654071e-05
6,004 Compression of Uncertain Trajectories in Road Networks 2020 VLDB 5.2415551e-05
6,074 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 5.2242306e-05
6,726 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 4.9484027e-05
7,109 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 4.8292998e-05
7,708 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6721808e-05
9,567 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 4.3254416e-05
9,661 MSQL+: A Plugin Toolkit for Similarity Search under Metric Spaces in Distributed Relational Database Systems 2018 VLDB 4.3100374e-05
9,832 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 4.2751057e-05
9,933 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.2500258e-05
11,305 TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching 2023 VLDB 4.1945683e-05
11,445 Learning Algorithms for Automatic Data Structure Design 2021 SIGMOD 4.1945683e-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.00044847972
155 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00040637896
250 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030661988
266 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029718727
1,234 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013122499
2,073 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.6142791e-05
4,988 Incremental Maintenance of Length Normalized Indexes for Approximate String Matching 2009 SIGMOD 5.783959e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,932 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 4.2500258e-05
6,464 Reference-Based Indexing of Sequence Databases 2006 VLDB 5.0532607e-05
4,216 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.3521675e-05
7,777 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.653704e-05
5,615 A Scalable Index for Top-k Subtree Similarity Queries 2019 SIGMOD 5.4101086e-05
3,774 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7757301e-05
7,708 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6721808e-05
6,807 Indexing for Subtree Similarity-Search using Edit Distance 2013 SIGMOD 4.9217776e-05
4,333 An Efficient Index Structure for String Databases 2001 VLDB 6.2805237e-05
3,199 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3927291e-05