A Delta-Oracle for Fast Model Merge Conflict Estimation using Sketch-Based Critical Pair Analysis

@InProceedings{ME2024,
  author       = {Karl Kegel and 
                  Andreas Domanowski and 
                  Kevin Feichtinger and 
                  Romain Pascual and
                  Uwe A\ss{}mann},
  title        = {A Delta-Oracle for Fast Model Merge Conflict Estimation
                  using Sketch-Based Critical Pair Analysis},
  year         = {2024},
  isbn         = {9798400706226},
  publisher    = {Association for Computing Machinery},
  address      = {New York, NY, USA},
  doi          = {10.1145/3652620.3688341},
  abstract     = {Conflicting changes are a major challenge in
                  branch-based development and modeling. State-of-the-art
                  research proposes continuous analysis via attempted
                  three-way merges to find potential merge conflicts early
                  on. These approaches are computation-heavy due to the
                  necessity of comparing all variant combinations, ideally
                  for each change. This work proposes a conflict
                  approximation algorithm (oracle) for quick feedback. The
                  oracle approximates conflicts using critical pair
                  analysis on tracked delta sequences, providing a quick
                  feedback loop. The oracle is paired with a classical
                  slow-but-precise full model comparison algorithm, which
                  is run occasionally to validate the oracle's results.
                  This work contributes the Sketch-based Critical Pair
                  Analysis (SCPA) approach for fast merge conflict
                  estimation. SCPA's runtime depends only on the number of
                  changes and not the model size. We evaluate SCPA against
                  EMFCompare in different simulated model evolution
                  scenarios. We found that for the investigated model
                  sizes, SCPA is faster by a magnitude while the number of
                  found conflicts strongly correlates with EMFCompare.},
  booktitle    = {Proceedings of the ACM/IEEE 27th International
                  Conference on Model Driven Engineering Languages and
                  Systems},
  pages        = {1046--1055},
  numpages     = {10},
  keywords     = {merge conflict estimation, critical pair analysis,
                  oracle algorithm},
  venue        = {Linz, Austria},
  eventdate    = {2024-09-22/2024-09-27},
  series       = {MODELS Companion '24}
}