Pith. sign in

REVIEW 2 major objections 4 minor 15 references

Efficient Discovery of Conditional Dependencies with Desbordante

T0 review · 2 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Algorithmic and engineering improvements plus parallel lattice traversal turn CFD discovery practical on commodity machines for tables of hundreds of thousands of rows.

desk verdict Solid engineering paper that makes CFD mining practical on 100k-row tables via C++ reimplementation, four concrete optimizations, and lattice parallelization; the 118 imes average speedup is real under the tested slice. read the letter →

arxiv 2607.04030 v1 pith:NTOPKDWT submitted 2026-07-04 cs.DB cs.AIcs.DCcs.LGcs.PF

Ivan Kozhukov , Dmitry Fedoseev , Maksim Emelyanov , Artem Smola , Pyotr Senichenkov , Pavel Anosov , George Chernishev This is my paper · ORCID
classification cs.DBcs.AIcs.DCcs.LGcs.PF
keywords conditionalfunctionaldependenciesCFDdiscoverydataprofilingalgorithmengineeringparallelizationqualitypatternmining
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Conditional functional dependencies (CFDs) capture rules that hold only inside a restricted context of the data; they are useful for data cleaning, complex constraints, and insight mining, yet discovering them is expensive. This paper starts from the prior CFDFinder algorithm, reimplements it in C++, and adds targeted optimizations—lightweight candidate patterns, bitmask-based cover pruning, batch processing, better data structures, and a thread-pool parallelization of independent lattice levels—yielding ParCFDFinder. Experiments on real and synthetic tables show speed-ups of up to 318 imes (118 imes on average) and memory reductions of up to 23 imes (14 imes on average) versus the existing Java implementation, so that tables with hundreds of thousands of rows can now be processed on ordinary hardware in reasonable time. The resulting code is integrated into an open-source C++ profiler that exposes a Python interface, making the faster algorithm immediately usable from ordinary data-science workflows.

What carries the argument

ParCFDFinder—the optimized, parallel CFDFinder pipeline whose core is a batched, bitmask-pruned pattern-generation stage together with a thread-pool lattice traversal that exploits independence of candidates at the same level.

What would settle it

Re-run the identical SupportIndependent + ConstantExpansion settings on the same tables with a different secondary pattern ordering or with an alternative pruning strategy (for example Partial FD or NegativeConstant) and check whether the reported 100 k-row times and memory factors still hold.

Watch

Extended reading notes

Core claim

A carefully engineered C++ reimplementation of CFDFinder, augmented by deferred cover construction via bitmasks, elimination of duplicate pattern generation, batch processing of candidates, improved hash structures, and parallel traversal of independent lattice levels, produces ParCFDFinder that is up to 318 times faster and uses up to 23 times less memory than the prior Java baseline, thereby making CFD discovery practical for the first time on commodity machines for tables of hundreds of thousands of rows.

Load-bearing premise

The measured speed-ups and the claim of practicality rest on a fixed pruning/expansion configuration and a deterministic secondary ordering introduced only for reproducibility; different user-chosen strategies may change both runtime and the discovered CFD set.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper reimplements and optimizes the state-of-the-art CFDFinder algorithm for conditional functional dependency discovery as ParCFDFinder in C++ inside the open-source Desbordante profiler (with Python bindings). Algorithmic changes target the dominant pattern-tableau generation stage (unique-value expansion, deferred cover construction via bitmasks, batch candidate processing, negative-constant reuse) plus lattice-level parallelization via a thread pool. Against the Java Metanome baseline, the authors report up to 318 imes (avg. 118 imes) wall-clock speedup and up to 23 imes (avg. 14 imes) memory reduction on public and synthetic datasets, with row-, column- and thread-scalability plots and a short medical case study. Correctness is checked by imposing a deterministic secondary ordering on equal-support patterns so that both implementations emit identical CFD counts when both finish.

Significance. If the measured factors hold under realistic use, the work materially extends the practical reach of CFD mining: commodity machines can now finish on tables of order 10^5 rows that previously timed out. The open C++/Python integration into a maintained profiler, the explicit engineering of the 99 % bottleneck, and the reproducible comparison methodology are concrete contributions that data-profiling and data-quality researchers can immediately reuse. The result is incremental rather than foundational, yet it closes a clear usability gap left by the unmaintained Metanome prototype.

