Efficient dictionary data structure to find similar backup clients
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.
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.
2. The method as recited in claim 1 , wherein the similarity of tags in a pair comprises a Jaccard similarity measure.
3. The method as recited in claim 1 , wherein all of the similarities are determined with a single scan of the fingerprint: tag dictionary.
4. 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.
5. The method as recited in claim 1 , wherein the deduplication is performed at a data storage node of a cluster.
6. 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.
7. 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.
8. The method as recited in claim 1 , wherein each tag comprises one or more respective files.
9. The method as recited in claim 1 , further comprising determining a size of one or more of the tags.
10. The method as recited in claim 1 , further comprising determining an intersection between one or more tags in each pair.
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.
12. The non-transitory storage medium as recited in claim 11 , wherein the similarity of tags in a pair comprises a Jaccard similarity measure.
13. 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.
14. 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.
15. The non-transitory storage medium as recited in claim 11 , wherein the deduplication is performed at a data storage node of a cluster.
16. 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.
17. 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.
18. The non-transitory storage medium as recited in claim 11 , wherein each tag comprises one or more respective files.
19. The non-transitory storage medium as recited in claim 11 , further comprising determining a size of one or more of the tags.
20. The non-transitory storage medium as recited in claim 11 , further comprising determining an intersection between tags in each pair.