Skip Suffix Array: A Partial Match Retrieval Method
on Structured Overlay Networks
Ryohei Banno and Kazuyuki Shudo
Tokyo Institute of Technology, Tokyo, Japan
Email: banno@computer.org

Abstract—Structured overlay networks provide superior scalability and robustness suitable for large scale distributed systems.
However, typical algorithms’ ability to handle complex queries islimited; consequently, their range of applications is also limited.
We propose a partial match retrieval method for structured
overlay networks that we refer to as Skip Suffix Array (SSA).
SSA integrates the concept of suffix arrays with Skip Graph,
which is a distributed range-queriable data structure. In addition,
we introduce a unique routing method for delivering partial
match queries. SSA achieves lower communication cost andbetter load balancing compared to some existing methods forpartial match retrieval, as well as its search time is suppressed toO(log N ) where N is the number of nodes. Experimental results
demonstrate that SSA can reduce the average path length andthe average number of messages by more than 85% compared
to existing methods, under experimental conditions with 10, 000
nodes and search words of length 8.
Index Terms—Overlay networks, partial match retrieval, peerto-peer networks, skip graph, suffix array

I. I NTRODUCTION
Structured overlay networks, a type of peer-to-peer network,
are promising techniques to obtain scalability and robustness
in large scale distributed systems. Structured overlay networks
are attracting significant academic and industrial interest due
to their applicability to data storage [1], publish/subscribe
messaging [2] and Internet of Things (IoT) systems [3].
One of the challenges in structured overlay networks ishandling complex queries. We focus on partial match retrieval
which is required to realize flexible search in data storage
and IoT systems, flexible filtering in publish/subscribe messaging, etc. Although typical algorithms for structured overlay
networks, such as Chord [4] and Pastry [5], cannot achieve
partial match retrieval, some existing methods can [6], [7].
However, these existing methods have some inefficiencies
including large communication costs and load imbalance.
In this paper, we propose Skip Suffix Array (SSA), a methodthat enables partial match retrieval on structured overlay
networks. SSA integrates the concept of suffix arrays [8], adata structure for string searches, with Skip Graph [9], a distributed range-queriable data structure. In addition, we extend
a state-of-the-art routing algorithm for Skip Graph to deliver
partial match queries to corresponding nodes efficiently. SSA
achieves lower communication costs and better load balancing
This work was supported in part by SECOM Science and Technology
Foundation, in part by New Energy and Industrial Technology Development
Organization (NEDO), and in part by JSPS KAKENHI Grant No.19K20253.

compared to existing methods. In addition, its search time issuppressed to O(log N ), where N is the number of nodes.
The primary contributions of this paper can be summarized
as follows.
We show the basic design of the proposed SSA methodthat integrates suffix arrays and Skip Graph.
• We present a routing method to deliver partial match
queries.
• We clarify the characteristics and effectiveness of SSA
by analytical and experimental comparisons with existing
methods.
•

Note that this paper is an extended version of our previous work [10], which reported the basic idea (in Japanese).
We extended the previous version by improving the routing
protocol to reduce the path length, and we redesigned andreconducted experiments. Specifically, the differences include:
proposal of an improved routing method (Section III-D),
quantitative evaluation that includes a comparison with ourprevious method and more existing methods (Section V).
The remainder of this paper is organized as follows. Section II introduces related studies on partial match retrieval on
overlay networks. Section III explains the proposed method.
Analytical comparisons with existing methods are discussed
in Section IV. Section V presents experimental evaluation.
Conclusions and suggestions for future work are given in
Section VI.
II. R ELATED WORK
Several existing methods attempt to provide partial match
retrieval on structured overlay networks.
Preliminary to discussing those methods, we define partial
match retrieval by assuming the following.
Each node of an overlay network has one or more labels,
which are to search.
• A label is a sequence of characters, denoted a1 a2 ...aL
where the length of the label is L.
• A set of substrings of a label lb is denoted Slb ={ai ai+1 ...aj | 1 ≤ i ≤ j ≤ L}.
•

Definition 1. Assuming S is a set of finite strings, partial
match retrieval is defined as follows: if a node issues a querywith a search word s ∈ S, the query is delivered to all nodes
which have a label lb such that s ∈ Slb .

Proc. 34th Int'l Conf. on Information Networking (ICOIN 2020),
pp.487-492, January 2020

