Conformance Checking for Less: Efficient Conformance Checking for Long Event Sequences

• URL: http://arxiv.org/abs/2505.21506v1
• Date: Sun, 09 Mar 2025 16:42:59 GMT
• Title: Conformance Checking for Less: Efficient Conformance Checking for Long Event Sequences
• Authors: Eli Bogdanov, Izack Cohen, Avigdor Gal,
• Abstract summary: ConLES is a sliding-window conformance checking approach for long event sequences.<n>It partitions traces into manageable subtraces and aligns each against the expected behavior.<n>We use global information that captures structural properties of both the trace and the process model.
• Score: 3.3170150440851485
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Long event sequences (termed traces) and large data logs that originate from sensors and prediction models are becoming increasingly common in our data-rich world. In such scenarios, conformance checking-validating a data log against an expected system behavior (the process model) can become computationally infeasible due to the exponential complexity of finding an optimal alignment. To alleviate scalability challenges for this task, we propose ConLES, a sliding-window conformance checking approach for long event sequences that preserves the interpretability of alignment-based methods. ConLES partitions traces into manageable subtraces and iteratively aligns each against the expected behavior, leading to significant reduction of the search space while maintaining overall accuracy. We use global information that captures structural properties of both the trace and the process model, enabling informed alignment decisions and discarding unpromising alignments, even if they appear locally optimal. Performance evaluations across multiple datasets highlight that ConLES outperforms the leading optimal and heuristic algorithms for long traces, consistently achieving the optimal or near-optimal solution. Unlike other conformance methods that struggle with long event sequences, ConLES significantly reduces the search space, scales efficiently, and uniquely supports both predefined and discovered process models, making it a viable and leading option for conformance checking of long event sequences.

Related papers

• Efficient Conformance Checking of Rich Data-Aware Declare Specifications (Extended) [49.46686813437884]
  We show that it is possible to compute data-aware optimal alignments in a rich setting with general data types and data conditions.<n>This is achieved by carefully combining the two best-known approaches to deal with control flow and data dependencies.
  arXiv  Detail & Related papers  (2025-06-30T10:16:21Z)
• $φ$-Decoding: Adaptive Foresight Sampling for Balanced Inference-Time Exploration and Exploitation [22.607133083903125]
  In-time optimization scales computation to derive deliberate reasoning steps for effective performance.<n>We frame the decoding strategy as foresight sampling, leveraging simulated future steps to obtain globally optimal step estimation.<n>Experiments show $phi$-Decoding outperforms strong baselines in both performance and efficiency.
  arXiv  Detail & Related papers  (2025-03-17T15:38:33Z)
• ProTracker: Probabilistic Integration for Robust and Accurate Point Tracking [41.889032460337226]
  ProTracker is a novel framework for accurate and robust long-term dense tracking of arbitrary points in videos.<n>This design effectively combines global semantic information with temporally aware low-level features.<n>Experiments demonstrate that ProTracker attains state-of-the-art performance among optimization-based approaches.
  arXiv  Detail & Related papers  (2025-01-06T18:55:52Z)
• Cell as Point: One-Stage Framework for Efficient Cell Tracking [54.19259129722988]
  We propose a novel end-to-end one-stage framework that reimagines cell tracking by treating Cell as Point.<n>Unlike traditional methods, CAP eliminates the need for explicit detection or segmentation, instead jointly tracking cells for sequences in one stage.<n> CAP demonstrates promising cell tracking performance and is 10 to 55 times more efficient than existing methods.
  arXiv  Detail & Related papers  (2024-11-22T10:16:35Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• A Scalable and Near-Optimal Conformance Checking Approach for Long Traces [3.3170150440851485]
  Conformity checking, a key task in process mining, can become computationally infeasible due to the exponential complexity of finding an optimal alignment. This paper introduces a novel sliding window approach to address these scalability challenges. By breaking down traces into manageable subtraces and iteratively aligning each with the process model, our method significantly reduces the search space.
  arXiv  Detail & Related papers  (2024-06-08T11:04:42Z)
• Parsimonious Optimal Dynamic Partial Order Reduction [1.5029560229270196]
  We present Parsimonious-OPtimal DPOR (POP), an optimal DPOR algorithm for analyzing multi-threaded programs under sequential consistency. POP combines several novel algorithmic techniques, including (i) a parsimonious race reversal strategy, which avoids multiple reversals of the same race. Our implementation in Nidhugg shows that these techniques can significantly speed up the analysis of concurrent programs, and do so with low memory consumption.
  arXiv  Detail & Related papers  (2024-05-18T00:07:26Z)
• Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
  We propose two strategies to learn from large-scale unlabeled data. The first strategy performs a local neighborhood sampling to reduce the dataset size in each without violating neighborhood relationships. A second strategy leverages a novel Re-Ranking technique, which has a lower time upper bound complexity and reduces the memory complexity from O(n2) to O(kn) with k n.
  arXiv  Detail & Related papers  (2023-07-26T16:19:19Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Adaptive Anomaly Detection for Internet of Things in Hierarchical Edge Computing: A Contextual-Bandit Approach [81.5261621619557]
  We propose an adaptive anomaly detection scheme with hierarchical edge computing (HEC) We first construct multiple anomaly detection DNN models with increasing complexity, and associate each of them to a corresponding HEC layer. Then, we design an adaptive model selection scheme that is formulated as a contextual-bandit problem and solved by using a reinforcement learning policy network.
  arXiv  Detail & Related papers  (2021-08-09T08:45:47Z)
• Generalizable Mixed-Precision Quantization via Attribution Rank Preservation [90.26603048354575]
  We propose a generalizable mixed-precision quantization (GMPQ) method for efficient inference. Our method obtains competitive accuracy-complexity trade-off compared with the state-of-the-art mixed-precision networks.
  arXiv  Detail & Related papers  (2021-08-05T16:41:57Z)
• Efficient Conformance Checking using Approximate Alignment Computation with Tandem Repeats [0.03222802562733786]
  Conformance checking aims to find and describe the differences between a process model capturing the expected process behavior and a corresponding event log recording the observed behavior. Alignments are an established technique to compute the distance between a trace in the event log and the closest execution trace of a corresponding process model. We propose a novel approximate technique that uses pre- and post-processing steps to compress the length of a trace and recompute the alignment cost.
  arXiv  Detail & Related papers  (2020-04-02T03:50:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.