Domains such as business processes and workflows require working with multi-dimensional ordered objects. There is a need to analyze this data for operational insights. For example, in business processes, users are interested in clustering process traces to discover per-cluster process models that are less complex. Such applications require the ability to measure the similarity between data objects. However, measuring the similarity between sequence-based data is computationally expensive. We present an intuitive and user-controlled approach to summarize sequence-based multi-dimensional data. Our summarization schemes provide a trade-of between the quality and eficiency of analysis tasks. We also derive an error model for summary-based similarity under an edit-distance constraint. Evaluation results over real-world datasets show the efectiveness of our methods.
Loan application received
Verify employment Record loan application
Request credit report
Review credit report
Review loan application sPeearrfcohrm title rReepvoiretw title Timestamp,Responsible,Department,Trace,Resource,Activity,Group 09/22/15 10:16AM,Resource21,General,Trace-11,Resource21,Record loan application,Group 1 09/26/15 08:10AM,Resource21,General,Trace-11,Resource10,Request credit report,Group 4 10/01/15 03:05 PM,Resource21,General,Trace-11,Resource21,Review credit report,Group 1 10/15/15 10:00AM,Resource21,General,Trace-11,Resource15,Verify employment,Group 2 10/20/15 12:30 PM, Resource21,General,Trace-11,Resource15,Review loan application,Group 1 10/31/15 04:30 PM,Resource21,General,Trace-11,Resource21,Send approval,Group 4
Send approval Send rejection among the traces within a cluster. In another example, scientists are interested in querying the provenance of workflow executions to look for executions similar to the one in their query.
Analyzing multi-dimensional sequence data poses a number of challenges. The first is
computational complexity. For example, using edit-distance to capture the similarity between
sequences [
We employ summarization schemes to enable eficient analysis of multi-dimensional data under edit-distance constraints. We focus on analysis tasks that are based on edit-distance because it is a widely used measure for similarity. Sections 2 and 3 introduce the key approach: instead of performing the analysis on the original high-dimensional data, which is computationally expensive, we transform the data into a summary or embedding space that has fewer dimensions, so that the same analysis can be computed more eficiently. Section 4 introduces our topic-summarization schemes to incorporate the multi-dimensional attributes of data items into the analysis and produce summaries that capture the semantics of process traces, while enabling the flexible trade-of between quality and eficiency of analysis tasks on summaries.In Section 5, we develop an error model for the edit-distance measure in the summary space to provide some guarantees for the results of analysis tasks on summaries. Finally, Section 6 shows the efectiveness of our summarization scheme on a number of datasets.
We assume the existence of an original dataset that consists of a set of process traces or logs of workflow executions. Running an analysis, which would typically be computationally expensive Original data … … …
Analysis under editdistance constraint
Generate summaries Summaries of data …
Analysis under editdistance constraint Relate approximate results to the ground-truth
Approximate results due to the high-dimensionality of the data, provides results which are deemed as exact or “ground truth" answer. As shown in Figure 3, our approach is to transform the original data into a new summary space with fewer dimensions, thus avoiding the computationally expensive analysis on original data. The output of any analysis in the summary space is an approximation of the “ground truth". To show the practicality of our proposed approach, we need to address the following challenges: (1) How to generate summaries of data in a controlled and intuitive manner, and (2) Relate the approximate results on summaries to the results on original data?
To address these two challenges, we define sequential-order-preserving summarization and introduce a summarization scheme that is intuitive and give users more control over the resulting summaries. We also present an error model for summary-based similarity measure under editdistance constraint and show that it provides guarantees over the results of clustering and similarity search tasks.
A multidimensional set O is a set of objects O and a set of associated attributes A = (1, 2, ..., |A|): O = ⟨O, A⟩, each object ∈ O is defined as a tuple: = (1(), 2(), ..., |A|()), in which each -th dimension corresponds to the value of attribute of , denoted as ().
A Multidimensional Sequence p of size on a multidimensional set O is defined as an ordered set of objects in O: p = (1, 2, ..., ), ∈ O, 1 ≤ ≤ . We denote p() as the index, or position, of an object in a sequence p. In the above definition, p() = , ∀1 ≤ ≤ .
For example, Figure 2 presents a sequence of objects defined on a multidimensional set with three attributes: Activity, Sector, and Responsible.
Our interest is in diferent forms of summarization of multidimensional sequences to improve eficiency of sequence analysis. Before defining summarization of sequences, we define the notion of many-to-one mapping of objects between multidimensional sets as an object mapping function f from an original multidimensional set O to a summary set S , f : O → S , so that for each ∈ O, ∃! ∈ S : = f ().
Definition 1. A f -summarization of a sequence p on O is defined as a summary sequence s on S , denoted as s = f (p), where each object ∈ p is replaced by its many-to-one mapping f : = f (), while retaining the same index s() := p().
A summarization of a sequence is said to preserve the sequential relationship from the original sequence if it satisfies the following definition: Definition 2. A f -summarization of a sequence p, denoted as s = f (p), is a sequential preserving summarization of p if: ∀, ′ ∈ p, if p() < p(′), then s() ≤ s(′), with = f (), ′ = f (′).
By retaining the indices of objects in the original sequence, f -summarization (c.f, definition 1 ) preserves sequential relationships, which is vital in improving the eficiency of sequence analysis. Therefore, we define the notion of reduced f -summarization, in which adjacent duplicate objects in the summary sequence are collapsed to reduce the size of a summarized sequence. Definition 3. A reduced f -summarization of a sequence p on O is defined as a sequence s on S , denoted as s = f * (p), where each object ∈ p is replaced by its f -based mapping = f () in s and, ∀, +1 ∈ p, 1 ≤ ≤ | p| − 1, if = +1, then s() = p(+1).
Theorem 1. A reduced f -summarization is sequence preserving.
To incorporate the multidimensional attributes of a sequence’s data items, we begin by outlining Attribute-based summarization as an f -summarization2 where f is a mapping on O. This scheme provides an intuitive way for users to choose attributes as a summarization criteria and produces summaries that are easy to interpret. It does not give users control over the average length of summarized sequences, which we refer to as resolution. This is because attribute values are static and already defined with the original data.
Longer summarized sequences are more expensive to analyze, but attribute-based summarization ofers little control in the sequence length. We seek a way for users to trade-of between eficiency and accuracy of data analysis. For example, for similarity search, users might tolerate false positives (e.g., 0.9 false positive rate) for faster response (e.g., results within 5 seconds). We observe that business processes can often be represented by higher-level process models of fewer dimensions. Figure 4 shows an example of a more abstract version of the process model in Figure 1, where each activity corresponds to multiple activities in Figure 1.
We propose a topic-based summarization technique that captures the many-to-one mapping from the original sequences to one with fewer dimensions, where each topic is an abstract representation of a set of original dimensions. Since the topics are implicit from the original sequences, we first perform dimensionality reduction on the original sequences to transform the original dimensions to topics. Then, we define the notion of topic-based summarization using the new representation.
Algorithm 1 highlights the main steps in the topic-based summarization process. Before applying dimension reduction techniques to the original sequences (Line 3), it is important to have an appropriate data representation for sequences (Line 2). We begin by selecting an attribute of the original sequences and transform multidimensional sequences to the appropriate attribute-based summarization. It is often intuitive to pick the attribute with the most number
Algorithm 1 Topic summarization process steps of dimensions as this attribute likely captures the most essential information about the objects in the original multidimensional set. For example, in Figure 2, Activity is the attribute with the most number of dimensions and it is also the base attribute to represent sequences, while other attributes, such as Sector and Responsible, provide supporting information for Activity.
We then represent each sequence p as a numeric vector (1, 2, ..., |* |), where * is the base attribute set that sequences are transformed to in the first step and |* | is the number of dimensions on * . We measure for p in a way that captures both the local importance of each dimension and its specificity to a sequence. To capture the local importance, we use the frequency of the -th dimension in p, denoted as tfp, that is defined by the number of items in p whose values equal the -th dimension of * , denoted as . To capture the specificity, we use the popularity of a dimension across all sequences: df = |{p ∈ S| ∈ p}|, where S is the set of all sequences. Intuitively, the higher df is, the more popular the -th dimension is and thus, the less specificity it is to a sequence. The formulation of is as follows: = {︃(1 + (tfp)) × ( d|Sf| ) if ∈ p 0 otherwise (1)
After representing sequences as vectors, the set of sequences S can be represented as a matrix M, whose size is |S| × | * | where each row corresponds to a vector representation of a sequence in S. With this matrix representation, we can apply of-the-shelf dimension reduction techniques on M, such as non-negative matrix factorization (NMF), principle component analysis (PCA), or singular value decomposition (SVD), among others (Line 3). The results of these techniques can be presented as two matrices M′ and W. M, whose size equals |S| × with being the number of new dimensions (i.e., = |S |), represents the original sequences on the summary space. W, whose size equals |O| × , represents the original dimensions on the new dimensions, or topics (i.e., each row is a vector representing the distribution of an original dimension over the set of new dimensions).
After dimensionality reduction, we produce a many-to-one mapping from the original dimensions to topics (Line 6). Two dimensions , in the original space are likely to be in the same topic if their corresponding vectors in W have high similarity (e.g., using Cosine similarity). In addition, and are likely to be in the same topic if they frequently appear next to each other in a sequence (i.e., they represent two closely related activities in the underlying process model). From these insights, we model the problem of finding an optimal many-to-one mapping from the original dimensions to topics as a constrained optimization problem: argmax f · ∑︁ f ()=f () subject to f : O → S (2) ∀, ∈ O, if f () ̸= f (), then ̸= .
|S | = .
where (, ) is the similarity between dimensions and based on their corresponding representation in W, (, ) is the number of times and are adjacent in input sequence set S, and is used to bias towards similarity between dimensions or the number of adjacent appearances. We now can formally define the notion of topic summarization as follows: Definition 4. (-Topic Summarization) A -topic summarization of sequences from original multidimensional set O to a summary set S is defined as a reduced -summarization, where the mapping f is the solution of the optimization problem defined in (2).
Finding an optimal k-topic summarization is NP-hard (a variant of the set partitioning problem). We take a greedy heuristic approach similar to the agglomerative clustering algorithm (Line 8). It starts by treating each original dimension as a singleton cluster, then merging nearby pairs of dimensions until all clusters have been merged into a single cluster. This step creates a hierarchy where each leaf node is a dimension and the root is the single cluster of the last merge. Because we want a partition of disjoint clusters as the new dimensions, the next step is to cut the hierarchy at some point to obtain the desirable number of clusters. To find the cut (Line 10), we find the minimum similarity threshold so that the distance between any two dimensions in the same cluster is no more than that threshold and there are at most clusters.
We seek to relate the approximate results of analysis tasks on the summary space to those on the original space. Since a similarity measure underlies a lot of analysis tasks, such as similarity search and traces clustering, we focus on the relationship between the similarity of sequences on the summary space with that on the original space under edit-distance constraint: ed(p, q) & ed(f (p), f (q)), where ed is the edit-distance function and f is a summarization function. We select edit-distance as the similarity measure because it captures both the structural similarity (i.e., whether two sequences consist of data items in similar order) and content-based similarity (i.e., whether two sequences share similar set of data items) between sequences. Furthermore, edit-distance’s results, presented as a chain of edit operators to transform a sequence to the other, can be easily interpreted by users, which makes it widely popular in practice.
In terms of the relationship between ed(p, q) and ed(f (p), f (q)), we are interested in the contractive property.
Definition 5. Given a summarization f , we said that the edit-distance measure satisfies the contractive property on f if ed(p, q) ≥ ed(f (p), f (q)), ∀p, q.
The contractive property guarantees that performing edit-distance based similarity search
on the summary space using f will yield results with 100% recall [
While the contractive property does not hold in general for edit-distance between summarized sequences, we show that it holds under certain circumstances. The first of which is when f is a non-reduced many-to-one.
Theorem 2. If f is a non-reduced many-to-one summarization on O, as defined in definition 1, then we have: ed(p, q) ≥ ed(f (p), f (q)), ∀p, q on O.
Theorem 3. Given two sequences p, q in the original space O, if f is a reduced many-to-one summarization on O, as defined in definition 3, then: • If Γ p,q ≥ Λ f (p),f (q), then we have ed(p, q) ≥ ed(f (p), f (q)); or edit-distance on summary space by f satisfies the contractive property. • If Γ f (p),f (q) > Λ p,q, then we have ed(p, q) < ed(f (p), f (q)); or edit-distance on summary space by f does not satisfy the contractive property. where Λ p,q = (|p|, |q|) and Γ p,q = ||p| − | q||, with |p| being the length of p.
While Theorem 3 does not cover all cases, we empirically show that the number of sequence pairs whose edit-distances on reduced many-to-one summarization that violate the contractive property is very small. Thus, it has a high recall for similarity search task.
We evaluate the efectiveness and eficiency of our summarization schemes on two analysis tasks: trace similarity search and traces clustering.
Datasets: We use datasets from multiple domains: the Lithography dataset (596 traces with 1066 types of activities, each having multi-dimensional attributes) is from a real semiconductor manufacturing process, the BPIC 2015 dataset (1199 traces with 289 activity types) is from a building permit application process, and the BANK dataset (2000 traces with 113 activity types) consists of synthetically generated logs from a large bank transaction process. Evaluations were conducted on a 2.7GHz quad-core Intel Core i7 machine with 16GB of RAM 3.
3Results for BPIC experiments are available at [
Topic Random
Summarization schemes: We compare results of analysis tasks using our proposed
summarization schemes (i.e., Topic and Attribute), Random summarization, which randomly maps
an original dimension to a new dimension in the summary space, and with the analysis results
on the original space. Although Random-based summaries lack interpretability, as shown
in [
The contractive property holds for most of the cases, as seen in Figure 5 which shows the percentage of sequence pairs in the Lithography dataset, out of over 177,000 pairs, whose edit-distances violate the contractive property in the summary space using and summarization over diferent number of summary dimensions . Since the recall rate is high, we focus on the false positive rate of the similarity search results.
Evaluation metrics: Given an edit distance threshold , the false positive metric tells us that, out of all sequence pairs that satisfy ed(f (p), f (q)) ≤ on the summary space, how many of them actually satisfy the threshold in the original space: ed(p, q) ≤ .
Efectiveness: Figure 6 shows the efectiveness of the summarization schemes on the similarity search task for the Lithography, and BANK datasets4. The y-axis reports the false positive results, while the x-axis corresponds to diferent edit-distance thresholds. As expected (Figure 6a, 6b, 6d, 6e), the higher the number of dimensions in the summary space (denoted by ), the better the result (i.e., lower false positive rates). That is because, with more dimensions in the summary space, summaries of sequences more resemble the original sequences. Thus, there is little diference between edit-distances on the summary space and in the original space.
Comparing the summarization schemes on the same number of dimensions, Random outperforms Topic (at the cost of interpretability and eficiency, as we will show later). For Attribute (Figure 6c), since we cannot control the number of dimensions (as it depends on the attribute data), the quality of the results also depend on the chosen attribute. Specifically, the 5 attribute outperforms and . This is in part because there are more dimensions on ’s summary space, and thus the summaries on the space more resemble the original sequences. and produce similar results, since similar s are often used in the same .
4We only evaluate Attribute summarization on the Lithography dataset because this dataset’s attributes provide better semantics compared with BANK.
5Three main activity attributes are used on the Lithography data: represents the person in charged of the activity; represents the area/department where the activity is taken, and represents the tool used to perform the activity.
1 0.9 0.8 tae0.7 r ev0.6 i its0.5 o p0.4 e lsa0.3 F 0.2 0.1 0
Eficiency: To evaluate the eficiency of the summarization schemes, we vary the number of dimensions in the summary space and measure the time to calculate the edit-distance between all pairs of sequences. We see in Figure 7, that for both Random and Topic, larger , which leads to longer longer sequences in the summary space, results in longer processing time. For similar values of , Topic outperforms Random, which verifies Topic’s ability to capture the semantic relationship between the original dimensions, and thus significantly reduces the size of sequences in the summary space, as well as the processing time. More importantly, even at diferent values of where we observed similar efectiveness of results by Random and Topic (e.g., = 2 with Random and = 10 with Topic on the Lithography dataset in Figure 6), Topic is still much more eficient than Random.
Evaluation metrics: We evaluate the clustering results using process-specific metrics [
N=3 Original ED Sector
N=4 Number of clusters Topic Tool
N=5 Random
Tracked By
the process model’s conformance fitness quantifies the extent to which the discovered model
can accurately reproduce the recorded traces, the structure complexity quantifies whether the
clustering results produce process models that are simple and compact. Given a summarization
scheme, we first transform all sequences to the summary space, and then perform traces
clustering (using hierarchical clustering) with edit-distance as the similarity measure. Then,
a process model is generated for each cluster using the Heuristic mining algorithm [
Efectiveness of summarization schemes: Figure 8 highlights the conformance fitness of the clustering results in the summary space by diferent summarization schemes 6 on the Lithography dataset. Surprisingly, using summarization schemes not only helps improve the eficiency of the clustering task (as we showed earlier in the eficiency evaluation), but also helps produce clusters with process models of higher fitness, compared with the clustering results in the original space. The trend is similar when varying the number of clusters . That is because measuring trace similarity on the summary space helps remove noise that often exists when measuring similarity using the original representation. Among summarization schemes, Attribute helps produce clustering results of higher conformance fitness (especially when using the attribute). That is because Attribute summarizations capture better the semantic relationship between traces (e.g., traces are similar if the corresponding sequences of , , or are similar).
In terms of the structural complexity (Figure 9), Attribute summarizations outperform other summarization schemes, again due to its ability to capture semantic relationships between traces, producing clusters whose process models capture traces with similar semantics, and thereby having simpler model structures. On the other hand, Random , unable to capture the semantic relationships between traces, is the worst performer.
6We use = 2 for Random, and = 20 for Topic, as these are similarly efective for similarity search.
In both conformance fitness and structural complexity tests, Topic summarization approaches Attribute. Unlike Attribute summarization, which does not give users control over the resolution of the summaries, Topic summarization provides a qualitative advantage in ofering a tunable parameter, , to trade-of between the efectiveness and eficiency in the analysis task.
Subsequence mapping and sequence retrieval is an active area of research. One common approach
is to summarize original sequences using q-grams [
Graph similarity and mining focuses on transforming the original graph – based on graph
substructures e.g. trees [
Embedding methods [
There has been a significant amount of research on various topics related to graph
summarization. We refer the reader to the following surveys [
Eforts to address scalability issues in business process analysis focuses either on process
model discovery of complex traces [
We introduce a method to perform eficient analysis on sequence-based multi-dimensional data using intuitive and user-controlled summarizations. We define a topic summarization scheme that ofer flexible trade-of between quality and eficiency of analysis tasks and derive an error model for summary-based similarity under an edit-distance constraint. The approach was found to be both efective and eficient based on evaluations on real-world process datasets.