Pith. sign in

REVIEW 5 minor 25 references

Lightning Fast Matching Dependency Discovery with Desbordante

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read Focused sampling and denser lattice structures make matching-dependency discovery more than 40 imes faster on average, up to 170 imes on hard datasets.

desk verdict Solid systems paper: real 40–170× speedups on HyMD via focused sampling, lattice pruning, and denser LHS encoding, shipped with open C++/Python code. read the letter →

arxiv 2607.10771 v1 pith:KV6P5ADW submitted 2026-07-12 cs.DB cs.AIcs.LGcs.PF

Alexey Shlyonskikh , Michael Sinelnikov , Daniil Nikolaev , Yurii Litvinov , George Chernishev This is my paper · ORCID
classification cs.DBcs.AIcs.LGcs.PF
keywords matchingdependenciesdependencydiscoveryhybridalgorithmsdataprofilingentityresolutionlatticesearchsimilarityindexes
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

Matching dependencies say that if certain attribute values are similar under user-chosen metrics, other attributes must also be similar. They are powerful for entity resolution, deduplication and data cleaning, but discovery is exponential and previously limited to research prototypes. This paper shows that three concrete changes to the state-of-the-art hybrid algorithm—column-match-focused sampling that prefers high-similarity pairs, skipping irrelevant lattice nodes when testing generalizations, and a sparse left-hand-side representation—raise practical speed by more than 40 imes on average (and more than 170 imes on a classic bibliographic dataset) while still returning exactly the same minimal interesting dependencies. The resulting C++ implementation ships with a Python interface that accepts custom similarity functions, so the technique can be used today rather than remaining a laboratory curiosity.

What carries the argument

Focused sampling by column match: records are ordered via pre-built similarity indexes so that pairs with higher similarity are examined first; efficiency is measured by the ratio of violating pairs and the algorithm switches phases only when that ratio falls below a relaxing threshold, keeping the lattice near its final state.

What would settle it

Run both the optimized and reference implementations on a previously unseen real-world table that contains many near-duplicates but few exact equals (or on a synthetic table engineered to violate the 0.01 efficiency threshold) and check whether the sets of returned minimal matching dependencies differ or the speedup collapses below 2×.

Watch

Extended reading notes

Core claim

Re-engineering the hybrid HyMD algorithm with focused sampling that prioritizes high-similarity record pairs, an invariant-based generalization check that ignores already-known non-generalizing lattice nodes, and a pointer-friendly sparse representation of left-hand sides yields more than 40 imes average wall-clock speedup (peaking above 170 imes) over the prior Java reference while discovering identical minimal interesting matching dependencies.

Load-bearing premise

The new sampling heuristic and phase-switch rule remain complete and efficient on tables outside the seven evaluated datasets; the paper supplies no theoretical guarantee that the schedule never misses a minimal dependency or becomes pathologically slow.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper presents an industrial-grade C++ reimplementation of the HyMD algorithm for discovering matching dependencies (MDs), integrated into the Desbordante profiler. It contributes three main optimizations—focused sampling by column match (Section V-A), a faster generalization-lookup that exploits lattice minimality (Section V-B), and a denser LHS representation using (offset, similarity) pairs (Section V-C)—plus several technical improvements (decision-boundary indices, empty-node pruning, column-match ordering). Head-to-head experiments on seven public datasets against the original Metanome Java HyMD report average wall-clock speed-ups >40 imes (up to 170 imes on CORA) and substantial memory reductions (Tables V–VII), while the final lattice-traversal phase still enumerates the same minimal interesting MDs. Bidirectional Python bindings allow custom similarity functions.

Significance. Matching dependencies are among the most expressive data-quality patterns; their discovery has remained largely impractical because of exponential lattice size and quadratic pair enumeration. Delivering a ready-to-use, open-source C++ implementation that is more than an order of magnitude faster than the previous state-of-the-art prototype, together with Python integration for custom metrics, materially lowers the barrier to applying MDs in entity resolution, deduplication and schema matching. The empirical evidence is concrete (public baseline, public datasets, reproducible code) and the optimizations are described with enough algorithmic detail to be re-implemented or further improved. The work therefore constitutes a solid engineering and systems contribution that advances practical data profiling.

