Memory optimized algorithm for evaluating deduplication hashes for large data sets
AssigneeEMC IP Holding Company LLC
InventorsAmro Magdi Mahmoud Sayed Khalifa, Angelo Reis
Life of this patent
Estimating the term…
Abstract
One example method includes performing a hash of data to generate a hash value, checking a binary trie to determine if the hash value has previously been entered into the binary trie, if the hash value has previously been entered in the binary trie, declaring the data as a duplicate of other data, and if the hash value has not been previously entered in the binary trie, updating the binary trie to include the hash value.
Claims18
A method, comprising:
- performing a hash of data to generate a hash value;
- converting the hash to at least one bit array, wherein a size of the at least one bit array is based on a size of a binary trie;
- checking the binary trie to determine if the hash value has previously been entered into the binary trie;
- if the hash value has previously been entered in the binary trie, declaring the data as a duplicate of other data;
- and
- if the hash value has not been previously entered in the binary trie, updating the binary trie to include the hash value and the at least one bit array corresponding to the binary trie is also updated to reflect the hash value.
A non-transitory computer readable storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
- performing a hash of data to generate a hash value;
- converting the hash to at least one bit array, wherein a size of the at least one bit array is based on a size of a binary trie;
- checking the binary trie to determine if the hash value has previously been entered into the binary trie;
- if the hash value has previously been entered in the binary trie, declaring the data as a duplicate of other data;
- and
- if the hash value has not been previously entered in the binary trie, updating the binary trie to include the hash value and the at least one bit array corresponding to the binary trie is also updated to reflect the hash value.
Dependencies are inferred from the claim text.