major comments (2)
  1. [§VI.B–C, Table III] §VI.B–C and Table III evaluate only SupportIndependentStrategy + ConstantExpansionStrategy under one fixed parameter vector (5 % min support gain, 10 % max support drop, confidence 1.0, max tableau length 2000). While the authors correctly note that pattern generation dominates runtime, the headline practicality claim for “hundreds of thousands of rows” is therefore demonstrated only for this slice; a short sensitivity check (or at least a statement of expected behaviour) for NegativeConstant, Range and Partial-FD strategies listed in §IV would strengthen the central claim.
  2. [Abstract, §I] The “for the first time” phrasing in the abstract and §I is relative only to Metanome’s CFDFinder. Related-work algorithms (FastCFD, CTANE, CFUN) already target different arity/support regimes; a one-paragraph clarification of the precise regime in which ParCFDFinder is newly practical would avoid over-claiming relative to the broader literature.
minor comments (4)
  1. [Table II vs Table III] Table II omits several datasets that appear in Table III (Avocado Prices, nursery). Adding their row/column/size statistics would make the experimental corpus self-contained.
  2. [Figs. 2–4] Figures 2–4 use a log y-axis for time yet still mark “timeout” only for Metanome; a short caption note that C++ runs never hit the three-hour limit would improve readability.
  3. [§VI.A] The secondary ordering criteria introduced in §VI.A for determinism are described only at a high level (“compare the attribute values of the patterns”). A short formal definition or pseudocode fragment would aid re-implementation.
  4. [§I, §IV.D] Minor typographical inconsistencies appear (e.g., “P roduct” with spaces in the introduction example, mixed “g1”/“g₁” notation). A final proof-reading pass would clean them.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: empirical systems evaluation of algorithmic optimizations measured against external baseline

full rationale

The paper is a systems/engineering contribution that reimplements and optimizes the existing CFDFinder algorithm (from Metanome) in C++, adds concrete techniques (unique-value expansion, cover-mask pruning, batch processing, negative-constant reuse, lattice-level parallelization via Boost.Asio), integrates the result into Desbordante, and reports wall-clock and memory measurements on public datasets. The headline speed-ups (up to 318× / avg 118×) and memory reductions (up to 23× / avg 14×) are obtained by direct comparison with the unmodified Java baseline under identical pruning/expansion parameters; correctness is checked by forcing deterministic secondary ordering so that both implementations emit identical CFD counts when both finish. Self-citations ([2], [5]–[8]) supply only background on the Desbordante framework and prior C++ reimplementation experience; none is used as a load-bearing lemma, uniqueness theorem, or fitted parameter that is later re-presented as a prediction. There are no self-definitional equations, no parameters fitted to data and then “predicted,” and no renaming of known empirical patterns. The derivation chain is therefore self-contained and externally falsifiable.

Assumptions & free parameters 4 free parameters · 3 assumptions · 1 invented entities

The work rests on standard definitions of FDs/CFDs, the existing CFDFinder lattice-traversal skeleton, and a handful of experimental configuration constants. No new physical or mathematical entities are postulated; free parameters are only the mining thresholds chosen for the reported runs.

free parameters (4)
  • minimum support gain = 5 % of rows
    Fixed at 5 % of |r| for all reported experiments; directly controls which patterns enter the frontier and therefore both runtime and the set of returned CFDs.
  • maximum support drop = 10 %
    Fixed at 10 %; used by SupportIndependentStrategy to decide whether a specialized CFD is retained.
  • maximum pattern tableau length = 2000
    Hard cap of 2000 patterns; aborts further expansion once reached.
  • minimum confidence = 1.0
    Set to 1.0 (exact CFDs only) for the main experiments.
