# Conformance Checking Approximation using Subset Selection and Edit Distance

arXiv: https://arxiv.org/abs/1912.05022 · HTML: https://mlsanity.com/paper/1912.05022/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2019.

## Built on by (most cited first, 7 of 7)

- [Performance-Preserving Event Log Sampling for Predictive Monitoring](https://mlsanity.com/paper/2301.07624/) (2023)
- [LLM-based event abstraction and integration for IoT-sourced logs](https://mlsanity.com/paper/2409.03478/) (2024)
- [Event Log Sampling for Predictive Monitoring](https://mlsanity.com/paper/2204.01470/) (2022)
- [DeclareAligner: A Leap Towards Efficient Optimal Alignments for Declarative Process Model Conformance Checking](https://mlsanity.com/paper/2503.10479/) (2025)
- [A Scalable and Near-Optimal Conformance Checking Approach for Long Traces](https://mlsanity.com/paper/2406.05439/) (2024)
- [Conformance Checking for Less: Efficient Conformance Checking for Long Event Sequences](https://mlsanity.com/paper/2505.21506/) (2025)
- [Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*](https://mlsanity.com/paper/2605.26938/) (2026)

## Abstract (arXiv)

Conformance checking techniques let us find out to what degree a process model and real execution data correspond to each other. In recent years, alignments have proven extremely useful in calculating conformance statistics. Most techniques to compute alignments provide an exact solution. However, in many applications, it is enough to have an approximation of the conformance value. Specifically, for large event data, the computing time for alignments is considerably long using current techniques which makes them inapplicable in reality. Also, it is no longer feasible to use standard hardware for complex processes. Hence, we need techniques that enable us to obtain fast, and at the same time, accurate approximation of the conformance values. This paper proposes new approximation techniques to compute approximated conformance checking values close to exact solution values in a faster time. Those methods also provide upper and lower bounds for the approximated alignment value. Our experiments on real event data show that it is possible to improve the performance of conformance checking by using the proposed methods compared to using the state-of-the-art alignment approximation technique. Results show that in most of the cases, we provide tight bounds, accurate approximated alignment values, and similar deviation statistics.