US 12,517,910 B2Granted

Method for stable set similarity joins

AssigneeCelonis SE

InventorsDaniel Schmitt, Nikolaus Augsten, Daniel Kocher, Willi Mann, Alexander Miller

Life of this patent

Estimating the term…

Loading patent…

Abstract

Provided is a method for the set similarity join, wherein each set represents a process and each token represents a process step. The process comprises a series of process steps executed in at least one source computer system. Hence, similar sets represent similar processes within a collection of processes. The method is based on a two-level signature scheme. Having indexed the sets using a first signature into inverted lists, selected lists, in particular long lists, are reindexed using a second signature. As a result, the number of candidates and thus the number of required distance calculations can be effectively reduced. Its experimental evaluation has shown that the method consistently outperforms state-of-the-art algorithms on datasets with diverging characteristics, suggesting a stable solution for a wide range of applications.

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

wherein each set (R) 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 the method comprises the following steps:
a) determining, by at least one computer processor, a first signature for each set (R),
b) indexing, by at least one computer processor, each set (R) based on the determined first signature, wherein each indexed set (I) is stored, by at least one computer processor, in at least one first record, wherein each of the at least one first record is recorded, by at least one computer processor, in a first data structure representing a first index and corresponds to the determined first signature,
c) selecting, by at least one computer processor, a subset of the first data structure based on a predefined cost function,
d) for each first record of the selected subset of the first data structure, determining, by at least one computer processor, a second signature for each indexed set (I),
e) reindexing, by at least one computer processor, the indexed set (I) based on the determined second signature, wherein each reindexed indexed set (I2) is stored, by at least one computer processor, in at least one second record, wherein each of the at least one second record is recorded, by at least one computer processor, in a second data structure representing at least one second index and corresponds to the determined second signature,
f) generating, by at least one computer processor, a hybrid index from the complement of the selected subset of the first index and the at least one second index, and
g) probing, by at least one computer processor, at least a subset of the hybrid index by computing, by at least one computer processor, a distance value between each set (I;
I2) of each record of the subset and the selected query set (Q), wherein a probed set (C) 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.

8 more elements

Abstract

Claims14