Method for large-scale set similarity joins

A computer-implemented method of finding at least one similar set to a selected query set within a collection of sets, wherein each set comprises a number of tokens,

• wherein each set represents a process and each token represents a process step, wherein the process comprises a series of process steps executed in at least one source computer system,
• wherein each set is transformed, by at least one computer processor, to a representation in a vector space, wherein the representation is stored, by at least one computer processor, within a storage device,
• wherein each set comprises a prefix, wherein the prefix comprises at least one token of the corresponding set up to a predefined number of tokens,
• wherein a data structure is created and stored, by at least one computer processor, within the storage device, wherein the data structure comprises multiple unique elements, wherein each unique element represents a token comprised in the collection of sets, wherein each set of at least a subset of the collection of sets is linked to at least one unique element of the data structure representing the at least one token of its prefix, wherein the linked sets are grouped by their number of tokens into at least one group for the corresponding unique element,
• wherein similar sets to the selected query set are identified, by at least one computer processor, according to the following steps:
• in a probing step, for each group of the data structure a spatial index is constructed, by at least one processor, from the linked sets, wherein each linked set is exclusively inserted into a collection of potentially similar sets if its representation in the vector space is located within a predefined subspace of the vector space, wherein the collection of potentially similar sets for each group is stored, by at least one computer processor, in the storage device, such that the collection of potentially similar sets comprises a subset of the linked sets of each group,
• in a candidate verifying step, for each potentially similar set of the spatial index a distance value to the selected query set is computed, by at least one computer processor, using a predefined distance function, wherein a potentially similar set is identified, by at least one computer processor, as one of the at least one similar set if the distance value is smaller or equal to a predefined threshold value,
• wherein:
• the at least one similar set represents at least one similar process to a selected process within a collection of processes,
• the predefined number of tokens in the prefix is computed, by at least one processor, based on the predefined distance function and the threshold value,
• the data structure and the collection of potentially similar sets are stored in a volatile memory of the storage device, in particular the main memory,
• the spatial index is only constructed for groups comprising at least a predefined number of linked sets, wherein for each group comprising less than the predefined number of linked sets the linked sets are sorted according to a random dimension of their representations, and
• for the selected query set an upper bound and a lower bound is computed by at least one computer processor, wherein each set comprising more tokens than the upper bound of the selected query set or less tokens than the lower bound of the selected query set is skipped.