DBScholar

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
4366
Venue
SIGMOD
Year
2010
Pagerank
9.2782094e-05
Overall Rank
2,036 | 86.04%
DOI
10.1145/1807167.1807266

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{zhang_sigmod10,
        title = {{Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance}},
        author = {Zhang, Zhenjie and Hadjieleftheriou, Marios and Ooi, Beng Chin and Srivastava, Divesh},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807266},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807266},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
975 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012870645
1,886 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 9.5358137e-05
2,186 String Similarity Joins: An Experimental Evaluation 2014 VLDB 9.0001436e-05
3,193 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.649474e-05
4,023 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.949387e-05
5,726 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1079184e-05
5,997 Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning 2020 VLDB 6.0146869e-05
6,002 Compression of Uncertain Trajectories in Road Networks 2020 VLDB 6.0133202e-05
6,484 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.8665833e-05
6,906 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 5.7418509e-05
7,692 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.5664611e-05
9,705 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 5.2351259e-05
9,979 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 5.1845938e-05
10,086 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.1559617e-05
11,504 TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching 2023 VLDB 5.093636e-05
11,643 Learning Algorithms for Automatic Data Structure Design 2021 SIGMOD 5.093636e-05
11,940 MSQL+: A Plugin Toolkit for Similarity Search under Metric Spaces in Distributed Relational Database Systems 2018 VLDB 5.093636e-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
107 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033511706
158 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00028199923
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.0002743469
200 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025597287
911 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013283031
1,701 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.9707165e-05
4,359 Incremental Maintenance of Length Normalized Indexes for Approximate String Matching 2009 SIGMOD 6.7451753e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,085 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD
2 6,496 Reference-Based Indexing of Sequence Databases 2006 VLDB
3 3,731 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB
4 8,078 Indexing Mixed Types for Approximate Retrieval 2005 VLDB
5 6,832 A Scalable Index for Top-k Subtree Similarity Queries 2019 SIGMOD
6 3,193 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD
7 7,692 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD
8 6,947 Indexing for Subtree Similarity-Search using Edit Distance 2013 SIGMOD
9 4,776 An Efficient Index Structure for String Databases 2001 VLDB
10 3,047 Similarity Evaluation on Tree-structured Data 2005 SIGMOD