ba$

ba$

$

$

1000
100
10
1

0

500

1000

1500

2000

2500

# of hashtags

$

6000

1000

Frequency of 3-gram

ba

10000

ba

Frequency of 2-gram

a

100
10
1

2000
0

0

Rank

Fig. 1. Example of suffix
tree

4000

(a) 2-gram

5000

10000
Rank

PIER [6], [11] is an approach to handle a partial match
query as a combination of multiple exact-match queries. In
a preprocess, each node divides its labels into n-grams. For
example, a label “computer” is divided into seven substrings
as 2-grams, i.e., “co”, “om”, “mp”, “pu”, “ut”, “te” and “er”.
Subsequently, the node stores its identifier, e.g., IP address
and/or the label, in a distributed hash table (DHT) [4], [5] witha key of each divided n-gram. When a node issues a partial
match query, its search word is also divided into n-grams. For
each n-gram, the issuer node retrieves a set of node IDs fromthe DHT using the n-gram as a key. Then, the node counts thenumber of appearances of each node ID in the obtained sets.
If there are node IDs such that the number is the same as thenumber of n-grams of the search word, they are considered as
nodes having matching labels. Finally, the issuer can deliver
the query to the corresponding nodes.
DST [7] constructs a suffix tree, a data structure capable ofpartial match queries, over a DHT. Fig. 1 shows an example
of a suffix tree for the string “ababa”. Substrings are mappedto each edge such that a sequence of substrings from a rootedge to a leaf edge represents a single suffix. The character “$”
indicates the end of the suffixes. In DST, each root edge of thesuffix tree is stored in the DHT with a key of the first characterof its corresponding substring. Stored data includes identifiersof child edges. Edges besides root edges are also stored in the
DHT with keys of IDs given by their own parent edge. On eachleaf edge, IDs of nodes whose labels have the corresponding
suffix are stored. When a node issues a partial match query, it
first retrieves a root edge from the DHT by specifying the firstcharacter of the search word as a key. Thereafter, by retrieving
the corresponding child edge on the DHT recursively, it canobtain IDs of nodes holding matching labels if they exist.

0

10

20

30

40

50

60

70

Rank

(b) 3-gram

Fig. 2. Deviation of appearance frequencies of n-grams

A. Existing methods

15000

Fig. 3. Imbalance of matching hashtags among
first charactersobtained from Twitter1 . Note that the average length of thesehashtags was 10.154, whereas the number of 2-grams and 3grams were 2, 442 and 14, 587 respectively. As can be seen,
only a few n-grams appear hundreds or thousands of times,
while most appear less than 10 times. Since all node IDs
corresponding to an n-gram are stored on a single node in
PIER, such deviation is directly reflected in the load of each
node.
Similarly, DST also involves load imbalance. There is alimited number of root edges, and the appearance frequenciesof their first characters are biased. Fig. 3 shows the number ofcorresponding hashtags for each initial character. Obviously, anode responsible for a character of high rank tends to have aheavier load because every query begins from one of the rootedges.
2) High communication costs: PIER performs a lookup in
a DHT for each n-gram of a search word. Thus, one partial
match query requires communication cost proportional to thelength of its search word. Likewise, DST also requires a large
number of messages due to its mechanism, i.e., a lookup in a
DHT occurs for each transition from a parent edge to its childedge.
3) n-gram related issues: Since PIER utilizes n-grams,
there could be false positive results. For example, the searchword “sea” can match the label “ease”. Such cases cause
increased communication costs.
In addition, a search word must be equal to or longer thann of n-grams.
III. S KIP S UFFIX A RRAY
The proposed SSA partial match retrieval method can
improve the inefficient aspects of the existing methods by
integrating suffix arrays with Skip Graph.
A. Suffix array

B. Inefficient aspects of existing approaches
Both PIER and DST have inefficiencies from some perspectives.
1) Load imbalance: One matter of concern is load imbalance. Namely, they are heavily affected by deviations in theappearance frequencies of keys.
In PIER, n-grams are used as keys in a DHT. Generally,
the appearance frequencies of n-grams are largely biased.
Fig. 2 (a) and Fig. 2 (b) show the deviation of the appearance frequencies of n-grams, using 10, 000 English hashtags

