# US 11,029,871 B2 · Deduplication using nearest neighbor cluster > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,029,871 B2 - Document ID: US11029871B2 - Status: Granted - Kind: B2 - Application number: 16/412,946 - Filed: 2019-05-15 - Published: 2020-11-19 - Granted: 2021-06-08 - Earliest claimed: 2019-05-15 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Jonathan Krasner; Sweetesh Singh; Steven Chalmer - Web page: https://patentgrep.com/patent/US11029871B2 ## CPC - G06F 3/0641: {De-duplication techniques} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling} - G06F 3/0673: {Single storage device} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06N 20/00: Machine learning - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Disclosed are techniques for data deduplication, which include methods, systems, or computer products for reducing data redundancy in a data storage system comprising searching a cluster of nearest neighbors, wherein the cluster has been created using a locality sensitive hashing algorithm, to determine if a data block has been stored in the data storage system prior to writing the data block. In alternate embodiments, the nearest neighbor clusters could be created using one or more of the following algorithms: k-means clustering algorithm, a k-medoids clustering algorithm, a mean shift algorithm, a generalized method of moment (GMM) algorithm, or a density based spatial clustering of applications with noise (DBSCAN) algorithm. ## Claims ### Claim 1 A method of reducing data redundancy in a data storage system comprising; searching a cluster of nearest neighbors to determine if a data block has been stored in the data storage system prior to writing the data block, wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor. ### Claim 2 (depends on 1) The method of claim 1, further comprising: writing the data block if no match is found, else storing mapping information for the data block if a match is found within the cluster of nearest neighbors. ### Claim 3 (depends on 1) The method of claim 1, wherein the nearest neighbor cluster is created with a machine learning module or an offload engine. ### Claim 4 (depends on 1) The method of claim 1, wherein the locality sensitive hashing function is a secure hash algorithm 1 (“SHA-1”) or a Message Digest 5 (“MD5”) algorithm. ### Claim 5 (depends on 1) The method of claim 1 further comprising: compressing one or more data sets within the cluster of nearest neighbors. ### Claim 6 (depends on 1) The method of claim 1, wherein the cluster of nearest neighbors includes a plurality of master blocks. ### Claim 7 A system comprising: one or more processors; and a memory configured to: search a cluster of nearest neighbors to determine if a data block has been stored in a data storage system prior to writing the data block, wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor. ### Claim 8 (depends on 7) The system of claim 7 further configured to: write the data block if no match is found, else storing mapping information for the data block if a match is found within the cluster of nearest neighbors. ### Claim 9 (depends on 7) The system of claim 7, wherein the nearest neighbor cluster is created with a machine learning module or an offload engine. ### Claim 10 (depends on 7) The system of claim 7, wherein the locality sensitive hashing function is a secure hash algorithm 1 (“SHA-1”) or a Message Digest 5 (“MD5”) algorithm. ### Claim 11 (depends on 7) The system of claim 7 further configured to: compress one or more data sets within the cluster of nearest neighbors. ### Claim 12 (depends on 7) The system of claim 7, wherein the cluster of nearest neighbors includes a plurality of master blocks. ### Claim 13 A non-transitory, computer readable medium comprising code stored thereon that, when executed, performs the following acts: searching a cluster of nearest neighbors to determine if a data block has been stored in a data storage system prior to writing the data block, wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor. ### Claim 14 (depends on 13) The non-transitory, computer readable medium of claim 13, wherein the code stored thereon, when executed, additionally performs the following acts: writing the data block if no match is found, else storing mapping information for the data block if a match is found within the cluster of nearest neighbors. ### Claim 15 (depends on 13) The non-transitory, computer readable medium of claim 13, wherein the nearest neighbor cluster is created with a machine learning module or an offload engine. ### Claim 16 (depends on 13) The non-transitory, computer readable medium of claim 13, wherein the locality sensitive hashing function is a secure hash algorithm 1 (“SHA-1”) or a Message Digest 5 (“MD5”) algorithm. ### Claim 17 (depends on 13) The non-transitory, computer readable medium of claim 13, wherein the cluster of nearest neighbors includes a plurality of master blocks. ### Claim 18 A non-transitory, computer readable medium comprising code stored thereon that, when executed, performs the following acts: searching a cluster of nearest neighbors to determine if a data block has been stored in a data storage system prior to writing the data block wherein the cluster has been created using a locality sensitive hashing function and determination of nearest neighbors is made by evaluating a plurality of hash values placed in a coordinate system having at least four dimensions in order to determine a distance between each neighbor; and compressing one or more data sets within the cluster of nearest neighbors.