テキスト索引パトリシア木を作り終えて,今度はString B-Treeの実装していたんだけど,階層化パトリシア木でも良いのかなっとかsuffix木の階層化の話で良いのが提案されてるかも...と気になって,CPS-tree: A Compact Partitioned Suffix Tree for Disk-based Indexing on Large Genome Sequencesという論文を読んでた。結論としてはString B-Treeで良いや,なんだけど。 Suffix Treeを素直にページサイズごとに切って,少し工夫しましたというようなお話。ICDE2007なんだけど,2007年までsuffix treeの二次記憶への格納の話があんまりされていないことに驚き。索引構築と主記憶に収まるように極小表現を考えたり,主記憶上の話が主に研究課題であったようだ。 悪くない論文なんだけど