Lightning Fast Matching Dependency Discovery with Desbordante

• URL: http://arxiv.org/abs/2607.10771v1
• Date: Sun, 12 Jul 2026 13:59:54 GMT
• Title: Lightning Fast Matching Dependency Discovery with Desbordante
• Abstract summary: We describe a number of optimization techniques for HyMD, the state-of-the-art algorithm for the discovery of matching dependencies.<n>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.<n> 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Fast Discovery of Inclusion Dependencies with Desbordante [36.993555985790614]
  We describe techniques for efficient implementation of two algorithms for discovery of inclusion dependencies - Spider and Faida.<n>We propose an efficient parallelization technique, which greatly speeds up the algorithm while simultaneously reducing its memory consumption.<n>We report up to 5x improvement in terms of run time reduction for Spider and up to 8x for Faida.
  arXiv  Detail & Related papers  (2026-08-03T13:35:33Z)
• optimize_anything: A Universal API for Optimizing any Text Parameter [98.42497715725356]
  We show a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs.<n>We show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm.
  arXiv  Detail & Related papers  (2026-05-19T10:18:12Z)
• Optimization-Aware Test Generation for Deep Learning Compilers [18.99078574014009]
  OATest is a novel approach for synthesizing optimization-aware computational graphs.<n>It can detect more bugs and achieve higher code coverage in TVM and ONNXRutimes.<n> OATest uncovers 58 previously unknown bugs, 36 of which have been confirmed or fixed by developers.
  arXiv  Detail & Related papers  (2025-11-24T09:27:59Z)
• e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving [14.658242244274687]
  E-graphs have attracted interest in many fields, particularly in logic synthesis and formal verification.<n>We present e-boost, a novel framework that bridges this gap through three key innovations.<n>e-boost demonstrates 558x runtime speedup over traditional exact approaches (ILP) and 19.04% performance improvement over the state-of-the-art extraction framework (SmoothE)
  arXiv  Detail & Related papers  (2025-08-18T15:38:12Z)
• Bag of Tricks for Inference-time Computation of LLM Reasoning [10.366475014241407]
  We investigate and benchmark diverse inference-time computation strategies across reasoning tasks of varying complexity.<n>Our ablation studies reveal that previously overlooked strategies can significantly enhance performance.<n>We establish a standardized benchmark for inference-time computation by systematically evaluating six representative methods across eight reasoning tasks.
  arXiv  Detail & Related papers  (2025-02-11T02:31:11Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  We show that by efficiently parallelizing existing causal discovery methods, we can scale them to thousands of dimensions. Specifically, we focus on the causal ordering subprocedure in DirectLiNGAM and implement GPU kernels to accelerate it. This allows us to apply DirectLiNGAM to causal inference on large-scale gene expression data with genetic interventions yielding competitive results.
  arXiv  Detail & Related papers  (2024-03-06T15:06:11Z)
• Decreasing the Computing Time of Bayesian Optimization using Generalizable Memory Pruning [56.334116591082896]
  We show a wrapper of memory pruning and bounded optimization capable of being used with any surrogate model and acquisition function. Running BO on high-dimensional or massive data sets becomes intractable due to this time complexity. All model implementations are run on the MIT Supercloud state-of-the-art computing hardware.
  arXiv  Detail & Related papers  (2023-09-08T14:05:56Z)
• FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels [82.53569355337586]
  This work offers an efficient solution to temporal point processes inference using general parametric kernels with finite support. The method's effectiveness is evaluated by modeling the occurrence of stimuli-induced patterns from brain signals recorded with magnetoencephalography (MEG) Results show that the proposed approach leads to an improved estimation of pattern latency than the state-of-the-art.
  arXiv  Detail & Related papers  (2022-10-10T12:35:02Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)

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.