{"id":131,"date":"2020-02-14T12:00:57","date_gmt":"2020-02-14T11:00:57","guid":{"rendered":"https:\/\/blog.rwth-aachen.de\/pads\/?p=131"},"modified":"2020-02-19T11:30:35","modified_gmt":"2020-02-19T10:30:35","slug":"efficient-construction-of-behavior-graphs-for-uncertain-event-data","status":"publish","type":"post","link":"https:\/\/blog.rwth-aachen.de\/pads\/2020\/02\/14\/efficient-construction-of-behavior-graphs-for-uncertain-event-data\/","title":{"rendered":"Efficient Construction of Behavior Graphs for Uncertain Event Data"},"content":{"rendered":"\n

This post is by Marco Pegoraro<\/a>, Scientific Assistant in the Process And Data Science group at RWTH Aachen University. Contact him via email for further inquiries.<\/em><\/p>\n\n\n\n

In previous posts on this blog, we talked about uncertainty in process mining, both in the context of conformance checking and process discovery. In an uncertain process trace<\/em>, the attributes of an event are not recorded as a precise value but as a range or a set of alternatives.<\/p>\n\n\n\n

\"\"
An uncertain trace with uncertainty on timestamps. Some timestamp ranges overlap, e.g. events 3 and 4.<\/figcaption><\/figure><\/div>\n\n\n\n

If we consider the case of timestamps represented as ranges, the total order usually present among events in a trace is lost; time relationships exist in a partial order<\/em> instead, where the order between events that have overlapping timestamps is undefined. The directed acyclic graph that graphically represents this partial order is called a behavior graph.<\/em><\/p>\n\n\n\n

\"\"
Left: a time diagram representing the timestamps of the events in the trace. Right: the behavior graph of the example trace. Notice that events having overlapping timestamps are not connected by a path (their order in time is undefined).<\/figcaption><\/figure><\/div>\n\n\n\n

A straightforward way to obtain a behavior graph is to check all pairs of events, connecting the ones that have a well-defined time relationship, then perform a transitive reduction to remove unnecessary edges. This runs in a cubic time with respect to the number of events. In the paper “Efficient Construction of Behavior Graphs for Uncertain Event Data<\/em>” (Pegoraro, Uysal, van der Aalst) we present a method to build behavior graphs in quadratic time, leading to a more efficient analysis of uncertain data in process mining.
<\/p>\n","protected":false},"excerpt":{"rendered":"

This post is by Marco Pegoraro, Scientific Assistant in the Process And Data Science group at RWTH Aachen University. Contact him via email for further inquiries. In previous posts on […]<\/p>\n","protected":false},"author":1679,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"c2c_always_allow_admin_comments":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-131","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/131","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/users\/1679"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/comments?post=131"}],"version-history":[{"count":1,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/131\/revisions"}],"predecessor-version":[{"id":135,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/131\/revisions\/135"}],"wp:attachment":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/media?parent=131"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/categories?post=131"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/tags?post=131"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}