  Process mining is a discipline which concerns the analysis of execution data
of operational processes, the extraction of models from event data, the
measurement of the conformance between event data and normative models, and the
enhancement of all aspects of processes. Most approaches assume that event data
is accurately capture behavior. However, this is not realistic in many
applications: data can contain uncertainty, generated from errors in recording,
imprecise measurements, and other factors. Recently, new methods have been
developed to analyze event data containing uncertainty; these techniques
prominently rely on representing uncertain event data by means of graph-based
models explicitly capturing uncertainty. In this paper, we introduce a new
approach to efficiently calculate a graph representation of the behavior
contained in an uncertain process trace. We present our novel algorithm, prove
its asymptotic time complexity, and show experimental results that highlight
order-of-magnitude performance improvements for the behavior graph
construction.
