Similarity analysis using enhanced MinHash

A system, comprising:

• one or more processors and a memory storing instructions that upon execution on or across the one or more processors implement a similarity analysis task configured to:
• obtain a plurality of sets individually representing one or more data entities, wherein individual sets of the plurality of sets respectively comprise:
• a contributor count array comprising respective counts of child sets;
• and
• a minimum hash information array generated without applying a hash function;
• generate a derived set from the plurality of obtained sets, wherein to generate the derived set the similarity analysis task is configured to:
• identify, from the plurality of sets, a first set and a second set according to respective similarity scores for the first and second sets, the respective similarity scores determined according to the respective minimum hash information arrays and the respective contributor count arrays of the first and second sets without applying a hash function to the first and second sets;
• apply a set operation to the identified first and second sets to determine the derived set;
• generate a minimum hash information array for the derived set without applying a hash function, the generating performed according to the respective minimum hash information arrays of the first and second sets and the respective contributor count arrays of the first and second sets;
• and
• generate a contributor count array for the derived set, wherein an entry at a particular index in the generated contributor count array is indicative of a count of child sets of the derived set whose minimum hash information array meets a criterion with respect to an entry at the particular index in the minimum hash information array for the derived set.

One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors cause one or more computer systems to implement:

• obtaining a plurality of sets individually representing one or more data entities, wherein individual sets of the plurality of sets respectively comprise;
• a contributor count array comprising respective counts of child sets;
• and
• a minimum hash information array generated without applying a hash function;
• generating a derived set from the plurality of obtained sets, wherein the generating comprises:
• identifying, from the plurality of sets, a first set and a second set according to respective similarity scores for the first and second sets, the respective similarity scores determined according to the respective minimum hash information arrays and the respective contributor count arrays of the first and second sets without applying a hash function to the first and second sets;
• applying a set operation to the identified first and second sets to determine the derived set;
• generating a minimum hash information array for the derived set without applying a hash function, the generating performed according to the respective minimum hash information arrays of the first and second sets and the respective contributor count arrays of the first and second sets;
• and
• generating a contributor count array for the derived set, wherein an entry at a particular index in the generated contributor count array is indicative of a count of child sets of the derived set whose minimum hash information array meets a criterion with respect to an entry at the particular index in the minimum hash information array for the derived set.