assumptions (3)
  • standard math Standard definitions of functional dependency, conditional functional dependency, cover, local/global support and confidence (Defs. 1–12).
    Taken as given from the data-profiling literature; all subsequent algorithms operate on these notions.
  • domain assumption The set of maximal non-FDs produced by a modified HyFD is a correct and complete starting point for the lattice traversal.
    Inherited from CFDFinder / HyFD; correctness of ParCFDFinder rests on this preprocessing step remaining sound.
  • domain assumption Independent tableau-generation tasks for candidates at the same lattice level may be executed concurrently without synchronization beyond a final merge.
    Stated in §V.B.3; underpins the parallelization claim.
invented entities (1)
  • ParCFDFinder independent evidence
    purpose: Name for the optimized, parallel C++ realization of CFDFinder that incorporates the four listed engineering improvements and the thread-pool lattice traversal.
    The paper’s central artifact; it is an algorithmic variant rather than a new mathematical object, and its independent evidence is the open-source implementation plus the experimental measurements.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Discovery of Conditional Dependencies with Desbordante." pith.science (2026). https://pith.science/paper/NTOPKDWT

@misc{pith2026260704030,
  author       = {Pith},
  title        = {Pith review of: Efficient Discovery of Conditional Dependencies with Desbordante},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NTOPKDWT}},
  note         = {Machine review of arXiv:2607.04030}
}
abstract

Conditional functional dependencies (CFDs) are functional dependencies with a restricted scope: they specify the context in which a dependency holds and are useful for data-quality tasks, specifying complex integrity constraints, and extracting valuable insights from data. We study the CFD discovery problem, which is computationally demanding. We build on the state-of-the-art CFDFinder algorithm and introduce a set of algorithmic and engineering improvements, including a parallelization strategy, to produce ParCFDFinder. Our implementation is integrated into Desbordante - a high-performance open-source data profiler written in C++ that exposes a Python interface, enabling CFD discovery to be invoked from any Python program. Experimental results show that our enhancements speed up the algorithm by up to $318\times$ ($118\times$ on average) and reduce memory usage by up to $23\times$ ($14\times$ on average) compared with the existing Java-based implementation of Metanome. Integrating ParCFDFinder into Desbordante makes it possible, for the first time, to conveniently discover CFDs on datasets with hundreds of thousands of rows on a commodity machine within a reasonable time.

Figures

Figures reproduced from arXiv: 2607.04030 by the authors.