A suffix array [8] is a sorted array of all suffixes of a string.
For example, the suffix array of a string “computer” is shownin Table I. When a suffix array is given, we can find theposition of an arbitrary substring efficiently by binary searchon the suffix array.
B. Skip Graph
Skip Graph [9] is one of the algorithms for structured overlay networks, known to handle range queries effectively. Each
1 The hashtags are obtained by using Twitter API on February 14th, 2019.

Proc. 34th Int'l Conf. on Information Networking (ICOIN 2020),
pp.487-492, January 2020

Level 3

TABLE IE XAMPLE OF SUFFIX
ARRAY

Suffixcomputerer
mputeromputer
puter
r
ter
uter

Position
0
6
2
1
3
7
5
4

Level 2
Level 1
Level 0
Key

7
21

7

21

7
7
Node A
001

21
Node B
10

33

148

275

399

Level 3

148

275

399

Level 2

275

399

33

148

33
Node C
01

148
Node D000275
Node E
110

10

13

13

2 In our previous work [10], we used MRF [15]. The difference between
SFB and MRF is disscussed in [14].

36399Node F
111

Level 1
Level 0

40

45

29

45

40

47
47

36
13

10

29

40

27

10
Node A000

13
Node B
100

27
Node C
010

47

36
29
Node D110

36
Node E001

45
40
Node F
101

45
Node G
011

47
Node H111

Fig. 5. Example of routing by SFB

Fig. 4. Example of Skip Graph

C. Topology of SSA
In SSA, we combine suffix arrays with Skip Graph to enable
partial match retrieval.
First, each node divides its labels into suffixes. Then, every
suffix is inserted in the Skip Graph as a virtual node. Although
in the usual Skip Graph each node has its own membership
vector, with SSA membership vectors are assigned for eachphysical node. Virtual nodes of the same physical node havethe same membership vector. This enables the height to be

27

29

10

Membership vector

node has a key and a random sequence called a membership
vector. A membership vector consists of symbols contained ina finite alphabet Σ, which is typically Σ = {0, 1}. As shownin Fig. 4, Skip Graph creates a multiplex structure of a skip
list [12]. Level 0 is a doubly linked list that consists of allnodes sorted in key order. In level i, each node composes a
doubly linked list with nodes whose membership vectors havethe same first i digits.
A node can issue a query by specifying a target key. The
query is forwarded among nodes in the same manner as a skip
list, i.e., it skips a long distance at higher levels and gradually
moves down to level 0. The path length is O(log N ) where
the number of nodes is N . Note that the size of the routing
table on each node is also O(log N ).
Since nodes are sorted in key order, each node can also
perform a range search; a query is delivered to nodes whose
keys are included in the specified range. Methods for routing
range queries in Skip Graph have been proposed [13], [14].
In SSA, we use SFB [14] due to its shorter path lengths andlower communication costs2 .
SFB utilizes a divide-and-conquer approach. Each nodethat receives a range query divides the target range into
subranges based on the keys of its neighbor nodes within therange, and then forwards the query with each subrange to thecorresponding neighbor node. As shown in Fig. 5, when node
A receives a range query with a target range (depicted as a blue
rounded rectangle at level 3) it first divides the range by the
key of node E into two subranges. Subsequently, it forwards
one of the two, the farther, to node E. Then, it repeats thisprocess for the remaining subranges at lower levels recursively.
Hereafter, we refer to a key of Skip Graph as a “label” asdescribed in Section I.

27

foo

Level 2

Level 1
Level 0

az
az

baz

ar
ar

o

oo

baz

z
foo

o

oo

bar
az

bar

z
r

baz

Node A (11)foooNode B (00)

oo

r

z

Node C (10)Fig. 6. Example SSA topology

