Patent ID: 8397028
Filing Date: 2013-03-12
Classification: G06F

Abstract:
1. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising: selecting a selected index entry for eviction from a bucket of index entries as a function of a time value, a utility value, and a precedence value, where an index entry in the bucket of index entries comprises a portion of a hash value, a memory location, and a utility value describing a usefulness of the index entry; and providing an index entry identifier that identifies the selected index entry, where the bucket of index entries is a bucket associated with a hash-bucket data structure that stores a portion of a data deduplication index, where the hash-bucket data structure is stored as an array in random access memory (RAM), where the array is divided into N buckets of size M, where N and M are integers, where a ranking value is generated for the index entry as a function of the time value and the precedence value when the index entry has not been accessed by an index lookup, where a ranking value is generated for the index entry as a function of the time value, the utility value, and the precedence value when the index entry has been accessed by an index lookup, and where index entries in the bucket of index entries are ranked according to ranking values.