# US 12,222,815 B2 · Efficient dictionary data structure to find similar backup clients > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,815 B2 - Document ID: US12222815B2 - Status: Granted - Kind: B2 - Application number: 17/125,536 - Filed: 2020-12-17 - Published: 2022-06-23 - Granted: 2025-02-11 - Earliest claimed: 2020-12-17 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Smriti Thakkar; Tony T. Wong; Abhinav Duggal - Web page: https://patentgrep.com/patent/US12222815B2 ## CPC - G06F 11/1453: {using de-duplication of the data} - G06F 11/1435: {using file system or storage system metadata} - G06F 11/1464: {for networked environments} - G06F 16/174: Redundancy elimination performed by the file system (error detection or correction of the data by redundancy in operations G06F11/14) - G06F 18/2113: by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation - G06F 18/22: Matching criteria, e.g. proximity measures - G06F 18/23: Clustering techniques - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract One example method includes generating a fingerprint:tag dictionary that includes a group of fingerprints and a group of tags, and the fingerprint:tag dictionary identifies, for each fingerprint, the tag or tags which include that fingerprint, computing a similarity matrix based on the fingerprint:tag dictionary, and the similarity matrix identifies, for each pair of tags in the fingerprint:tag dictionary, a relative similarity of the tags in the pair to each other, running a clustering algorithm to identify groups of similar tags in the similarity matrix, and deduplicating, based on the groups of similar tags, respective data associated with the fingerprints. ## Claims ### Claim 1 A method, comprising: generating a fingerprint: tag dictionary that comprises a plurality of pairs, wherein each pair includes a fingerprint and a list of tags, which include the fingerprint, wherein each tag is assigned to one or more fingerprints; computing one or more similarity matrixes based on every pair of two tags in the fingerprint:tag dictionary, wherein each similarity matrix identifies a relative similarity between a first list of fingerprints assigned to one of the two tags and a second list of fingerprints assigned to the other one of the two tags; running a clustering algorithm to identify groups of similar tags based on the one or more similarity matrixes; and deduplicating, based on the groups of similar tags, respective data associated with the fingerprints, wherein at least one of the tags includes 10,000 fingerprints, which are generated by a hashing process. ### Claim 2 (depends on 1) The method as recited in claim 1, wherein the similarity of tags in a pair comprises a Jaccard similarity measure. ### Claim 3 (depends on 1) The method as recited in claim 1, wherein all of the similarities are determined with a single scan of the fingerprint: tag dictionary. ### Claim 4 (depends on 1) The method as recited in claim 1, wherein computing the one or more similarity matrixes is more efficient, in terms of computational complexity, IO load, and memory usage, than calculating the similarity matrix using a brute force approach or a bloom filter approach. ### Claim 5 (depends on 1) The method as recited in claim 1, wherein the deduplication is performed at a data storage node of a cluster. ### Claim 6 (depends on 1) The method as recited in claim 1, wherein computing the one or more similarity matrixes comprises computing a similarity, pairwise, among tags in each pair in the fingerprint:tag dictionary. ### Claim 7 (depends on 1) The method as recited in claim 1, wherein the fingerprints and tags in the fingerprint:tag dictionary are arranged in a plurality of entries, and each entry comprises a respective fingerprint and all the tags which include the respective fingerprint, and computing the one or more similarity matrixes comprises reading a list of tags sequentially for a fingerprint in each pair and, for each pair, determining the similarity of all the tags in each pair. ### Claim 8 (depends on 1) The method as recited in claim 1, wherein each tag comprises one or more respective files. ### Claim 9 (depends on 1) The method as recited in claim 1, further comprising determining a size of one or more of the tags. ### Claim 10 (depends on 1) The method as recited in claim 1, further comprising determining an intersection between one or more tags in each pair. ### Claim 11 A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising: generating a fingerprint: tag dictionary that comprises a plurality of pairs, wherein each pair includes a fingerprint and a list of tags, which include the fingerprint, wherein each tag is assigned to one or more fingerprints; computing one or more similarity matrixes based on every pair of two tags the fingerprint:tag dictionary, wherein each similarity matrix identifies a relative similarity between a first list of fingerprints assigned to one of the two tags and a second list of fingerprints assigned to the other one of the two tags; running a clustering algorithm to identify groups of similar tags based on the one or more similarity matrixes; and deduplicating, based on the groups of similar tags, respective data associated with the fingerprints, wherein at least one of the tags includes 10,000 fingerprints, which are generated by a hashing process. ### Claim 12 (depends on 11) The non-transitory storage medium as recited in claim 11, wherein the similarity of tags in a pair comprises a Jaccard similarity measure. ### Claim 13 (depends on 11) The non-transitory storage medium as recited in claim 11, wherein all of the similarities are determined with a single scan of the fingerprint: tag dictionary. ### Claim 14 (depends on 11) The non-transitory storage medium as recited in claim 11, wherein computing the one or more similarity matrixes is more efficient, in terms of computational complexity, IO load, and memory usage, than calculating the similarity matrix using a brute force approach or a bloom filter approach. ### Claim 15 (depends on 11) The non-transitory storage medium as recited in claim 11, wherein the deduplication is performed at a data storage node of a cluster. ### Claim 16 (depends on 11) The non-transitory storage medium as recited in claim 11, wherein computing the one or more similarity matrixes comprises computing a similarity, pairwise, among tags in each pair in the fingerprint: tag dictionary. ### Claim 17 (depends on 11) The non-transitory storage medium as recited in claim 11, wherein the fingerprints and tags in the fingerprint: tag dictionary are arranged in a plurality of entries, and each entry comprises a respective fingerprint and all the tags which include the respective fingerprint, and computing the one or more similarity matrixes comprises reading a plurality of tags sequentially for a fingerprint in each pair and, for each pair, determining the similarity of all the tags in each pair. ### Claim 18 (depends on 11) The non-transitory storage medium as recited in claim 11, wherein each tag comprises one or more respective files. ### Claim 19 (depends on 11) The non-transitory storage medium as recited in claim 11, further comprising determining a size of one or more of the tags. ### Claim 20 (depends on 11) The non-transitory storage medium as recited in claim 11, further comprising determining an intersection between tags in each pair.