suppressed, which is reflected in the size of routing tables, toO(log N ) where N is the number of physical nodes [15].
Fig. 6 shows an example of SSA topology. In this topology,
there are three physical nodes, A, B, and C labeled “foo”,“bar”, and “baz”, with membership vectors 11, 00, and 10
respectively. As can be seen, the level 0 list forms a suffix arraysuch that all physical nodes having a label that corresponds
to one substring are placed continuously. Therefore, we canperform partial match retrieval efficiently by range search. For
example, if a partial match query is issued with the searchword “ba”, it is handled as a range query where the range
includes keys starting with “ba”. This query is eventually
delivered to two virtual nodes, i.e., “bar” of node B and “baz”
of node C.
Note that since SSA utilizes the topology maintenancemechanism of Skip Graph, methods aiming at the improvement of the topology can be applied [16]–[18]. By using thesemethods according to the characteristic of each applicationsuch as the locality of node placement, better performancee.g., shorter path lengths might be obtained.
D. Routing in SSA
As mentioned previously, we use SFB [14] in SSA. Although SFB achieves a shorter average path length than otherrouting methods [13], [15], utilizing it in SSA can cause
inefficient routing paths because SFB does not assume theuse of virtual nodes.
Considering virtual node VN1 attempts to forward subrange
SR1 to virtual node VN2 and subrange SR2 to virtual node
VN3 , the possible undesirable cases are described as follows.
(i) VN2 or VN3 is of the same physical node as VN1 . For
example, if nodes A and G in Fig. 5 are of the same

Proc. 34th Int'l Conf. on Information Networking (ICOIN 2020),
pp.487-492, January 2020

physical node, the physical node receives the same query
twice.
(ii) VN2 and VN3 are of the same physical node. For
example, if nodes C E in Fig. 5 are of the same physicalnode, the physical node receives the same query twice.
(iii) A virtual node of the physical node of VN2 is containedin SR2 . For example, if nodes B and F in Fig. 5 are of
the same physical node, the physical node receives thesame query twice.
To avoid these cases, we propose Multi-Key SFB (MK-SFB)
which extends SFB by aggregating the query processing andforwarding as like Multi-key Skip Graph [15]. MK-SFB isdesigned to work effectively under the assumption that eachphysical node may have multiple keys (i.e., multiple virtual
nodes).
When a node receives a range query, the node first confirms
whether the range contains virtual nodes of the same physicalnode. If such virtual nodes exist, it divides the range by thekeys of the virtual nodes and delegates subranges to the nodes
as internal processes of the physical node. This avoids case(i).
Then, each of the above virtual nodes divides the subrange
it is responsible for into smaller subranges according to SFB,
but not yet forwards the subranges. Inside the physical node,
subranges to be forwarded to the same physical node are
aggregated and forwarded collectively to the physical node.
This avoids case (ii).
In addition, when each virtual node divides a subrange, it
can consider “sibling” virtual nodes of its neighbor virtual
node. For example, let nodes B and F be of the same physicalnode in Fig. 5. Since node B is a neighbor of node A, node A
can obtain the label of the physical node of node B. Therefore,
node A can easily know the existence of node F by considering
the label’s suffixes. In this case, node A divides the subrange
into four smaller subranges by nodes F, E, C, and B. As aresult, case (iii) can be avoided. Although this technique relieson the characteristic of SSA, i.e., a key of a virtual node is asuffix of the key of its physical node, it can also be applied toother cases that do not have such characteristic by exchanging
the information of child virtual nodes among connected nodes.
IV. A NALYTICAL COMPARISON
Here, we analytically compare SSA to the existing methods
described in Section II-A. In this section, we use the following
notations.
• N : number of physical nodes• M : average number of labels for each physical node
• Lavg : average length of labels• Ls : length of search word s
Table II shows a summary of the comparison.
Relative to search time, PIER and DST requireO(Ls log N ), because they perform lookups in a DHT
multiple times according to the length of a search word. For
SSA, the height of the Skip Graph is O(log N ), because
membership vectors are assigned for each physical node. In

TABLE IIC OMPARISON OF PARTIAL MATCH RETRIEVAL METHODS
PIER
DST
SSA

