文献

J-GLOBAL ID：201102264452698967   整理番号：11A1896104

Bloom Filterによる高速でコンパクトなインデックス構造-NAND Flash SSD上の高速データベースを対象とした-

Fast and compact index structure using Bloom Filter-For high speed database on NAND Flash SSD-

著者 (3件)： 山田淳二 (東大 大学院情報理工学系研究科) ,  浅野正一郎 (東大 大学院情報理工学系研究科) ,  浅野正一郎 (国立情報学研)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 111  号： 255(CPSY2011 25-41)  ページ： 31-36  発行年： 2011年10月14日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 高速で大容量のNAND Flash SSD(Solid State Disk)について,大量のデータアクセスを伴うデータベース分野での利用が研究されている。データの上書きに消去-モディファイ-再書込みが必要なNAND Flashの特性から,SSDへの書込みはシーケンシャルに行うことが望まれることから,SSD上にシーケンシャルにデータを書込み,Keyと書込み位置の対応を主記憶上のインデックスで保持する構造が,従来から提案されてきた。しかし,従来の構造では,主記憶上のインデックス構造の高速性とメモリ利用効率の両立が難しく,SSDの高速性能を十分に生かすことが出来なかった。本稿では,この点を解決する,Bloom Filterを利用した,メモリ利用効率が高く高速なインデックスのデータ構造を提案し,従来手法と比べて11.8倍の高速化を確認した。(著者抄録)

シソーラス用語： *フラッシュメモリ ,  駆動機構 ,  索引 ,  *データ構造 ,  ファイル編成 ,  インデクシング【計算機】 ,  記憶構造 ,  *データベース ,  高速化
準シソーラス用語： Bloomフィルタ ,  SSD

分類 (3件)： その他のディジタル計算機方式  (JC02050G) ,  記憶方式  (JC02040V) ,  データベースシステム  (JD03030U)

引用文献 (7件)：

• DEBNATH, Biplob. FlashStore : High Throughput Persistent Key-Value Store. Proc. VLDB, Sep. 2010. 2010, 3, 2, 1414-1425
• DEBNATH, Biplob. SkimpyStash : RAM Space Skimpy-Key-Value Store on Flashbased Storage. Proc. SIGMOD'11 Conference, Athens, Greece, Jun. 2011, 25-36
• CHANG, F. Bigtable : A Distributed Storage System for Structured Data. ACM Trans. Computer Systems. 2008, 26, issue2, 4
• BLOOM, B. H. Space/time trade-offs in hash coding with allowable errors. Commun. ACM. 1970, 13, issue7, 422-426
• BRODER, Andrie Z. Network Applications of Bloom Filters : A Survey. Internet Mathematics. 2005, 1, 4, 485-504

タイトルに関連する用語 (5件)： インデックス構造 ,  NAND ,  FLASH ,  SSD ,  データベース