An Efficient Range Search Method
Utilizing Detour Routes in Skip Graph
Yuya Miki, Takeshi Kaneko, Ryohei Banno† , and Kazuyuki Shudo
Tokyo Institute of Technology
Tokyo, Japanmiki.y.ad@m.titech.ac.jp

Abstract—Skip Graph is a structured overlay that preserves
the order of keys and provides efficient routing, especially forcomplex queries such as range queries. However, existing routing
methods for range queries in Skip Graph have problems suchas long path lengths and a large number of messages because of
inefficiencies. In this paper, we propose a new routing method
for range queries named Detouring Range Search (DRS), thatprovides more efficient routing by utilizing detour routes. In
the proposed method, each node that receives a query divides
the target range into subranges based on the center of thesubordinate node sequence and delegates them to its neighbornodes. Our evaluation experiments show that the proposed
method can reduce the average path length by approximately
20% compared with that of an existing method when the numberof nodes is sufficiently large.
Index Terms—Skip Graph, Structured overlay, Peer-to-peer
network, Routing algorithm, Range query

I. I NTRODUCTION
An overlay network is a logical network built upon an
existing network that provides message distribution and asearch function for nodes and data. Additional useful functions
are provided by constructing a topology independent of theunderlying network. In particular, a structured overlay provides high scalability and efficient routing by constructing anautonomous distributed network of nodes following a specificdata structure and a protocol. Because of their performance,
structured overlays have been applied to a variety of systems,
such as distributed file systems and video streaming. They arealso being considered for applications in blockchain, which
has attracted attention in recent years [1], [2].
In structured overlays, Skip Graph [3] is known for its
range query capability. Unlike other structured overlays [4],[5], Skip Graph manages data without hashing keys and canthus construct a topology that preserves the order of the keys.
Several routing methods [6]–[8] have been proposed for range
queries in Skip Graph, but these methods have problems suchas long path lengths and a large number of messages which
can lead to high latency and low fault tolerance.
In this paper, we propose a new routing method for range
queries in Skip Graph, named Detouring Range Search (DRS).
In the proposed method, each node that receives a query
divides the target range into subranges based on the centerof the subordinate node sequence and delegates them to its
This work was supported by JSPS KAKENHI Grant Number JP21H04872.
† Current affiliation as of December 2021: Kogakuin University

neighbor nodes. In this way, the query can be delivered to allnodes in the range with a minimum number of messages andwith a short average path length.
This paper is organized as follows. In Section II, we provide
an overview of existing routing methods in Skip Graph. Next,
we describe the details of the proposed method in Section III,and the evaluation experiments of the proposed method andtheir results are discussed in Section IV. Finally, in Section
V, we present conclusions and future work.
II. R ELATED W ORK
Skip Graph [3] is a data structure designed based on Skip
List [9], where each node belongs to multiple sorted doubly
linked lists. Each node has a key and a random string called amembership vector, and the topology is constructed based onthese values. A linked list at level i is formed by nodes whose
membership vector prefix i digits match.
In this paper, we denote the set of characters that constitutea membership vector as a finite alphabet Σ.
A. Routing method for exact-match queries
For an exact-match query, the search starts at the highest
level of the node that issues the query. The query is forwarded
by repeatedly hopping within a range that does not exceed thetarget key and descending one level down. In this way, thehigher level acts as a link to shortcut long distances, whichenables us to reach the node with a target key with a shortpath length.
Detouring Skip Graph (DSG) [10] is a method to reduce
the path length of routing for exact-match queries by utilizing
detour routes. DSG estimates the center of the subordinate
node sequence and decides whether to detour based on thevalue. When estimating the center, it is difficult to obtain the
distribution of keys in advance, but evaluation experiments in
DSG have shown that in many cases, using the average of two
keys is sufficient to reduce the path length. In this way, thepath length can be reduced by utilizing detour routes.
DSG is not a routing method for range queries, which isthe subject of this paper, but the approach of utilizing detour
routes by estimating the center of neighbor nodes in DSG canbe applied to range queries.

Proc. 19th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2022), pp.895-898, January 2021

Search Query

Target Range: [5, 305]
Level 3

10

35

70

135

142

168

215

135
215

35

10
Level 0
Key

135
70

168
142

k2
Fig. 2: Dividing position using the proposed method.

142
35

k1

lowerNode168

10delegationNode

300
300

70

Level 2

Level 1mid(k1, k2)

localNode

300
215

10