Search timeO(Ls log N )O(Ls log N )O(log N )Storage cost
O(M Lavg + log N )O(M Lavg + log N )O(M Lavg log N )addition, the number of physical nodes at level i between
two virtual nodes connected at level i + 1 is expected to beO(1)3 ; therefore, SSA incurs O(log N ) search time. Notethat each method can be improved in some manner, e.g.,parallel processing and caching; however, such improvements
are beyond the scope of this paper to clarify the essential
differences.
From a storage cost perspective, PIER requires that eachnode has n-gram data and the routing table of a DHT.
Thus, the storage cost is O(M Lavg + log N ). For DST, eachnode has the routing table of a DHT and the edges of a
suffix tree it is responsible for. Here, the number of edgesis O(M Lavg N ); therefore, the storage cost on each DST
node is O(M Lavg + log N ). In SSA, each physical node
has M Lavg virtual nodes on average; thus, the storage cost
is expected to be O(M Lavg log N ). Although this indicates
SSA is disadvantageous, existing methods suffer from load
imbalance (Section II-B). Since the load on each node isunpredictable, ensuring sufficient storage capacity for the
possible worst case may be required. Note that we evaluateload imbalance in Section V-C.
V. E VALUATION
We evaluated SSA in simulation experiments. The simulation program was implemented in Java (Java SE Development
Kit 8) and run on a machine with a quad-core CPU (Intel Corei7-8650U 1.90 GHz), 16 GB memory, and the Windows 10
operating system.
Here, the following five methods were evaluated.
SSA: proposed method
SSA (old): previous version of SSA [10]PIER (3-gram) : PIER using 3-grams
PIER (2-gram) : PIER using 2-grams
DST
: DST
In this evaluation, the simulator generated 10, 000 nodes
for each method. Each node has a single label from the setof hashtags described in Section II-B (without duplication).
We considered six search word length patterns (search words
length: 3, 4, 5, 6, 7, 8) and prepared 1, 000 random partial
match queries for each pattern. Here, each query had two
kind of information, i.e., a search word and a source physicalnode of partial match retrieval. The former was selected
randomly from existing substrings of corresponding length in
the hashtags. The latter was also selected randomly from the
10, 000 nodes such that the label of the selected node did notcontain the given search word.
3 Strictly speaking, O(|Σ|) where |Σ| is the size of the alphabet formembership vectors.

Proc. 34th Int'l Conf. on Information Networking (ICOIN 2020),
pp.487-492, January 2020

100

80
SSA

60

SSA (old)

40

PIER (3-gram)
PIER (2-gram)

20
0

DST
3

4
5
6
7
Search word length

8Fig. 7. Average path length in 1, 000 queries

For PIER and DST, we used a DHT built on top of Skip
Graph. This was realized using “Routing by Numeric ID” in
SkipNet [19]. Using a DHT on top of Skip Graph is convenient
relative to fairness of the experimental conditions, such as
routing table size.
For all experiments, we set the size of the alphabet formembership vectors to 2.
A. Search time
As mentioned in Section II-A, existing methods require
multiple exact match queries to process a single partial match
query. In contrast, SSA can perform partial match retrieval
using a single range query.
To confirm the influence on search time, we performed anexperiment to measure the average path length. For each searchword length, the simulator performed each of 1, 000 queries
and calculated the average path length from the physical source
node to the corresponding physical nodes. Then, the averageof the 1, 000 queries was calculated.
Fig. 7 shows the results. In PIER, the average path length
increased linearly with search word length, and that of DST
increased relatively gently. In contrast, SSA and SSA (old)were essentially unaffected by search word length. With asearch word length of 8, the proposed SSA reduced the averagepath length by more than 85% compared to the existing
methods.
Due to the improvement of the routing algorithm (Section III-D), the average path length of SSA is shorter than thatof SSA (old), especially when using short search word lengths.
In principle, since the improvement is for routing within atarget range, the difference should be more prominent when
the number of results is large (i.e., the target range is wide). In
fact, we confirmed this in Fig. 8 which shows the average path
length of queries with greater than 100 search results. In these
queries, SSA reduced the average path length by more than
44% compared to SSA (old) with every search word length.
B. Communication cost
We also confirmed the tendencies of communication cost.
Similar to the search time experiment, the simulator performed
each of 1, 000 queries and counted the number of messages
exchanged among physical nodes for each search word length.
Then, the average of the 1, 000 queries was calculated.
Fig. 9 shows the results. Here, for all methods, search word
length of 3 caused a relatively larger number of messages.

Average path length

Average path length

100

80
SSA

60

SSA (old)

40

PIER (3-gram)
PIER (2-gram)

20
0

DST
3

4

5
6
7
Search word length

8Fig. 8. Average path length in queries with greater than 100 results

