Range-Key Extension of the Skip Graph
Yoshimasa Ishi, Yuuichi Teranishi, Mikio Yoshida, Susumu Takeuchi, Shinji Shimojo, Shojiro Nishio · 2010
In the Skip Graph, which is a structured overlay network that supports range retrievals, a key is supposed to consist of a single value. Therefore, the Skip Graph cannot perform range-to-range retrievals. In the present research, we extend the Skip Graph, enabling it to retain a range as a key, and propose the Range-Key Skip Graph, which can perform range-to-range retrievals. We also implement the proposed scheme and evaluate it on the PlanetLab.