文献

J-GLOBAL ID：201202235890873248   整理番号：12A1081266

Range-key Skip Graphによる範囲検索可能な大規模分散キーバリューストアの実現

An Implementation of Large Scale Distributed Key-value Store with Range Search Feature Based on Range-key Skip Graph

著者 (7件)： 石芳正 (大阪大 サイバーメディアセ) ,  寺西裕一 (大阪大 サイバーメディアセ) ,  寺西裕一 (情報通信研究機構) ,  吉田幹 (ビービーアール) ,  竹内亨 (NTT 未来ねっと研) ,  下條真司 (大阪大 サイバーメディアセ) ,  下條真司 (情報通信研究機構)
資料名： 情報処理学会論文誌ジャーナル(CD-ROM)  (情報処理学会論文誌 論文誌ジャーナル(CD-ROM))
巻： 53  号： 7  ページ： 1850-1862  発行年： 2012年07月15日 
JST資料番号： Z0778B  ISSN： 1882-7837  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： オーバレイネットワークRange-key Skip Graphを用いることにより大規模環境においてもスケーラブルな範囲検索を実現可能とする分散キーバリューストアの構成法を提案する。Skip Graph拡張の1つであるMulti-key Skip Graphを用いれば範囲検索可能な分散キーバリューストアを構成できるが,この方法では1つのキーごとに個別の経路表を持つため,キー数に比例して経路表のサイズが増加し,ノードの参加離脱時にオーバヘッドが大きくなるという問題がある。そこで本研究では,ノードが担当するキーの集合を範囲キーとして扱い,Range-key Skip Graphによりルーティングを行うことで経路表を簡素化する方法を提案する。シミュレーションと実機による評価を行い,本提案により検索コストをMulti-key Skip Graphと同等に保ちつつ,経路表を大幅に簡素化可能であること,ならびにその性能がスケールすることを示した。(著者抄録)

シソーラス用語： *情報システム ,  分散処理 ,  グラフ ,  *通信網 ,  スケーラビリティ【計算機】 ,  大規模系 ,  *情報検索 ,  経路選定 ,  記憶装置 ,  経路 ,  通信操作
準シソーラス用語： Range-key Skip Graph ,  *オーバレイネットワーク ,  オーバヘッド ,  *分散キーバリューストア

分類 (3件)： その他の情報処理  (JE15050M) ,  電話・データ通信・交換一般  (ND11010T) ,  検索技術  (AC06020S)

引用文献 (21件)：

• [1] DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P. and Vogels, W.: Dynamo: Amazon's highly available key-value store, SIGOPS Operating Systems Review, Vol.41, No.6, pp.205-220 (2007).
• [2] The Apache Cassandra Project, available from <http://cassandra.apache.org/> (accessed 2012-04-04).
• [3] Rakuten ROMA, available from <http://code.google.com/p/roma-prj/> (accessed 2012-04-04).
• [4] Flare - GREE Labs, available from <http://labs.gree.jp/Top/OpenSource/Flare.html>, (accessed 2012-04-04).
• [5] The Kumofs Project, available from <http://kumofs.sourceforge.net/> (accessed 2012-04-04).

タイトルに関連する用語 (2件)： 範囲検索 ,  大規模