This is considered to depend on the number of search results.
Fig. 10 shows the average number of results for each searchword length. As can be seen, shorter search word lengths
resulted in a larger average number of results. Especially in
PIER (2-gram), a short search word also caused false positive
results. Note that SSA, SSA (old), and DST yielded the same
number of results because they do not involve false positive
results. Fig. 11 shows the difference in the false positive rate
between PIER (2-gram) and PIER (3-gram). Using 3-gram
rather than 2-gram appears to be effective relative to avoiding
the influence of false positive; however, it has a disadvantage
of inability to search by words of two or less length.
In Fig. 9, PIER seems to have the tendency of proportional
increase to the search word length. DST appears to be insensitive to search word length, despite the increasing tendency
of its average path length. This also appears to be caused by
the number of search results, i.e., longer search word length
simultaneously brings about longer average path length anda smaller average number of search results. Nevertheless, theaverage number of messages of PIER and DST is quite larger
than SSA and SSA (old). With a search word length of 8, theproposed SSA reduced the number of messages by more than
85% compared to the existing methods.
C. Load balance
As described in Section II-B, PIER and DST involve load
imbalance. Fig. 12 and Fig. 13 plot the number of messages
and storage cost on each node in descending order, respectively. The number of messages was measured using searchword length of 8. The storage cost is the sum of the numberof routing table’s entries and the number of node IDs storedwith n-grams (PIER) or edges (DST).
As shown in Fig. 12, SSA and SSA (old) have relatively
small deviation compared to PIER and DST.
As shown in Fig. 13, SSA and SSA (old) tend to havegreater storage cost than PIER and DST; however, the deviations are small. Note that a good feature of the proposed
SSA is storage cost predictability. The storage cost of eachnode in SSA is dependent on the number of labels (one in thisevaluation) which the node has and their length. In contrast, inthe existing methods, each node cannot know its storage cost inadvance because the data stored on each node are determinedby cryptographic hash functions. Fig. 14 shows the label lengthfor each storage cost rank. Here, the results are smoothedwith the moving average according to a subset size of 100.

Proc. 34th Int'l Conf. on Information Networking (ICOIN 2020),
pp.487-492, January 2020

SSA

60

SSA (old)

40

PIER (3-gram)
PIER (2-gram)

20

DST

0

3

4
5
6
7
Search word length

8Fig. 9. Average number of messages

36
32
28
24
20
16
12
8
4
0

0.3

SSA/SSA (old)/DST
PIER (3-gram)
PIER (2-gram)
3

4
5
6
7
Search word length

False positive rate

80

Average # of results

Average # of messages

100

PIER (3-gram)
PIER (2-gram)

1

DST
1

10

100
Rank

1000

10000

Fig. 12. Number of messages on each node

3

4

5
6
7
Search word length

8

100

1000

SSA/SSA (old)PIER (3-gram)

100

PIER (2-gram)
DST

10PIER (3-gram)

0.05

Fig. 11. False positive rate in PIER

1

10

100
Rank

1000

10000

Fig. 13. Storage cost on each node

As shown, it is clear that SSA and SSA (old) demonstrate asimilar tendency to that shown in Fig. 13, whereas the existing
methods appear to have no correlation with storage cost rank.
Such a feature in the existing methods may require that eachnode ensures sufficient storage capacity for the possible worst
case.
VI. C ONCLUSION
In this paper, we have proposed SSA to provide partial
match retrieval capability on overlay networks. We have also
proposed MK-SFB which aggregates the query processing andforwarding for effective routing in SSA.
The proposed SSA yields lower communication costs andbetter load predictability compared to existing methods. The
experimental results demonstrate that the proposed SSA reduces both the average path length and average number ofmessages by greater than 85% compared to the existing PIER
and DST methods when using search word length of 8.
Future work includes improvement of storage costs andproviding capabilities of complex queries other than partial
match retrieval such as regular expression.
R EFERENCES[1] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman,
A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo:
Amazon’s highly available key-value store,” in Proc. ACM SIGOPS
Symp. Operating Syst. Principles, Oct. 2007, pp. 205–220.
[2] T. Akiyama, Y. Teranishi, R. Banno, K. Iida, and Y. Kawai, “Scalable
pub/sub system using OpenFlow control,” J. Inf. Process., vol. 24, no. 4,
pp. 635–646, Jul. 2016.
[3] D. Wu, D. I. Arkhipov, E. Asmare, Z. Qin, and J. A. McCann, “UbiFlow:
Mobility management in urban-scale software defined IoT,” in Proc.
IEEE Int. Conf. Comput. Commun., Apr. 2015, pp. 208–216.
[4] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan,“Chord : A scalable peer-to-peer lookup service for internet applications,” in Proc. Conf. ACM Special Interest Group Data Commun., Aug.
2001, pp. 149–160.

