# US 2023/0057692 A1 · Optimal cluster selection in hierarchical clustering of files

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0057692 A1
- Document ID: US20230057692A1
- Status: Published application
- Kind: A1
- Application number: 17/405,272
- Filed: 2021-08-18
- Published: 2023-02-23
- Earliest claimed: 2021-08-18
- Assignees: EMC IP Holding Company LLC
- Applicants: EMC IP Holding Company LLC
- Inventors: Tony Tzeming Wong; Smriti Thakkar
- Web page: https://patentgrep.com/patent/US20230057692A1

## CPC

- G06F 16/122: {using management policies (point-in-time backing up or restoration of persistent data G06F11/1446; file migration policies for HSM systems G06F16/185)}
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F 16/906: Clustering; Classification
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system partitions files, including segments identified by fingerprints. into clusters. The system counts common fingerprints by counting fingerprints which correspond to both a file cluster and another file cluster. The system counts unique fingerprints by counting fingerprints which correspond to the file cluster and/or the other file cluster. The system uses the common and unique fingerprint counts to approximate the distance between the file cluster and the other file cluster. The system identifies the smallest of distances which are approximated between all file clusters. The system merges the file cluster and the other file cluster into a merged file cluster if the approximated distance is the smallest of distances. The system determines an index corresponding to the smallest and next smallest of distances. The system determines indexes which correspond to merges of all file clusters. The system uses the maximum of indexes to identify the optimal file clustering.

## Claims

### Claim 1

A system for optimized hierarchical clustering of files, comprising:
one or more processors; and
a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to:
partition files, comprising segments identified by fingerprints. into corresponding clusters count common fingerprints by counting fingerprints which correspond to both a cluster of a file and a cluster of another file;
count unique fingerprints by counting fingerprints which correspond to at least one of the cluster of the file and the cluster of the other file;
approximate a distance, based on the count of common fingerprints and the count of unique fingerprints, between the cluster of the file and the cluster of the other file;
identify a smallest of distances which are approximated between all clusters of the files;
merge the cluster of the file and the cluster of the other file into a cluster of the file and the other file, in response to a determination that the approximated distance is the smallest of the distances;
determine an index corresponding to a smallest and a next smallest of the distances;
determine indexes which correspond to merges of all clusters of the files; and
identify, based on a maximum of the indexes, an optimal clustering of the files.

### Claim 2 (depends on 1)

The system of claim 1, wherein each fingerprint is generated as a hash value by applying a hash function to a corresponding segment.

### Claim 3 (depends on 1)

The system of claim 1, wherein the fingerprints which are counted comprise a sampled subset of all fingerprints corresponding to the files.

### Claim 4 (depends on 1)

The system of claim 1, wherein counting common fingerprints and counting unique fingerprints comprise:
generating a hash value by applying a hash function to a fingerprint of a segment in the cluster of the file and an other hash value by applying the hash function to a fingerprint of an other segment in the cluster of the file;
setting a bit corresponding to the hash value and a bit corresponding to the other hash value in an array corresponding to the cluster of the file;
generating an additional hash value by applying the hash function to a fingerprint of a segment in the cluster of the other file and an added hash value by applying the hash function to a fingerprint of an other segment in the cluster of the other file;
setting a bit corresponding to the additional hash value and a bit corresponding to the added hash value in an other array corresponding to the cluster of the other file;
counting total fingerprints by counting bits set in the array and bits set in the other array;
merging the array and the other array into a merged array;
counting the unique fingerprints by counting bits set in the merged array; and
subtracting the count of unique fingerprints from the count of total fingerprint to count the common fingerprints.

### Claim 5 (depends on 1)

The system of claim 1, wherein approximating the distance comprises dividing the count of common fingerprints by the count of unique fingerprints to estimate a similarity, and then subtracting the similarity from a value of one to approximate the distance.

### Claim 6 (depends on 1)

The system of claim 1, wherein determining the index comprises one of dividing the next smallest of distances by the smallest of the distances and subtracting the smallest of distances from the next smallest of the distances.

### Claim 7 (depends on 1)

The system of claim 1, wherein a distance between a cluster of an additional file and the cluster of the file and the other file comprises one of a distance between the cluster of the additional file and the cluster of the file, a distance between the cluster of the additional file and the cluster of the other file, and a distance between the cluster of the additional file and an intermediate of the cluster of the file and the cluster of the other file.

### Claim 8

A computer-implemented method for optimized hierarchical clustering of files, the computer-implemented method comprising:
partitioning files, comprising segments identified by fingerprints. into corresponding clusters
counting common fingerprints by counting fingerprints which correspond to both a cluster of a file and a cluster of another file;
counting unique fingerprints by counting fingerprints which correspond to at least one of the cluster of the file and the cluster of the other file;
approximating a distance, based on the count of common fingerprints and the count of unique fingerprints, between the cluster of the file and the cluster of the other file;
identifying a smallest of distances which are approximated between all clusters of the files;
merging the cluster of the file and the cluster of the other file into a cluster of the file and the other file, in response to a determination that the approximated distance is the smallest of the distances;
determining an index corresponding to a smallest and a next smallest of the distances;
determining indexes which correspond to merges of all clusters of the files; and
identifying, based on a maximum of the indexes, an optimal clustering of the files.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein each fingerprint is generated as a hash value by applying a hash function to a corresponding segment.