35

70

135

142

168

215

Node A

B

C

D

E

F

G

300
H

000...

101...

011...

110...

001...

100...

010...

111...

Membership vector

Fig. 1: Example of routing with SFB.

B. Routing method for range queries
For a range query, routing is performed in the same way
as exact-match queries until an arbitrary node in the target
range receives the query and then starts multicasting within
the target range.
Multi-Range Forwarding (MRF) is a routing method forrange queries that reduces path length and number of messagesby dividing the target range and delegating the subranges [6].
Let us denote the target range of a range query as R. In MRF,
each node that receives a query within R divides R into two
subranges based on its key. Then, it delegates the subrange toeach of the nodes that is a neighbor node at the highest levelin the subrange. By repeating this operation for each node thatreceives a query, all nodes within the target range eventually
receive the query.
Since MRF can avoid duplicate transfers, it can handle range
queries with a minimum number of messages. However, whenusing MRF, the path length can be unnecessarily long in somecases; Split-Forward Broadcasting (SFB) is one way to solve
this inefficiency [7].
In SFB, the target range is divided into subranges anddelegated to neighbor nodes in the same way as in MRF.
However, SFB uses a different dividing policy. For a range
query whose target range is R, the first node that receives
the query within R first divides R into two subranges basedon its key. Then, for each of the left and right subranges, itdelegates the subrange divided based on the key of a neighbornode rather than its own key. By repeating this operation foreach node that receives the query, all nodes within the target
range eventually receive the query. Fig. 1 shows an example ofrouting using SFB where Σ = {0, 1}. The translucent green
rectangle represents the target range or subrange, and eachnode within the range is painted green at the level where it
received the query.
However, in some cases, the path length is unnecessarily

long because routing with SFB does not fully utilize the links.
Specifically, it happens because the query is forwarded in aunidirectional manner, even though the links are bidirectional.
To address this inefficiency, we propose a new routing method
for range queries. We compare the existing methods with theproposed method in detail in Section IV.
From the perspective of generality, this paper discusses
ordinary Skip Graph, which does not have additional links.
Therefore, methods that require their own additional links [8]are outside the scope of this paper.
III. P ROPOSED M ETHOD
We propose a new routing method named Detouring Range
Search (DRS), that can reduce the average path length compared to that of SFB, as described in Section II. In thefollowing, we assume that arithmetic operations and absolutevalues are defined on a set of keys, as in DSG. In the
proposed method, the target range is divided into subranges
and delegated to neighbor nodes in the same way as in SFB.
However, we use a different dividing policy from that of SFB.
Specifically, each node that receives a range query estimatesthe center of the subordinate node sequence, i.e., the centerof the node that is adjacent to itself at the highest level andthe node that is adjacent to itself at the next highest level, anddivides the target range into subranges based on the value.
The proposed method with this dividing policy enables nodes
to utilize detour routes and make full use of their routing tables
and existing links. As for the method of estimating the center,as described in II-A, it is difficult to obtain the distribution ofkeys in advance, so we use the average of the two keys.
Fig. 2 shows the dividing position for a right subrange
in the proposed method. localNode is a node that received
a query from another node, or a node that issued a query.
delegationNode, whose key is k1 , is a neighbor node at thehighest level of localNode in the range. lowerNode, whose key
is k2 , is a neighbor node at the next highest level of localNodein the range. In the proposed method, localNode divides
the range at the center of delegationNode and lowerNode,although it divides the range at delegationNode in SFB.
Fig. 3 shows an example of routing with the proposed
method. For a range query whose target range is R, the first
node or delegationNode that receives the query within R or
the delegated range first divides R into two subranges by
its key. Then, for each of the left and right subranges, it
divides the subrange for the center of the subordinate nodesequence and delegates them. By repeating these operations,

Proc. 19th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2022), pp.895-898, January 2021

Search Query

Algorithm 1: Routing process of the proposed method

Target Range: [5, 305]
Level 3

10

35

70

135

142

168

215

135

300

70

Level 2

300

215

35

168

10

142

1: procedure UPON R ECEIVING AT L OCAL(range, query )2:

leftSubRange ← clone of range

3:

leftSubRange.setRightClosedBound(localNode.key )4:rightSubRange ← clone of range

5:

rightSubRange.setLeftClosedBound(localNode.key )6:

UPON R ECEIVING (leftSubRange, query, FALSE)

7:

UPON R ECEIVING (rightSubRange, query, TRUE)

