EUVIMEDEUVIMED entdecken
Crossref

Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization

Pierre Faure–Giovagnoli, Simon Vilmin, Jean-Marc Petit, Vasile-Marian Scuturici

ACM Transactions on Database Systems · 31.12.2026 · 51 (4) · 1-45

DOI: 10.1145/3800938 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 16.04.2026. Verfasst von Pierre Faure–Giovagnoli und 3 weiteren Autor:innen. Die Arbeit nennt 78 Literaturangaben. Gefördert von: Compagnie Nationale du Rhône.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The incorporation of domain knowledge (DK) in AI has been studied for years and turns out to be critical in practice. Functions are also a basic notion for dealing with data science projects and are somehow related to DK. Consider the following scenario. Let \(D(y, z_1, \ldots , z_n)\) be a dataset, Alice a data scientist, Bob a domain expert and \(y = f(z_1, \ldots , z_n)\) a function known to Bob from his background knowledge. Alice is interested in the following simple yet crucial questions: How to define the satisfaction of f in D ? How to measure that satisfaction efficiently? How does this satisfaction relate to the supervised learning task of learning f from D ? It turns out that these problems are related to the study of counterexamples through the use of functional dependencies (FDs) and, in particular, FD measures used to quantify their satisfaction in a dataset such as the \(g_3\) indicator where the equality is replaced by more flexible predicates. In this article, we first examine the complexity of computing \(g_3\) . It is known that \(g_3\) can be computed in polynomial time when using equality, while it becomes NP -hard when using general predicates. Our goal is to refine this dichotomy by studying the impact of the following common properties: reflexivity, transitivity, symmetry, and antisymmetry. We show that symmetry and transitivity together are sufficient to guarantee that the \(g_3\) can be computed in polynomial time. However, removing one of them makes the problem NP -hard. Second, we study the computation of \(g_3\) in the polynomial and NP -hard cases identified previously. We propose different exact and approximate solutions for the computation of \(g_3\) in both cases. We compare these solutions in a detailed experimental study of time performance and approximation accuracy. All the algorithms are also made available via fastg3 , an open-source Python library with an underlying C++ implementation. Finally, we link counterexamples and \(g_3\) to supervised learning with a web application called adesit . adesit is intended to be part of an iterative data refinement process right after data selection and just before the machine learning process itself. It provides a way to evaluate the ability of a dataset to perform well for a given supervised learning problem through statistical and visual exploration. In a last section, we validate our approach by applying it to the industrial problem of air gap monitoring in compact hydro-generators.

Förderung

  • Compagnie Nationale du Rhône

Zitieren

APA

Faure–Giovagnoli, P., Vilmin, S., Petit, J., & Scuturici, V. (2026). Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization. ACM Transactions on Database Systems, 51(4), 1-45. https://doi.org/10.1145/3800938

Vancouver

Faure–Giovagnoli P, Vilmin S, Petit J, Scuturici V. Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization. ACM Transactions on Database Systems. 2026;51(4):1-45. doi:10.1145/3800938

BibTeX
@article{FaureGiovagnoli2026,
  author = {Faure–Giovagnoli, Pierre and Vilmin, Simon and Petit, Jean-Marc and Scuturici, Vasile-Marian},
  title = {Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization},
  journal = {ACM Transactions on Database Systems},
  year = {2026},
  volume = {51},
  number = {4},
  pages = {1--45},
  doi = {10.1145/3800938}
}
Kostenlos starten →