論文

査読有り 筆頭著者 責任著者
2015年

SFB: a scalable method for handling range queries on Skip Graphs

IEICE Communications Express
  • Banno Ryohei
  • ,
  • Fujino Tomoyuki
  • ,
  • Takeuchi Susumu
  • ,
  • Takemoto Michiharu

4
1
開始ページ
14
終了ページ
19
記述言語
英語
掲載種別
DOI
10.1587/comex.4.14
出版者・発行元
一般社団法人 電子情報通信学会

Skip Graph is a promising candidate algorithm for large scale distributed systems. The principal feature is range query functionality, but Skip Graph does not have a definite method of multicasting inside ranges designated by query issuers. Even though several simple ways can be considered, they are inefficient regarding the latency or traffic volume. In this letter, we first introduce Multi-Range Forwarding (MRF) used in Multi-key Skip Graph. MRF can be used even in normal Skip Graph, and is efficient compared to the simple ways. Second, we propose a method named Split-Forward Broadcasting (SFB). We analytically evaluate SFB and explain that SFB can roughly halve the average number of hops of MRF.

リンク情報
DOI
https://doi.org/10.1587/comex.4.14
CiNii Articles
http://ci.nii.ac.jp/naid/130004972772
URL
http://orcid.org/0000-0001-7268-4657

エクスポート
BibTeX RIS