P-skip graph : an efficient data structure for peer to peer network

Abstract

With the growth of the Internet and the emergence of the trend of moving from desktop computing to client-server computing and finally to distributed computing, a class of distributed network viz. peer-to-peer network has gained huge popularity. Peer-to-peer network displays interesting characteristics of fast queries, updation, deletion, fault-tolerance and much more while lacking any central authority. With a view of changing trend in mind, the major concern of computer experts is to develop an appropriate data structure than can efficiently handle all the desired characteristics of the underlying network. Adjacency Matrix Skip-Webs, Skip-Nets, Skip-List, Distributed Hash Table, and many more data structures form the candidature for peer-to-peer networks, of which, Skip-Graph (evolved version of skip-list) displays the best characteristics. Researchers keep on optimizing the existing data structures according to the need of the area where the data structure is to be applied. Many optimization techniques have been applied to adapt a data structure to a particular scenario and usage of Skip-Graphs is one such option. Skip-Graph help to search and locate a node in a peer-to-peer network efficiently with time complexity being O(log n). However when a hotspot node is searched and queried again and again, the Skip-Graph does not learn or adapt to the situation and still searches traditionally with O(log n) complexity. The main focus of the thesis is to modify traditional Skip-Graph data structure so that it can automatically learn and adapt to the environment in peer-to-peer network. The aim is to use to top most level of the Skip-Graph node to establish a link to the most frequently searched node so that satisfying a trend of similar queries becomes as easy as O(1).