Necklace: An Efficient Cuckoo Hashing Scheme for Cloud Storage Services

Date Added: Apr 2014
Format: PDF

With the rapid growth of data, query performance is an important concern in cloud storage applications. To reduce the query response time, cuckoo hashing via d hash functions has been adopted to achieve O (1) query efficiency. However, in practice the cuckoo hashing consumes a large amount of system resources, since an item insertion may suffer from frequent \"Kickout\" operations or even endless loops. In order to address this problem, the authors propose an efficient loop-oblivious scheme, called Necklace, in the cloud. The idea behind Necklace is to minimize data migration among servers and alleviate the collisions in the insertion operation.