配列を用いたキャッシュコンシャスな索引木の提案

• Item type: SIG Technical Reports(1)
• 公開日: 2002-07-18
• タイトル: 配列を用いたキャッシュコンシャスな索引木の提案
• タイトル / 言語: en
• タイトル: Cache Conscious Trees using Arrays : A proposal
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Gunma University
• 著者名: 高見澤, 秀久; 有次, 正義
• 著者名(英): Hidehisa, Takamizawa; Masayoshi, Aritsugi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年の研究において，キャッシュコンシャスな索引構造は優れた性能を示している．キャッシュコンシャスな索引木における重要な考えは，ノードからのポインタの削除にある．ポインタを削除することにより，ノードが持つ子ノードの数は増加し木の高さは低くなる．その結果として効果的なキャッシュの利用が可能となる．本稿では，キャッシュコンシャスな索引木「Array-Based Cache conscious trees」（ABC木）を提案する．ABC木では，木構造を完全木として配列により表現する．この索引木の構造や操作方法はB+木に類似しているが，B+木のように子ノードへのポインタを格納しない．ノード間の相対的な位置関係を計算することで目的のノードを得る．また，その高さの完全木を構築するのに必要となる領域をあらかじめ確保しノード間の位置関係を保つことで更新処理にも柔軟に対応する．そのため，ノードのオーバーフローやアンダーフローが発生した場合のコストも比較的低くなる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Cache conscious indexing structures attracts many researchers because of their efficiency. The key idea to implement the trees is to remove pointers from nodes of trees. This allows a node to increase the number of child nodes, thereby making the height of a tree low. As a result, cache is used effectively. In this paper, Array-Based Cache conscious trees (ABC trees in short) are proposed. ABC trees are constructed as complete trees using arrays. While the tree is treated like a B+tree, it does not hold pointers to child nodes. A node of the ABC tree can be extracted by calculating spatial relations among nodes in the tree. Updates can be processed efficiently because the necessary space for nodes of the complete tree are allocated and the whole spatial relations among nodes in the space can be calculated in advance to the processing. Therefore, it is expected that the costs of node split and merge are relatively low.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2002, 号 67(2002-DBS-128), p. 53-58, 発行日 2002-07-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会