Label length

10

PIER (2-gram)

0.1

Fig. 10. Average number of search results

Storage cost

# of messages

SSA
SSA (old)

0.2
0.15

0

8

10000
100

0.25

SSA/SSA (old)10

PIER (3-gram)
PIER (2-gram)
DST

1

1

10
100
1000
Storage cost rank

10000

Fig. 14. Label length for each storage cost rank

[5] A. Rowstron and P. Druschel, “Pastry: Scalable, decentralized object
location, and routing for large-scale peer-to-peer systems,” in Proc.
IFIP/ACM Int. Conf. Distrib. Syst. Platforms and Open Distrib. Process.,
Nov. 2001, pp. 329–350.
[6] R. J. Huebsch, “PIER: Internet scale P2P query processing with distributed hash tables,” Ph.D. dissertation, Dept. Elect. Eng. Comput. Sci.,
Univ. California, Berkeley, CA, USA, Mar. 2008.
[7] H. Zhuge and L. Feng, “Distributed suffix tree overlay for peer-to-peer
search,” IEEE Trans. Knowl. Data Eng., vol. 20, no. 2, pp. 276–285,
Feb. 2008.
[8] U. Manber and E. W. Myers, “Suffix Arrays: A New Method for OnLine String Searches,” SIAM J. Comput., vol. 22, no. 5, pp. 935–948,
Oct. 1993.
[9] J. Aspnes and G. Shah, “Skip Graphs,” ACM Trans. Algorithms, vol. 3,
no. 4, pp. 37:1–37:25, Nov. 2007.
[10] R. Banno, H. Sato, S. Oyama, and M. Kurihara, “A partial match
retrieval method on P2P networks using Skip Graph and suffix array,”Comput. Softw., vol. 29, no. 3, pp. 164–180, Jul. 2012 (in Japanese).
[11] M. Harren, J. M. Hellerstein, R. Huebsch, B. T. Loo, S. Shenker, and
I. Stoica, “Complex queries in DHT-based peer-to-peer networks,” inProc. Int. Workshop Peer-to-Peer Syst., Mar. 2002, pp. 242–250.
[12] W. Pugh, “Skip Lists : A probabilistic alternative to balanced trees,”
Commun. ACM, vol. 33, no. 6, pp. 668–676, Jun. 1990.
[13] A. G. Beltran, P. Milligan, and P. Sage, “Range queries over Skip Tree
Graphs,” Comput. Commun., vol. 31, no. 2, pp. 358–374, Feb. 2008.
[14] R. Banno, T. Fujino, S. Takeuchi, and M. Takemoto, “SFB: A scalable
method for handling range queries on Skip Graphs,” IEICE Commun.
Express, vol. 4, no. 1, pp. 14–19, Jan. 2015.
[15] Y. Konishi, M. Yoshida, S. Takeuchi, Y. Teranishi, K. Harumoto, andS. Shimojo, “An extension of Skip Graph to store multiple keys on
single node,” J. Inform. Process. Soc. Jpn. (in Japanese), vol. 49, no. 9,
pp. 3223–3233, Sep. 2008.
[16] F. Makikawa, T. Tsuchiya, and T. Kikuno, “Balance and proximity-aware
Skip Graph construction,” in Proc. Int. Conf. Netw. Comput., Nov 2010,
pp. 268–271.
[17] Y. Hassanzadeh-Nazarabadi, A. Küpçü, and Öznur Özkasap, “Locality
aware Skip Graph,” in Proc. IEEE Int. Conf. Distrib. Comput. Syst.
Workshops, June 2015, pp. 105–111.
[18] T. Kawaguchi, R. Banno, M. Hojo, M. Ohnishi, and K. Shudo, “SelfRefining Skip Graph: Skip Graph approaching to an ideal topology,” inProc. IEEE Consumer Commun. Netw. Conf., Jan. 2017, pp. 441–448.
[19] N. J. A. Harvey, J. Dunagan, M. B. Jones, S. Saroiu, M. Theimer, andA. Wolman, “SkipNet: A scalable overlay network with practical locality
properties,” in Proc. USENIX Symp. Internet Technologies and Syst.,
Mar. 2003, pp. 9–23.

Proc. 34th Int'l Conf. on Information Networking (ICOIN 2020),
pp.487-492, January 2020