CSS - treeの挿入処理の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2002-07-18
• タイトル: CSS - treeの挿入処理の高速化
• タイトル / 言語: en
• タイトル: Accelerating insertion processing to the CSS - tree
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 慶應義塾大学大学院理工学研究科
• 著者所属: 慶應義塾大学大学院理工学研究科
• 著者所属: 慶應義塾大学理工学部
• 著者所属: 慶應義塾大学理工学部
• 著者所属(英): en
• 著者所属(英): Gradudate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Gradudate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Keio University
• 著者名: 本田, 喜久; 川島, 英之; 今井, 倫太; 安西, 祐一郎
• 著者名(英): Yoshihisa, Honda; Hideyuki, Kawashima; Michita, Imai; Yuichiro, Anzai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年 キャッシュを意識して探索を高速化するメモリ索引構造が提案されている. 中でも 1999年に提案されたFull Cache Sensitive SearchTree(CSS-tree)は 探索時間がデータサイズによってはハッシュよりも短く また索引構造のために必要なメモリ空間使用量がB-treeよりも少ない点で優れている. 他方 更新処理が遅いため CSS-tree が有用であるのはオンライン解析処理のように更新処理が極めて少ない状況に限られると言われている. しかし 更新処理を追加処理のみに限定すれば 索引構造の再構築時間を減らすことができる. そこで本研究では 追加処理のみが発生する状況において CSS-treeへの挿入処理を高速化する手法を提案する. 提案手法は (1)配列とCSS-treeのノードの拡張に要するコストを減らすために あらかじめ余分な索引構造領域を獲得しておき (2)配列とCSS-treeの葉ノードの再マップに要するコストを減らすために CSS-tree の葉ノードの領域をなくし CSS-treeの内部ノードのスロットに 配列のキー値を格納する. 提案手法の有効性を評価するために C言語とアセンブラを用いて SunOS 5.6上に実験用データベースシステムを実装し 挿入処理時間を測定した. 実験の結果 提案手法は 更新処理を追加処理に限定しない再構築手法と比べて 最大で7.18倍速くなることがわかった.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In recent years, memory index structures that accelerate search speed utilizing the structure of CPU cache have proposed. Especially, the Full Cache Sensitive Search Tree(CSS-tree) proposed in 1999 is faster than hash depending on data size and require smaller amount of space than B-tree. On the other hand, reconstructing the CSS-tree is so slow that it has been considered that the CSS-tree is only useful under static environments such as OLAP. However, if updating is limited only to additional insertions, the reconstruction cost can be dramatically decreased. Then, in this research, we propose the new techniques that accelerate insertion processing to the CSS-tree. The technique consists of (1) preliminary acquiring excess index structure space to reduce cost for node expanding and (2)omitting leaf nodes to reduce cost for remapping the leaf nodes and instead, storing key value into internal nodes. To evaluate the proposed technique, we implemented an experimental system with C language and assemblers on SunOS 5.6 and measured the insertion time and the size of memory space for the structure. The result showed that the proposed technique accelerates 7.18 times faster than original technique.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2002, 号 67(2002-DBS-128), p. 59-66, 発行日 2002-07-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会