An Undirected Graph Traversal Based Grouping Prediction Method for Data De-duplication

The data capacity of the de-duplication system, which is limited by the memory, is difficult to carry out a large-scale expansion. To solve this problem, the paper proposes a hash table grouping prediction method based on undirected graph traversal. This method exploits the indexing table replacement, which is similar to the virtual memory cache replacement, to expand the storage capacity of the data de-duplication system without increasing the system memory. The hit rate of the grouping prediction and system performance are improved by grouping index entries based on undirected graph traversal. Experimental results show that, based on the cache prefetching and the hash table grouping, the memory consuming takes up 10% of the index table size while the capacity equally rise to 10 times of original. The method can make the index table cache hit rate increased to 87.6%, comparing 47% without group in dataset 1 of our experiment, make the performance acceptable.