minor comments (5)
  1. Section V-A: the initial efficiency threshold of 0.01 and the lattice-stop fraction are presented as fixed heuristics. A short sensitivity paragraph (or an appendix table) showing how runtime and MD count change under modest variations would strengthen confidence that the schedule is robust.
  2. Table VI: preprocessing times improve even for the “vanilla” Desbordante rewrite; a one-sentence clarification that the gain comes mainly from faster metric implementations (rather than algorithmic changes) would avoid mis-attribution.
  3. Figures 6–7: the dual y-axes (time vs. number of MDs) are useful, yet the caption should explicitly state that the MD counts are those of the optimized implementation, so readers do not wonder whether the three versions produce identical cardinalities.
  4. Section VII: the claim that more than half of execution time is spent waiting for memory is plausible but unsupported by any profiler numbers; a brief citation of cache-miss or stall counters would make the future-work argument more concrete.
  5. Throughout: a few typographical inconsistencies remain (“Levenstein” vs. “Levenshtein”, “undecillions”, occasional missing articles). A final proof-reading pass would polish the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: empirical speedups measured against independent public baseline; optimizations do not redefine the MD lattice or completeness.

full rationale

The paper's central claim is an engineering result: a C++ reimplementation of HyMD plus three concrete optimizations (focused sampling by column match, skipping irrelevant generalization nodes via the lattice minimality invariant, and denser LHS representation as pairs of offsets/non-zero similarities) yields measured wall-clock and memory improvements over the public Metanome Java HyMD on seven external datasets (Tables V–VII). Completeness is preserved because the final lattice-traversal phase still exhaustively validates every remaining candidate against the full data; the sampling threshold (0.01) and stop heuristic only affect the hybrid schedule's efficiency, not the set of minimal interesting MDs that are output. No parameter is fitted to data and then re-presented as a prediction; no uniqueness theorem or ansatz is imported from the authors' prior work to force the result; self-citations to Desbordante are solely for platform context. The derivation chain is therefore self-contained against an external, independently implemented baseline and contains no definitional or self-citation circularity.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard lattice-theoretic properties of matching dependencies (already established by Fan et al. and Schirmer et al.), on the hybrid search framework of HyMD, and on a small set of engineering heuristics whose only free parameters are the sampling efficiency threshold and the lattice-stop fraction. No new physical or mathematical entities are postulated; the free parameters are ordinary algorithmic knobs whose effect is measured empirically.

free parameters (2)
  • sampling efficiency threshold = 0.01 (initial)
    Starts at 0.01 and is relaxed when returning to the sampling phase; controls when the algorithm switches from inference to lattice traversal (Section V-A).
  • lattice-stop fraction of invalidated MDs
    Heuristic adapted from HyFD that decides when to leave lattice traversal; exact numeric value not stated but described as 'a certain low value' (Section V-A).
assumptions (4)
  • domain assumption Only minimal MDs (w.r.t. the product order on decision boundaries) need be stored; any specialization of a holding MD also holds.
    Standard lattice property of matching dependencies used throughout Sections II and IV; taken from prior MD theory.
  • domain assumption Natural decision boundaries (actual similarity values occurring in the data) suffice; non-natural thresholds can be ignored.
    Definition 6 and subsequent search-space reduction; inherited from HyMD.
  • domain assumption Interestingness filters (cardinality, support, disjointness, minimum threshold ≈0.7) correctly discard uninteresting MDs without losing useful ones for the intended applications.
    Section II, following Schirmer et al.; the paper adopts the same filters.
  • domain assumption Similarity measures used in practice are symmetric and return 1.0 on equal values, enabling the short-sampling sub-strategy.
    Explicitly stated in Section V-A (⋆) as a precondition for the cluster-window sampling path.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lightning Fast Matching Dependency Discovery with Desbordante." pith.science (2026). https://pith.science/paper/KV6P5ADW

@misc{pith2026260710771,
  author       = {Pith},
  title        = {Pith review of: Lightning Fast Matching Dependency Discovery with Desbordante},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KV6P5ADW}},
  note         = {Machine review of arXiv:2607.10771}
}
read the original abstract

Matching dependency is a generalization of the functional dependency concept, which allows users to apply custom similarity functions for matching individual attributes. Matching dependencies have a wide range of applications for solving various data quality problems, such as entity resolution, data deduplication, data integration, schema matching, and many more. However, their discovery is a very computationally intensive problem, which limits their practical application. In this paper, we describe a number of optimization techniques for HyMD - currently the state-of-the-art algorithm for the discovery of matching dependencies. These optimizations belong to both technical and scientific domains. The most important of them are: 1) a new sampling technique, 2) a faster generalization lookup technique, and 3) an improved representation of a dependency. The first one aims to raise the efficiency of inference from record pairs, while the last two are designed to speed up lattice-related operations. To evaluate our optimizations, we implemented our version of HyMD in Desbordante, an open-source high-performance data profiler. Experiments demonstrated that they allow for a speedup of more than 40x over the state-of-the-art implementation on average, reaching a speedup greater than 170x in some cases. Finally, the improved version of HyMD is ready to use by anyone. It comes with bidirectional Python integration, which allows calling the C++ algorithm implementation from Python programs while allowing users to supply their custom matching functions.

