# Lightning Fast Matching Dependency Discovery with Desbordante

arXiv: https://arxiv.org/abs/2607.10771 · HTML: https://mlsanity.com/paper/2607.10771/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 30 references that are in the map.
- First posted on arXiv 12 Jul 2026.

## Builds on (most cited first, 3 of 3)

- [Sherlock: A Deep Learning Approach to Semantic Data Type Detection](https://mlsanity.com/paper/1905.10688/) (2019)
- [Desbordante: from benchmarking suite to high-performance science-intensive data profiler (preprint)](https://mlsanity.com/paper/2301.05965/) (2023)
- [Solving Data Quality Problems with Desbordante: a Demo](https://mlsanity.com/paper/2307.14935/) (2023)

## Abstract (arXiv)

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.