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
h4dc462a903542db1
Venue
SIGMOD
Year
2010
Pagerank
9.0864612e-05
Overall Rank
2,072 | 86.08%
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
963 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012816649
1,933 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 9.3459285e-05
2,220 String Similarity Joins: An Experimental Evaluation 2014 VLDB 8.8146984e-05
3,255 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4890984e-05
4,107 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.8026037e-05
5,444 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1268526e-05
6,031 Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning 2020 VLDB 5.9104518e-05
6,130 Compression of Uncertain Trajectories in Road Networks 2020 VLDB 5.8783975e-05
6,605 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.7367357e-05
7,030 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 5.6173605e-05
7,842 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.4425932e-05
9,126 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 5.22387e-05
9,879 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 5.1176637e-05
10,299 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.0418674e-05
11,813 TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching 2023 VLDB 4.9793485e-05
11,950 Learning Algorithms for Automatic Data Structure Design 2021 SIGMOD 4.9793485e-05
12,239 MSQL+: A Plugin Toolkit for Similarity Search under Metric Spaces in Distributed Relational Database Systems 2018 VLDB 4.9793485e-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
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.0003305531
161 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00027718195
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027163517
201 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025331535
929 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013020115
1,737 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.7494976e-05
4,439 Incremental Maintenance of Length Normalized Indexes for Approximate String Matching 2009 SIGMOD 6.5998035e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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