Adaptive Probabilistic Skip Graph

Abstract

Mining of massive data sets is the need of the hour in present computer science industry. The exponential growth in the number of users on internet and volume of available data has lead to the invention of variants of the algorithms and data structures traditionally used in peer to peer networks. Many data structures like adjacency matrix, skip webs, hash tables, skip lists and skip graphs have been proposed to represent the peer to peer networks. The data structure to be used depends upon the requirements of the area where it is being implemented. Available data structures do not seem to be quite efficient in handling the current volume of big data. There is an imminent requirement of data structures which are dynamic and adaptive to the current trends of data. This thesis explores usage of one of these data structures, skip graph, a variant of skip list for peer to peer networks. The existing algorithm for searching in skip graph has O(log n) time complexity which can be further decreased by reforming the present structure as discussed in the proposed approach named as Adaptive Probabilistic Skip Graph. Modifications have been proposed in the scenario where a node is repeatedly being queried by a certain node and it has been experimentally verified that in such scenarios, the search time reduces drastically. The major focus of the thesis has been on optimizing the search algorithm by adding probability vector in the basic structure of the skip graph node.