IEICE TRANSACTIONS on Information
An Efficient Routing Method for Range Queries in Skip Graph
Summary :
Skip Graph is a promising distributed data structure for large scale systems and known for its capability of range queries. Although several methods of routing range queries in Skip Graph have been proposed, they have inefficiencies such as a long path length or a large number of messages. In this paper, we propose a novel routing method for range queries named Split-Forward Broadcasting (SFB). SFB introduces a divide-and-conquer approach, enabling nodes to make full use of their routing tables to forward a range query. It brings about a shorter average path length than existing methods, as well as a smaller number of messages by avoiding duplicate transmission. We clarify the characteristics and effectiveness of SFB through both analytical and experimental comparisons. The results show that SFB can reduce the average path length roughly 30% or more compared with a state-of-the-art method.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.516-525
- Publication Date
- 2020/03/01
- Publicized
- 2019/12/09
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2019FCP0008
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
- Category
Authors
Ryohei BANNO
Tokyo Institute of Technology
Kazuyuki SHUDO
Tokyo Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ryohei BANNO, Kazuyuki SHUDO, "An Efficient Routing Method for Range Queries in Skip Graph" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 3, pp. 516-525, March 2020, doi: 10.1587/transinf.2019FCP0008.
Abstract: Skip Graph is a promising distributed data structure for large scale systems and known for its capability of range queries. Although several methods of routing range queries in Skip Graph have been proposed, they have inefficiencies such as a long path length or a large number of messages. In this paper, we propose a novel routing method for range queries named Split-Forward Broadcasting (SFB). SFB introduces a divide-and-conquer approach, enabling nodes to make full use of their routing tables to forward a range query. It brings about a shorter average path length than existing methods, as well as a smaller number of messages by avoiding duplicate transmission. We clarify the characteristics and effectiveness of SFB through both analytical and experimental comparisons. The results show that SFB can reduce the average path length roughly 30% or more compared with a state-of-the-art method.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019FCP0008/_p
Copy
@ARTICLE{e103-d_3_516,
author={Ryohei BANNO, Kazuyuki SHUDO, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Routing Method for Range Queries in Skip Graph},
year={2020},
volume={E103-D},
number={3},
pages={516-525},
abstract={Skip Graph is a promising distributed data structure for large scale systems and known for its capability of range queries. Although several methods of routing range queries in Skip Graph have been proposed, they have inefficiencies such as a long path length or a large number of messages. In this paper, we propose a novel routing method for range queries named Split-Forward Broadcasting (SFB). SFB introduces a divide-and-conquer approach, enabling nodes to make full use of their routing tables to forward a range query. It brings about a shorter average path length than existing methods, as well as a smaller number of messages by avoiding duplicate transmission. We clarify the characteristics and effectiveness of SFB through both analytical and experimental comparisons. The results show that SFB can reduce the average path length roughly 30% or more compared with a state-of-the-art method.},
keywords={},
doi={10.1587/transinf.2019FCP0008},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - An Efficient Routing Method for Range Queries in Skip Graph
T2 - IEICE TRANSACTIONS on Information
SP - 516
EP - 525
AU - Ryohei BANNO
AU - Kazuyuki SHUDO
PY - 2020
DO - 10.1587/transinf.2019FCP0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2020
AB - Skip Graph is a promising distributed data structure for large scale systems and known for its capability of range queries. Although several methods of routing range queries in Skip Graph have been proposed, they have inefficiencies such as a long path length or a large number of messages. In this paper, we propose a novel routing method for range queries named Split-Forward Broadcasting (SFB). SFB introduces a divide-and-conquer approach, enabling nodes to make full use of their routing tables to forward a range query. It brings about a shorter average path length than existing methods, as well as a smaller number of messages by avoiding duplicate transmission. We clarify the characteristics and effectiveness of SFB through both analytical and experimental comparisons. The results show that SFB can reduce the average path length roughly 30% or more compared with a state-of-the-art method.
ER -
English
