The string B-tree: a new data structure for string search in external memory and its applications

✍ Scribed by Ferragina, Paolo; Grossi, Roberto

• Book ID: 118162612
• Publisher: Association for Computing Machinery
• Year: 1999
• Tongue: English
• Weight: 355 KB
• Volume: 46
• Category: Article
• ISSN: 0004-5411
• DOI: 10.1145/301970.301973

✦ Synopsis

We introduce a new text-indexing data structure, the
String B-Tree
, that can be seen as a link between some traditional external-memory and string-matching data structures. In a short phrase, it is a combination of B-trees and Patricia tries for internal-node indices that is made more effective by adding extra pointers to speed up search and update operations. Consequently, the String B-Tree overcomes the theoretical limitations of inverted files, B-trees, prefix B-trees, suffix arrays, compacted tries and suffix trees. String B-trees have the same worst-case performance as B-trees but they manage unbounded-length strings and perform much more powerful search operations such as the ones supported by suffix trees. String B-trees are also effective in main memory (RAM model) because they improve the online suffix tree search on a dynamic set of strings. They also can be successfully applied to database indexing and software duplication.