Similarity clustering in linear time with error-free retrieval using signature overlap with signature size matching

A system for determining whether to assign a data item to at least one cluster of data items, comprising:

• a memory;
• and
• a processing device, coupled to the memory, to:
• identify a signature of the data item, the identified signature including a set of elements;
• derive a first size value, the first size value being the number of elements of the identified signature based on a set of size values of signatures that includes a maximum size value;
• derive a second size value based on the set of size values of signatures;
• select a subset of the set of elements of the identified signature to form at least one partial signature of the identified signature wherein the number of elements in the at least one partial signature represents the number of elements in common between the identified signature having the first size value and a second signature having the second size value and being similar to the identified signature, wherein the second signature is of an anticipated second data item;
• combine the selected subset of elements into at least one token;
• determine whether the at least one token is present in a memory, the memory configured to contain an existing set of tokens;
• determine whether to assign the data item to at least one cluster based on whether the at least one token is present in the memory;
• and
• perform said deriving a first size value, said deriving a second size value, said selecting, said combining, said determining whether the at least one token is present in a memory, and said determining whether to assign the data item to at least one cluster, with one or more minimum similarity threshold values, to obtain one or more clusterings.

A non-transitory computer readable storage medium including instructions that, when executed by a processing device, cause the processing device to determine whether to assign a data item to at least one cluster of data items, the processing device further to:

• identify a signature of the data item, the identified signature including a set of elements;
• derive a first size value, the first size value being the number of elements of the identified signature based on a set of size values of signatures that includes a maximum size value;
• derive a second size value based on the set of size values of signatures;
• select a subset of the set of elements of the identified signature to form at least one partial signature of the identified signature wherein the number of elements in the at least one partial signature represents the number of elements in common between the identified signature having the first size value and a second signature having the second size value and being similar to the identified signature wherein the second signature is of an anticipated second data item;
• combine the selected subset of elements into at least one token;
• determine whether the at least one token is present in a memory, the memory configured to contain an existing set of tokens;
• determine whether to assign the data item to at least one cluster based on whether the at least one token is present in the memory;
• and
• perform said deriving a first size value, said deriving a second size value, said selecting, said combining, said determining whether the at least one token is present in a memory, and said determining whether to assign the data item to at least one cluster, with one or more minimum similarity threshold values, to obtain one or more clusterings.