论文《高效恢复缺失的事件》翻译

Efficient Recovery of Missing Events

有效恢复缺失的事件

Abstract—For various entering and transmission issues raised by human or system,

missing events often occur in event data, which record execution logs of business

processes. Without recovering the missing events, applications such as provenance

analysis or complex event processing built upon event data are not reliable. Following

the minimum change discipline in improving data quality, it is also rational to find a

recovery that minimally differs from the original data. Existing recovery approaches

fall short of efficiency owing to enumerating and searching over all of the possible

performance.

Index Terms—Data repairing, event data processing, petri net

摘要：对于人工或系统提出的各种输入和传输问题，事件数据中经常会出现丢失

事件，这些事件数据记录了业务流程的执行日志。如果不恢复丢失的事件，诸如

起源分析或基于事件数据的复杂事件处理等应用程序就不可靠。遵循改善数据质

量的最小变化原则，找到与原始数据最小差异的恢复也是合理的。由于枚举和搜

索所有可能的事件序列，现有的恢复方法缺乏效率。在这篇论文中，我们研究了

恢复丢失事件的有效技术。根据我们的理论结果，恢复问题似乎是 np 困难的。

然而，先进的索引剪枝技术进一步提高了恢复效率。实验结果表明，我们的最小

恢复方法具有较高的精度，在时间性能上显著优于最先进的技术，提高了 5 个数

recent Web services and online transactions [17]. In event data management,

complex event processing [5] detects interesting event patterns from data. While

querying and mining on event data are widely investigated, the quality of event data

itself draws less attention.

According to our survey of real event data recorded by a train manufacturer, at

least 47.66 percent events are missed in a total of 4, 470 event sequences. The missing

events occur for various reasons, such as (1) forgot to submit when manually recording

event logs, (2) suffered from system failures, or (3) mess after collecting the events

from heterogeneous execution environment. In this survey, the most typical missing

events are routing events (41.43 percent of the 47.66 percent missing events), which

pass or distribute tasks (e.g., by the manager) to one or multiple staffs for subsequent

Moreover, mining patterns over event data is important, since event patterns (with

distinct appearance frequencies) can be utilized as discriminative features in matching

and identifying heterogeneous events [28]. The basic idea is to enrich the features of

singleton events (less discriminative) by more complex event patterns (more

discriminative) in event matching (see more details in [27], [28]). As presented in [15],

interesting event patterns (a.k.a. episodes) that occur frequently could be discovered

from event sequences. For instance, a pattern

could no longer be discovered.

without any prior knowledge. Fortunately, most business events do not occur randomly.

specifications [5]. We focus on recovering missing events in the light of process

specifications.

Example 1. Consider a real process specification in Fig. 1a for producing an

engineering drawing in a train manufacturer. Each square (namely transition) denotes

a task in the process specification, e.g., transition

the arrows attached to a transition denote that the corresponding flows should be

executed in parallel. For example, both the dimension checking (task C) and the

tolerance checking (task

) should be conducted after line type proofing (task B) in

An execution of the process generates a sequence of events, where each event

corresponds to a task in the process specification. We say that a sequence conforms to

place bend following the flow constraints in the specification. For example, the first

sequence <ABCDEG> in Fig. 1b denotes a complete execution of engineering drawing

including steps drafting, line type proofing, dimension checking, tolerance checking,

evaluating, archiving from bstart to bend.

Owing to various data quality issues, event logs are often incomplete. For instance,

the second sequence <ABCEG> has an event D missed during the collection of event

logs from the database for dimension checking. Without recovering the missing event

D, it is unlikely to find the provenance step of E. Moreover, if such data transmission

problems occur frequently in the dimension checking database, an incorrect event

pattern without dimension checking step in engineering drawing will be mined.

following the intuition that systems or human always try to minimize their mistakes in

third sequence <ABCDG> in Fig. 1 in Example 1, a minimum recovery <ABCDEG>

could be more likely referring to the aforesaid intuition of minimum (missing) mistakes,

rather than <ABCDEFBCDEG>, <ABCDEFBCDEFBCDEG>, ... Indeed, as discussed

in Example 4, the chance that all events in a loop (e.g., FBCDE in the aforesaid recovery)

are missing is low in practice. Consequently, the accuracy of the former minimum

bend [23]. Each ei corresponds to an agent of processing some job, which can either

skip a job (denoted by si) or accept it (by ai and execute ei). Suppose that a sequence

<c1c2c3b1> is given. Simply filling the prerequisites of observed events from the

process specification, e.g., <s1s2s3s4> for b1, may not be able to form a valid recovery.

On the other hand, a large number of possible recoveries for the sequence could be

enumerated, e.g., <a1e1a2c1c2e2c3s3s4b1>, <a1e1a2c1

c2e2s3s4c3b1>; ... ;<s1a2e2s3s4c1c2c3b1>; .. . Efficiently finding the optimal

recovery (with the minimum change) is highly non-trivial.

Efficiently computing the recovery of missing events is essential and challenging

with the following considerations: (1) The number of transitions could be as large as

118 in real process/workflow specifications [7], and 1,000 in event sequences according

to our observation in Section 6. The number of possible paths (even w.r.t. specifications

without loops) is exponential to the number of transitions [6], [16], and thus may hardly

loops exist in process specifications. (2) Real-time business process monitoring [10],

recovering the missing events in an online manner. It further motivates us to develop

more efficient pruning and heuristics for missing event recovery.

We propose a linear time backtracking algorithm for the recovery of a simple case,

where all the events are in parallel execution without any choices.

index with advanced pruning techniques are developed to speed-up recovery.

We devise efficient heuristic that performs directly on process specifications

without generating branching index. By precomputing possible executions (paths),

recovery efficiency is significantly improved. Several typical cases are studied, on

which the heuristic shows the best performance.

Finally, we report the extensive experimental evaluation on real data.

1 引言

业务流程持续生成大量的事件数据，从传统的企业办公自动化系统或科学的

工作流程[2]、[8]到最近的 Web 服务和在线交易[17]。在事件数据管理中，起源

分析[20]标识出通向数据项的步骤序列，而复杂事件处理[5]从数据中检测出有趣

的事件模式。虽然对事件数据的查询和挖掘得到了广泛的研究，但对事件数据本

身的质量关注较少。

根据我们对一家火车制造商记录的真实事件数据的调查，在总共 4470 个事