集約Skip Graph: 効率的な集約クエリを実現するSkip Graph拡張の提案

書誌情報

阿部敏之，上田達也，安倍広多，石橋勇人，松浦敏雄，集約Skip Graph: 効率的な集約クエリを実現するSkip Graph拡張の提案，情報処理学会第2回インターネットと運用技術シンポジウム予稿集, pp.75–82, (2009-12).

Abstract

Skip graphは範囲検索が可能な構造化オーバレイネットワークであり，キーをインデックスとして値を保持する分散データベースを構成可能である．ある範囲内のすべてのキーに対応する値に関して最大値や最小値，平均値などを求めるクエリ(集約クエリ)をSkip graphを用いて実現する場合，範囲内のすべてのノードと通信する必要があるため，範囲の大きさに比例してメッセージ数が増加する問題がある．そこで，あらかじめ部分範囲の集約値を保持することで，任意の範囲の集約クエリを効率的に実行できるSkip graphの拡張(集約Skip graph)を提案する．集約Skip graphの効果はシミュレーションにより確認した．

Skip graph is a structured overlay network that allows range query. Skip graph is useful for a distributed database which stores values corresponding to keys. Considering to find some aggregated value like a maximum, a minimum, or an average of stored values within a range of keys, Skip graph requires more messages as the query covers wider range since all nodes within the range have to be accessed. This paper proposes Aggregation skip graph, that is an extension of Skip graph, in order to perform aggregation queries effectively. This is achieved by holding values partially aggregated for local ranges. The simulation results are also shown in the paper.

論文

ここに掲載した著作物の利用に関する注意 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。

Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof.

プレゼンテーション

注

集約Skip Graphに関しては，Aggregation Skip Graph: A Skip Graph Extension for Efficient Aggregation Query（ジャーナル）も御参照下さい．