The string B-tree

DOI Web Site 被引用文献6件

書誌事項

タイトル別名
  • a new data structure for string search in external memory and its applications

この論文をさがす

説明

<jats:p> We introduce a new text-indexing data structure, the <jats:italic>String B-Tree</jats:italic> , 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. </jats:p>

収録刊行物

  • Journal of the ACM

    Journal of the ACM 46 (2), 236-280, 1999-03

    Association for Computing Machinery (ACM)

被引用文献 (6)*注記

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