### Claim 10 (depends on 8)

The computer-implemented method of claim 8, wherein the fingerprints which are counted comprise a sampled subset of all fingerprints corresponding to the files.

### Claim 11 (depends on 8)

The computer-implemented method of claim 8, wherein counting common fingerprints and counting unique fingerprints comprise:
generating a hash value by applying a hash function to a fingerprint of a segment in the cluster of the file and an other hash value by applying the hash function to a fingerprint of an other segment in the cluster of the file;
setting a bit corresponding to the hash value and a bit corresponding to the other hash value in an array corresponding to the cluster of the file;
generating an additional hash value by applying the hash function to a fingerprint of a segment in the cluster of the other file and an added hash value by applying the hash function to a fingerprint of an other segment in the cluster of the other file;
setting a bit corresponding to the additional hash value and a bit corresponding to the added hash value in an other array corresponding to the cluster of the other file;
counting total fingerprints by counting bits set in the array and bits set in the other array;
merging the array and the other array into a merged array;
counting the unique fingerprints by counting bits set in the merged array; and
subtracting the count of unique fingerprints from the count of total fingerprint to count the common fingerprints.

### Claim 12 (depends on 8)

The computer-implemented method of claim 8, wherein approximating the distance comprises dividing the count of common fingerprints by the count of unique fingerprints to estimate a similarity, and then subtracting the similarity from a value of one to approximate the distance.

### Claim 13 (depends on 8)

The computer-implemented method of claim 8, wherein determining the index comprises one of dividing the next smallest of distances by the smallest of the distances and subtracting the smallest of distances from the next smallest of the distances.

### Claim 14 (depends on 8)

The computer-implemented method of claim 8, wherein a distance between a cluster of an additional file and the cluster of the file and the other file comprises one of a distance between the cluster of the additional file and the cluster of the file, a distance between the cluster of the additional file and the cluster of the other file, and a distance between the cluster of the additional file and an intermediate of the cluster of the file and the cluster of the other file.

### Claim 15

A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein to be executed by one or more processors, the program code including instructions to:
partition files, comprising segments identified by fingerprints. into corresponding clusters;
count common fingerprints by counting fingerprints which correspond to both a cluster of a file and a cluster of another file;
count unique fingerprints by counting fingerprints which correspond to at least one of the cluster of the file and the cluster of the other file;
approximate a distance, based on the count of common fingerprints and the count of unique fingerprints, between the cluster of the file and the cluster of the other file;
identify a smallest of distances which are approximated between all clusters of the files;
merge the cluster of the file and the cluster of the other file into a cluster of the file and the other file, in response to a determination that the approximated distance is the smallest of the distances;
determine an index corresponding to a smallest and a next smallest of the distances;
determine indexes which correspond to merges of all clusters of the files; and
identify, based on a maximum of the indexes, an optimal clustering of the files.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein each fingerprint is generated as a hash value by applying a hash function to a corresponding segment.

### Claim 17 (depends on 15)

The computer program product of claim 15, wherein the fingerprints which are counted comprise a sampled subset of all fingerprints corresponding to the files.

### Claim 18 (depends on 15)

The computer program product of claim 15, wherein counting common fingerprints and counting unique fingerprints comprise:
generating a hash value by applying a hash function to a fingerprint of a segment in the cluster of the file and an other hash value by applying the hash function to a fingerprint of an other segment in the cluster of the file;
setting a bit corresponding to the hash value and a bit corresponding to the other hash value in an array corresponding to the cluster of the file;
generating an additional hash value by applying the hash function to a fingerprint of a segment in the cluster of the other file and an added hash value by applying the hash function to a fingerprint of an other segment in the cluster of the other file;
setting a bit corresponding to the additional hash value and a bit corresponding to the added hash value in an other array corresponding to the cluster of the other file;
counting total fingerprints by counting bits set in the array and bits set in the other array;
merging the array and the other array into a merged array;
counting the unique fingerprints by counting bits set in the merged array; and
subtracting the count of unique fingerprints from the count of total fingerprint to count the common fingerprints.

### Claim 19 (depends on 15)

The computer program product of claim 15, wherein approximating the distance comprises dividing the count of common fingerprints by the count of unique fingerprints to estimate a similarity, and then subtracting the similarity from a value of one to approximate the distance.

### Claim 20 (depends on 15)

The computer program product of claim 15, wherein determining the index comprises one of dividing the next smallest of distances by the smallest of the distances and subtracting the smallest of distances from the next smallest of the distances, and wherein a distance between a cluster of an additional file and the cluster of the file and the other file comprises one of a distance between the cluster of the additional file and the cluster of the file, a distance between the cluster of the additional file and the cluster of the other file, and a distance between the cluster of the additional file and an intermediate of the cluster of the file and the cluster of the other file.
