Aligning modeled and observed behavior: a compromise between computation complexity and quality

B.F. Van Dongen, J. Carmona, T. Chatain, F. Taymouri

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

Abstract

Certifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can be made easier on models instead of on plain data. In spite of its importance, the current algorithmic support for computing alignments is limited: either techniques that explicitly explore the model behavior (which may be worst-case exponential with respect to the model size), or heuristic approaches that cannot guarantee a solution, are the only alternatives. In this paper we propose a solution that sits right in the middle in the complexity spectrum of alignment techniques; it can always guarantee a solution, whose quality depends on the exploration depth used and local decisions taken at each step. We use linear algebraic techniques in combination with an iterative search which focuses on progressing towards a solution. The experiments show a clear reduction in the time required for reaching a solution, without sacrificing significantly the quality of the alignment obtained.

Original languageEnglish
Title of host publicationAdvanced Information Systems Engineering
Subtitle of host publication29th International Conference, CAiSE 2017, Essen, Germany, June 12-16, 2017, Proceedings
EditorsE. Dubois, K. Pohl
Place of PublicationDordrecht
PublisherSpringer
Pages94-109
Number of pages16
ISBN (Electronic)978-3-319-59536-8
ISBN (Print)978-3-319-59535-1
DOIs
Publication statusPublished - 2017
EventForum and Doctoral Consortium Papers Presented at the 29th International Conference on Advanced Information Systems Engineering, CAiSE-Forum-DC 2017 - Essen, Germany
Duration: 12 Jun 201716 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10253 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceForum and Doctoral Consortium Papers Presented at the 29th International Conference on Advanced Information Systems Engineering, CAiSE-Forum-DC 2017
CountryGermany
CityEssen
Period12/06/1716/06/17

Fingerprint

Process Model
Alignment
Model
Heuristics
Computing
Alternatives
Experiment
Experiments

Keywords

  • Alignments
  • Conformance checking
  • Heuristics
  • ILP
  • Process mining

Cite this

Van Dongen, B. F., Carmona, J., Chatain, T., & Taymouri, F. (2017). Aligning modeled and observed behavior: a compromise between computation complexity and quality. In E. Dubois, & K. Pohl (Eds.), Advanced Information Systems Engineering: 29th International Conference, CAiSE 2017, Essen, Germany, June 12-16, 2017, Proceedings (pp. 94-109). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10253 LNCS). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-59536-8_7
Van Dongen, B.F. ; Carmona, J. ; Chatain, T. ; Taymouri, F. / Aligning modeled and observed behavior : a compromise between computation complexity and quality. Advanced Information Systems Engineering: 29th International Conference, CAiSE 2017, Essen, Germany, June 12-16, 2017, Proceedings. editor / E. Dubois ; K. Pohl. Dordrecht : Springer, 2017. pp. 94-109 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{4e47f4a20e82478d97475396b90531ba,
title = "Aligning modeled and observed behavior: a compromise between computation complexity and quality",
abstract = "Certifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can be made easier on models instead of on plain data. In spite of its importance, the current algorithmic support for computing alignments is limited: either techniques that explicitly explore the model behavior (which may be worst-case exponential with respect to the model size), or heuristic approaches that cannot guarantee a solution, are the only alternatives. In this paper we propose a solution that sits right in the middle in the complexity spectrum of alignment techniques; it can always guarantee a solution, whose quality depends on the exploration depth used and local decisions taken at each step. We use linear algebraic techniques in combination with an iterative search which focuses on progressing towards a solution. The experiments show a clear reduction in the time required for reaching a solution, without sacrificing significantly the quality of the alignment obtained.",
keywords = "Alignments, Conformance checking, Heuristics, ILP, Process mining",
author = "{Van Dongen}, B.F. and J. Carmona and T. Chatain and F. Taymouri",
year = "2017",
doi = "10.1007/978-3-319-59536-8_7",
language = "English",
isbn = "978-3-319-59535-1",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "94--109",
editor = "E. Dubois and K. Pohl",
booktitle = "Advanced Information Systems Engineering",
address = "Germany",

}

Van Dongen, BF, Carmona, J, Chatain, T & Taymouri, F 2017, Aligning modeled and observed behavior: a compromise between computation complexity and quality. in E Dubois & K Pohl (eds), Advanced Information Systems Engineering: 29th International Conference, CAiSE 2017, Essen, Germany, June 12-16, 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10253 LNCS, Springer, Dordrecht, pp. 94-109, Forum and Doctoral Consortium Papers Presented at the 29th International Conference on Advanced Information Systems Engineering, CAiSE-Forum-DC 2017, Essen, Germany, 12/06/17. https://doi.org/10.1007/978-3-319-59536-8_7

Aligning modeled and observed behavior : a compromise between computation complexity and quality. / Van Dongen, B.F.; Carmona, J.; Chatain, T.; Taymouri, F.

Advanced Information Systems Engineering: 29th International Conference, CAiSE 2017, Essen, Germany, June 12-16, 2017, Proceedings. ed. / E. Dubois; K. Pohl. Dordrecht : Springer, 2017. p. 94-109 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10253 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Aligning modeled and observed behavior

T2 - a compromise between computation complexity and quality

AU - Van Dongen, B.F.

AU - Carmona, J.

AU - Chatain, T.

AU - Taymouri, F.

PY - 2017

Y1 - 2017

N2 - Certifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can be made easier on models instead of on plain data. In spite of its importance, the current algorithmic support for computing alignments is limited: either techniques that explicitly explore the model behavior (which may be worst-case exponential with respect to the model size), or heuristic approaches that cannot guarantee a solution, are the only alternatives. In this paper we propose a solution that sits right in the middle in the complexity spectrum of alignment techniques; it can always guarantee a solution, whose quality depends on the exploration depth used and local decisions taken at each step. We use linear algebraic techniques in combination with an iterative search which focuses on progressing towards a solution. The experiments show a clear reduction in the time required for reaching a solution, without sacrificing significantly the quality of the alignment obtained.

AB - Certifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can be made easier on models instead of on plain data. In spite of its importance, the current algorithmic support for computing alignments is limited: either techniques that explicitly explore the model behavior (which may be worst-case exponential with respect to the model size), or heuristic approaches that cannot guarantee a solution, are the only alternatives. In this paper we propose a solution that sits right in the middle in the complexity spectrum of alignment techniques; it can always guarantee a solution, whose quality depends on the exploration depth used and local decisions taken at each step. We use linear algebraic techniques in combination with an iterative search which focuses on progressing towards a solution. The experiments show a clear reduction in the time required for reaching a solution, without sacrificing significantly the quality of the alignment obtained.

KW - Alignments

KW - Conformance checking

KW - Heuristics

KW - ILP

KW - Process mining

UR - http://www.scopus.com/inward/record.url?scp=85021221283&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59536-8_7

DO - 10.1007/978-3-319-59536-8_7

M3 - Conference contribution

AN - SCOPUS:85021221283

SN - 978-3-319-59535-1

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 94

EP - 109

BT - Advanced Information Systems Engineering

A2 - Dubois, E.

A2 - Pohl, K.

PB - Springer

CY - Dordrecht

ER -

Van Dongen BF, Carmona J, Chatain T, Taymouri F. Aligning modeled and observed behavior: a compromise between computation complexity and quality. In Dubois E, Pohl K, editors, Advanced Information Systems Engineering: 29th International Conference, CAiSE 2017, Essen, Germany, June 12-16, 2017, Proceedings. Dordrecht: Springer. 2017. p. 94-109. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-59536-8_7