Membership Proof and Verification in Authenticated Skip Lists Based on Heap

How to keep cloud data intact and available to users is a problem to be solved. Authenticated skip list is an important data structure used in cloud data integrity verification. How to get the membership proof of the element in authenticated skip list efficiently is an important part of authentication. Kaouthar Blibech and Alban Gabillon proposed a head proof and a tail proof algorithms for the membership proof of elements in the authenticated skip list. However, the proposed algorithms are uncorrelated each other and need plateau function. We propose a new algorithm for computing the membership proof for elements in the authenticated skip list by using two stacks, one is for storing traversal chain of leaf node, the other is for storing authentication path for the leaf. The proposed algorithm is simple and effective without needing plateau function. It can also be applicable for other similar binary hash trees.

SLC-index: A scalable skip list-based index for cloud data processing

Due to the increasing number of cloud applications,the amount of data in the cloud shows signs of growing faster than ever before.The nature of cloud computing requires cloud data processing systems that can handle huge volumes of data and have high performance.However,most cloud storage systems currently adopt a hash-like approach to retrieving data that only supports simple keyword-based enquiries,but lacks various forms of information search.Therefore,a scalable and efficient indexing scheme is clearly required.In this paper,we present a skip list-based cloud index,called SLC-index,which is a novel,scalable skip list-based indexing for cloud data processing.The SLC-index offers a two-layered architecture for extending indexing scope and facilitating better throughput.Dynamic load-balancing for the SLC-index is achieved by online migration of index nodes between servers.Furthermore,it is a flexible system due to its dynamic addition and removal of servers.The SLC-index is efficient for both point and range queries.Experimental results show the efficiency of the SLC-index and its usefulness as an alternative approach for cloud-suitable data structures.

Optimized Algorithms for Flexible Length-Based Authenticated Skip List

With the growing trend toward using cloud storage,the problem of efficiently checking and proving data integrity needs more consideration.Many cryptography and security schemes,such as PDP(Provable Data Possession) and POR(Proofs of Retrievability) were proposed for this problem.Although many efficient schemes for static data have been constructed,only a few dynamic schemes exist,such as DPDP(Dynamic Provable Data Possession).But the DPDP scheme falls short when updates are not proportional to a fixed block size.The FlexList-based Dynamic Provable Data Possession(FlexDPDP) was an optimized scheme for DPDP.However,the update operations(insertion,remove,modification)in Flex DPDP scheme only apply to single node at a time,while multiple consecutive nodes operation is more common in practice.To solve this problem,we propose optimized algorithms for multiple consecutive nodes,which including MultiNodes Insert and Verification,MultiNodes Remove and Verification,MultiNodes Modify and Verification.The cost of our optimized algorithms is also analyzed.For m consecutive nodes,an insertion takes O(m) + O(log N) + O(log m),where N is the number of leaf nodes of FlexList,a remove takes O(log/V),and a modification is the same as the original algorithm.Finally,we compare the optimized algorithms with original FlexList through experiences,and the results show that our scheme has the higher efficiency of time and space.

DICE:An Effective Query Result Cache for Distributed Storage Systems

Due to the proliferation of Internet and Intranet,the distributed storage systems have received a lot of attention. These systems span a large number of machines and store huge amount of data for a lot of users.In the distributed storage systems,a row can be directly accessed using a row key.We concentrate on a problem of efficient processing of queries whose predicate is on a column but not a row key.In this paper,we present a cache management technique,called DICE which maintains query results of range queries to support the next range queries.To accelerate the search time of the cached query results,we use modified Interval Ski Lists.In addition,we devise a novel cache replacement policy since DICE maintains an interval rather than a data item.Since our cache replacement policy considers the properties of intervals,our proposed technique is more efficient than traditional buffer replacement algorithms.Our experimental result demonstrates the efficiency of our proposed technique.