With the increase of IoT devices, P2P-based IoT platforms have been attracting attention because of their capabilities of building and maintaining their networks autonomously in a decentralized way. In particular, Skip Graph, which has a low network rebuilding cost and allows range search, is suitable for the platform. However, when data observed at geographically close points have similar values (i.e. when data have strong spatial autocorrelation), existing types of Skip Graph degrade their search performances. In this paper, we propose a query transfer method that enables efficient search even for spatially autocorrelated data by adaptively using two-types of Skip Graph depending on the key-distance to the target key. Simulation results demonstrate that the proposed method can reduce the query transfer distance compared to the existing method even for spatially autocorrelated data.

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.