8: end procedure

35

Level 1

10

135
70

168
142

300

9: procedure UPON R ECEIVING(range, query, isRightSide )
10:

215

if isRightSide = TRUE thenneighbors ← routingTable.getRightNeighbors()

11:
Level 0

10

35

70

135

142

168

215

300

12:

else
neighbors ← routingTable.getLeftNeighbors()

Node A

B

C

D

E

F

G

H

13:

000...

101...

011...

110...

001...

100...

010...

111...

14:

end if15:

delegationNode ← neighbors.getDelegationNode(range )16:

if delegationNode 6= NULL thenFig. 3: Example of routing with the proposed method.

all nodes within the target range eventually receive the query.
However, since there is no lower level neighbor node at level0, the subrange is divided by the keys of neighbor nodes anddelegated in the same way as in SFB.
Algorithm 1 provides the pseudo code of the proposed
method. UPON R ECEIVING AT L OCAL is called only once atthe node that receives the query within the target range or thedelegated range. After that, UPON R ECEIVING is called at thatnode.
In the pseudo code, setRightClosedBound and setLeftClosedBound are functions that change the endpoint of
the range to the value specified by the argument and close
the right or left side. Similarly, setRightOpenBound andsetLeftOpenBound are functions that change the endpointof the range to the value specified by the argument and open
it to the right or left. mid is a function that estimates the centerof the two nodes specified by the arguments and returns the
key value.

17:
18:
19:
20:

subRange ← clone of range
lowerNode ← neighbors.getLowerNode(range )if lowerNode 6= NULL thendivideKey ← mid(delegationNode, lowerNode )

21:
22:
23:
24:
25:
26:

else

27:
28:
29:
30:
31:

else

divideKey ← delegationNode.key
end if
if isRightSide = TRUE thensubRange .setLeftClosedBound(divideKey )range .setRightOpenBound(divideKey )subRange .setRightClosedBound(divideKey )range .setLeftOpenBound(divideKey )end ifcall UPON R ECEIVING AT L OCAL(subRange, query ) at

delegationNode
32:
UPON R ECEIVING (range, query, isRightSide )33:
end if34: end procedure

IV. E VALUATION
We conducted simulation experiments to evaluate the path
length within the target range and observed the effect of the
proposed method on the path length. Keys for the experiments
are generated via the following two distributions.
• Uniform distribution• Power-law distribution
For these methods, we used the same distributions as thoseused in the experiments in [10].
The details of each experiment are described in the following sections. The alphabet of the membership vector is fixedat {0, 1}, which is commonly used in the implementation of
Skip Graph. Based on the key generated by the designatedmethod, our simulator constructed Skip Graph with 10,000
nodes, and the average path length was measured by changing
the number of nodes in the target range NR for MRF, SFB,
and the proposed method. The flow of the measurement is asfollows.

1) The leftmost node in the target range issues a range
query.
2) Each node forwards the query with the designated routing method while keeping track of the path length fromthe start node to each node in the target range.
3) After the query is delivered, the simulator calculates theaverage path length.
4) The above procedure is repeated 100 times for the same
topology, and the average value of the 100 trials is
calculated. The above procedure is repeated for fivedifferent topologies, and the average value is calculated.
The start node, as described in [7], is the first node thatreceives the query in the range during actual routing. However,since the position in the target range is not always the same,
we used the leftmost node in the range as the start node, as
in the experiments in [7], to evaluate the performance of themulticast methods in the target range.

Proc. 19th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2022), pp.895-898, January 2021

Average path length

20
16

TABLE I: Comparison of the average path length for a topology
where keys were generated by two different distributions.

MRF
SFB
Proposed

MRF
SFB

12

Proposed8

NR = 10
3.06
3.06
2.22
2.22
2.14
2.14

100
7.82
7.82
5.06
5.06
4.40
4.41

1, 000
12.77
12.77
7.95
7.95
6.56
6.60

10, 000
17.79
17.79
10.90
10.90
8.67
8.75

V. C ONCLUSION

40

key: uniform
key: power
key: uniform
key: power
key: uniform
key: power

10

100

1000

10000

Number of nodes in target range

Fig. 4: Comparison of the average path length for a topology where
keys were generated by a uniform distribution.