Figure 1
Figure 1. Schema of CFDFinder algorithm CFUN is an extension of the FUN algorithm (originally designed for standard functional dependencies) that has been adapted for the conditional setting. The algorithm introduces the concepts of conditional agree sets, conditional closure, and quasi-closure. Operating in a levelwise manner (akin to Apriori), CFUN identifies the canonical cover of satisfied CFDs by computing the difference… view at source ↗
Figure 2
Figure 2. Scalability with respect to the number of rows: comparison of Java [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Scalability with respect to the number of rows: C++ implementations [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Scalability with respect to the number of columns. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Scalability with respect to the number of threads. [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 2 canonical work pages

  1. [1]

    Functional dependency discovery: an experimental evaluation of seven algorithms,

    T. Papenbrock, J. Ehrlich, J. Marten, T. Neubert, J.-P. Rudolph, M. Sch ¨onberg, J. Zwiener, and F. Naumann, “Functional dependency discovery: an experimental evaluation of seven algorithms,”Proc. VLDB Endow., vol. 8, no. 10, p. 1082–1093, jun 2015. [Online]. Available: https://doi.org/10.14778/2794367.2794377

    doi:10.14778/2794367.2794377 2015

  2. [2]

    Desbordante: from benchmarking suite to high-performance science-intensive data profiler,

    G. Chernishev, M. Polyntsov, A. Chizhov, K. Stupakov, I. Shchuckin, A. Smirnov, M. Strutovskyet al., “Desbordante: from benchmarking suite to high-performance science-intensive data profiler,” in Proceedings of the 8th International Conference on Data Science and Management of Data (12th ACM IKDD CODS and 30th COMAD), ser. CODS-COMAD ’24. New York, NY , U...

    work page doi:10.1145/3703323.3703725 2025

  3. [3]

    Discovering interesting conditional functional depen- dencies,

    M. Grundke, “Discovering interesting conditional functional depen- dencies,” Master’s thesis, Information Systems Chair Hasso-Plattner- Institute, Potsdam, 2018

    2018

  4. [4]

    Data profiling with Metanome,

    T. Papenbrock, T. Bergmann, M. Finke, J. Zwiener, and F. Naumann, “Data profiling with Metanome,”Proc. VLDB Endow., vol. 8, no. 12, p. 1860–1863, Aug. 2015. [Online]. Available: https: //doi.org/10.14778/2824032.2824086

    work page doi:10.14778/2824032.2824086 2015

  5. [5]

    Lightning fast matching dependency discovery with desbordante,

    A. Shlyonskikh, M. Sinelnikov, D. Nikolaev, Y . Litvinov, and G. Cherni- shev, “Lightning fast matching dependency discovery with desbordante,” in2024 36th Conference of Open Innovations Association (FRUCT), 2024, pp. 729–740

    2024

  6. [6]

    Fast discovery of inclusion dependencies with desbordante,

    A. Smirnov, A. Chizhov, I. Shchuckin, N. Bobrov, and G. Chernishev, “Fast discovery of inclusion dependencies with desbordante,” in2023 33rd Conference of Open Innovations Association (FRUCT), 2023, pp. 264–275

    2023

  7. [7]

    Order in desbordante: Techniques for efficient imple- mentation of order dependency discovery algorithms,

    Y . Kuzin, D. Shcheka, M. Polyntsov, K. Stupakov, M. Firsov, and G. Chernishev, “Order in desbordante: Techniques for efficient imple- mentation of order dependency discovery algorithms,” in2024 35th Conference of Open Innovations Association (FRUCT), 2024, pp. 413– 424

    2024

  8. [8]

    Des- bordante: a framework for exploring limits of dependency discovery algorithms,

    M. Strutovskiy, N. Bobrov, K. Smirnov, and G. Chernishev, “Des- bordante: a framework for exploring limits of dependency discovery algorithms,” in2021 29th Conference of Open Innovations Association (FRUCT), 2021, pp. 344–354

    2021

Show all 15 references
  1. [9]

    Discovering data quality rules,

    F. Chiang and R. Miller, “Discovering data quality rules,”PVLDB, vol. 1, pp. 1166–1177, 08 2008

    2008

  2. [10]

    Discovering conditional functional dependencies,

    W. Fan, F. Geerts, L. V . S. Lakshmanan, and M. Xiong, “Discovering conditional functional dependencies,” pp. 1231–1234, 2009

    2009

  3. [11]

    Mining statistically important equivalence classes and delta-discriminative emerging patterns,

    J. Li, G. Liu, and L. Wong, “Mining statistically important equivalence classes and delta-discriminative emerging patterns,”KDD ’07: Proceed- ings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 430–439, 08 2007

    2007

  4. [12]

    Discovering (frequent) constant conditional functional dependencies,

    T. Diallo, N. Novelli, and J.-M. Petit, “Discovering (frequent) constant conditional functional dependencies,”Int. J. Data Mining, Modelling and Management Int. J. Data Mining, Modelling and Management, vol. 120, 01 2010

    2010

  5. [13]

    C” from the “FD

    J. Rammelaere and F. Geerts,Revisiting Conditional Functional De- pendency Discovery: Splitting the “C” from the “FD”: European Conference, ECML PKDD 2018, Dublin, Ireland, September 10–14, 2018, Proceedings, Part II, 01 2019, pp. 552–568

    2018

  6. [14]

    A hybrid approach to functional dependency discovery,

    T. Papenbrock and F. Naumann, “A hybrid approach to functional dependency discovery,” pp. 821–833, 06 2016

    2016

  7. [15]

    On generating near-optimal tableaux for conditional functional dependencies,

    L. Golab, H. Karloff, F. Korn, D. Srivastava, and B. Yu, “On generating near-optimal tableaux for conditional functional dependencies,”Proc. VLDB Endow., vol. 1, no. 1, p. 376–390, Aug. 2008. [Online]. Available: https://doi.org/10.14778/1453856.1453900

    2008 doi

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.