Figures

Figures reproduced from arXiv: 2607.10771 by the authors.

Figure 1
Figure 1. The search space lattice for matching dependencies of our example (Table II) with “Distance” attribute in the RHS. Solid lines denote specializations [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. An overview of the HyMD algorithm, figure from [15]. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 4
Figure 4. Full sampling illustration represent a similarity index as an array of record IDs with pointers to the start/end of the sets of records. This structure is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figures from the paper (2 more)
Figure 6
Figure 6. Figure 6: Scaling the number of records 2 4 6 8 10 12 14 16 Column matches 0 5000 10000 15000 20000 25000 30000 Time [ms] 0 5000 10000 15000 20000 25000 MDs [#] [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 7
Figure 7. Figure 7: Scaling the number of column matches B. Experiments Experiment 1. In this experiment, we studied the over￾all performance of three implementations: vanilla HyMD (Metanome), vanilla HyMD (Desbordante), and optimized HyMD (Desbordante). The results are presented in Table…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 4 canonical work pages

  1. [1]

    Abedjan, L

    Z. Abedjan, L. Golab, F. Naumann, and T. Papenbrock,Data Profiling. Morgan & Claypool Publishers, 2018

    2018

  2. [2]

    Desbordante: from benchmarking suite to high-performance science-intensive data profiler (preprint)

    G. A. Chernishev, M. Polyntsov, A. Chizhov, K. Stupakovet al., “Desbordante: from benchmarking suite to high-performance science- intensive data profiler (preprint),”CoRR, vol. abs/2301.05965, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2301.05965

    work page Pith review arXiv doi:10.48550/arxiv.2301.05965 2023

  3. [3]

    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

  4. [4]

    Inclusion dependency discovery: An experimental evaluation of thirteen algorithms,

    F. D ¨ursch, A. Stebner, F. Windheuser, M. Fischer, T. Friedrich, N. Strelow, T. Bleifuß, H. Harmouch, L. Jiang, T. Papenbrock, and F. Naumann, “Inclusion dependency discovery: An experimental evaluation of thirteen algorithms,” inProceedings of the 28th ACM International Conference on Information and Knowledge Management, ser. CIKM ’19. New York, NY , US...

    work page doi:10.1145/3357384.3357916 2019

  5. [5]

    C. C. Aggarwal and J. Han,Frequent Pattern Mining. Springer Publishing Company, Incorporated, 2014

    2014

  6. [6]

    Bhunt: Automatic discovery of fuzzy algebraic constraints in relational data,

    P. G. Brown and P. J. Hass, “Bhunt: Automatic discovery of fuzzy algebraic constraints in relational data,” inProceedings of the 29th International Conference on Very Large Data Bases - Volume 29, ser. VLDB ’03. VLDB Endowment, 2003, p. 668–679

    2003

  7. [7]

    Sherlock: A deep learning approach to semantic data type detection,

    M. Hulsebos, K. Hu, M. Bakker, E. Zgraggen, A. Satyanarayan, T. Kraska, c. Demiralp, and C. Hidalgo, “Sherlock: A deep learning approach to semantic data type detection,” inProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, ser. KDD ’19. New York, NY , USA: Association for Computing Machinery, 2019, p. 1500–1...

    doi:10.1145/3292500.3330993 2019

  8. [8]

    Differential dependencies: Reasoning and discov- ery,

    S. Song and L. Chen, “Differential dependencies: Reasoning and discov- ery,”ACM Transactions on Database Systems (TODS), vol. 36, no. 3, pp. 1–41, 2011

    2011

Show all 25 references
  1. [9]

    Reasoning about record matching rules,

    W. Fan, X. Jia, J. Li, and S. Ma, “Reasoning about record matching rules,”Proceedings of the VLDB Endowment (PVLDB), vol. 2, no. 1, pp. 407–418, 2009

    2009

  2. [10]

    Data cleaning and query answering with matching dependencies and matching functions,

    L. Bertossi, S. Kolahi, and L. V . Lakshmanan, “Data cleaning and query answering with matching dependencies and matching functions,” in Proceedings of the 14th International Conference on Database Theory, 2011, pp. 268–279

    2011

  3. [11]

    Mdedup: Duplicate detection with matching dependencies,

    l. Koumarelas, T. Papenbrock, and F. Naumann, “Mdedup: Duplicate detection with matching dependencies,”Proc. VLDB Endow., vol. 13, no. 5, p. 712–725, jan 2020. [Online]. Available: https://doi.org/10. 14778/3377369.3377379

    2020

  4. [12]

    Solving data quality problems with desbordante: a demo,

    G. A. Chernishev, M. Polyntsov, A. Chizhov, K. Stupakovet al., “Solving data quality problems with desbordante: a demo,”CoRR, vol. abs/2307.14935, 2023. [Online]. Available: https://doi.org/10.48550/ arXiv.2307.14935

    2023 arXiv

  5. [13]

    Fast discovery of inclusion dependencies with desbordante,

    A. Smirnov, A. Chizhov, I. Shchuckin, N. Bobrov, and G. A. Chernishev, “Fast discovery of inclusion dependencies with desbordante,” in33rd Conference of Open Innovations Association, FRUCT 2023, Zilina, Slovakia, May 24-26, 2023. IEEE, 2023, pp. 264–275. [Online]. Available: h...

    2023 doi

  6. [14]

    Order in desbordante: Techniques for efficient implementation of order dependency discovery algorithms,

    Y . Kuzin, D. Shcheka, M. Polyntsov, K. Stupakov, M. Firsov, and G. A. Chernishev, “Order in desbordante: Techniques for efficient implementation of order dependency discovery algorithms,” in35th Conference of Open Innovations Association, FRUCT 2024, Tampere, Finland, April 2...

    2024

  7. [15]

    Efficient discovery of matching dependencies,

    P. Schirmer, T. Papenbrock, I. Koumarelas, and F. Naumann, “Efficient discovery of matching dependencies,”ACM Transactions on Database Systems, vol. 45, no. 3, pp. 1–33, Aug. 2020. [Online]. Available: https://doi.org/10.1145/3392778

    2020 doi

  8. [16]

    Dependencies revisited for improving data quality,

    W. Fan, “Dependencies revisited for improving data quality,” inProceed- ings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2008, pp. 159–170

    2008

  9. [17]

    Discovering matching dependencies,

    S. Song and L. Chen, “Discovering matching dependencies,” inPro- ceedings of the 18th ACM conference on Information and knowledge management, 2009, pp. 1421–1424

    2009

  10. [18]

    Efficient discovery of similarity constraints for matching depen- dencies,

    ——, “Efficient discovery of similarity constraints for matching depen- dencies,”Data & Knowledge Engineering, vol. 87, pp. 146–166, 2013

    2013

  11. [19]

    A hybrid approach to functional dependency discovery,

    T. Papenbrock and F. Naumann, “A hybrid approach to functional dependency discovery,” inProceedings of the 2016 International Conference on Management of Data, ser. SIGMOD ’16. New York, NY , USA: Association for Computing Machinery, 2016, p. 821–833. [Online]. Available: http...

    2016 doi

  12. [20]

    Efficient differential dependency discovery,

    S. Kuang, H. Yang, Z. Tan, and S. Ma, “Efficient differential dependency discovery,”Proceedings of the VLDB Endowment, vol. 17, no. 7, pp. 1552–1564, 2024

    2024

  13. [21]

    Data dependencies extended for variety and veracity: A family tree,

    S. Song, F. Gao, R. Huang, and C. Wang, “Data dependencies extended for variety and veracity: A family tree,”IEEE Transactions on Knowl- edge and Data Engineering, vol. 34, no. 10, pp. 4717–4736, 2020

    2020

  14. [22]

    Tane: An efficient algorithm for discovering functional and approximate depen- dencies,

    Y . Huhtala, J. K ¨arkk¨ainen, P. Porkka, and H. Toivonen, “Tane: An efficient algorithm for discovering functional and approximate depen- dencies,”The Computer Journal, vol. 42, no. 2, pp. 100–111, 1999

    1999

  15. [23]

    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

  16. [24]

    Allen and D

    M. Allen and D. Cervo,Multi-Domain Master Data Management: Advanced MDM and Data Governance in Practice, 1st ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2015

    2015

  17. [25]

    Loshin,Master Data Management

    D. Loshin,Master Data Management. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2009

    2009

Pith tools

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