A. Uniform distribution
We generated the keys of the nodes to follow a uniform
distribution P {v.key = k} = 2130 (k ∈ {0, 1, ..., 230 − 1})
where v.key is the key of node v. The center estimation mid
2
for this distribution is mid(k1 , k2 ) := k1 +k
2 .
Fig. 4 shows the average path length measured by theprocedure described above. The proposed method has a shorter
average path length than that of the other two methods,
although the three routing methods show a similar tendencywith respect to the change in NR . In the graph in Fig. 4,
compared to SFB, the reduction of the average path length ateach NR is 3.15% (NR = 10), 13.05% (NR = 100), 17.46%(NR = 1, 000), and 20.48% (NR = 10, 000).
B. Power-law distribution
We generated the keys of the
R knodes to follow a power-law
distribution P {v.key ≤ k} = 0 f (κ)dκ (0 ≤ k ≤ 230 ) for aprobability density function f (k) = ck 10 (0 ≤ k ≤ 230 ). Here,R 230
c is a constant that satisfies 0 f (κ)dκ = 1. As mentioned in
Section II-A, the average of two keys works well as the centerof two nodes in many cases, so the mid used in Section IV-A
is also used to estimate the center in this key distribution. The
purpose of using a power-law distribution is to evaluate theeffect of the proposed method on a biased key distribution. For
this purpose, we use the topology from Section IV-A with only
the key value changed to observe the change in the averagepath length for two different key distributions.
Table I compares the results measured by the proceduredescribed above with the results in Section IV-A. For two
different key distributions, a comparable path length is observed for each of the three routing methods. For the proposed
method, the reduction ratio is equivalent to that in Section
IV-A for the two routing methods, indicating that the proposed
method is effective, even when the key distribution is biased.

In this paper, we proposed a new routing method forrange queries in Skip Graph, named Detouring Range Search(DRS). By efficiently using the topology of Skip Graph, theproposed method can deliver a query to all nodes in the target
range with a minimum number of messages and a short path
length. Evaluation experiments show that the proposed method
can reduce the average path length by approximately 20%
compared to that of existing methods.
We confirmed that the proposed method is effective evenwhen the key distribution is biased. Our future work will
include an analytical evaluation of the path length reduction
and an investigation of the center estimation methods.
R EFERENCES[1] E. Rohrer and F. Tschorsch, “Kadcast: A Structured Approach to
Broadcast in Blockchain Networks,” in Proceedings of the 1st ACM
Conference on Advances in Financial Technologies (AFT’19), 2019, pp.
199–213.
[2] R. Banno, Y. Kitagawa, and K. Shudo, “Exploiting semi-structured overlay networks in blockchain systems,” IEICE Communications Express,
2021.
[3] J. Aspnes and G. Shah, “Skip graphs,” ACM Transactions on Algorithms(TALG), vol. 3, no. 4, pp. 37:1–37:25, 2007.
[4] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek,
F. Dabek, and H. Balakrishnan, “Chord: a scalable peer-to-peer lookup
protocol for Internet applications,” IEEE/ACM Transactions on networking, vol. 11, no. 1, pp. 17–32, 2003.
[5] A. Rowstron and P. Druschel, “Pastry: Scalable, decentralized object
location, and routing for large-scale peer-to-peer systems,” in IFIP/ACM
International Conference on Distributed Systems Platforms (Middleware
2001). Springer, 2001, pp. 329–350.
[6] Y. Ishi, Y. Teranishi, M. Yoshida, S. Takeuchi, S. Shimojo, and S. Nishio,“Range-Key Extension of the Skip Graph,” in 2010 IEEE Global
Communications Conference (GLOBECOM 2010). IEEE, 2010, pp.
1–6.
[7] R. Banno and K. Shudo, “An Efficient Routing Method for Range
Queries in Skip Graph,” IEICE TRANSACTIONS on Information and
Systems, vol. E103-D, no. 03, pp. 516–525, 2020.
[8] A. González-Beltrán, P. Milligan, and P. Sage, “Range queries over skip
tree graphs,” Computer Communications, vol. 31, no. 2, pp. 358–374,
2008.
[9] W. Pugh, “Skip lists: a probabilistic alternative to balanced trees,”
Communications of the ACM, vol. 33, no. 6, pp. 668–676, 1990.
[10] T. Kaneko, R. Banno, K. Shudo, K. Abe, and Y. Teranishi, “Detouring
Skip Graph: Efficient Routing via Detour Routes on Skip Graph Topology,” IEEE Open Journal of the Communications Society, vol. 1, pp.
1658–1673, 2020.

Proc. 19th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2022), pp.895-898, January 2021