Lightning Fast Matching Dependency Discovery with Desbordante
2026-07-12 • Databases
DatabasesArtificial IntelligenceMachine LearningPerformance
AI summaryⓘ
The authors studied a type of rule called matching dependency that helps find similar data points using custom similarity checks, which is useful for tasks like merging duplicate records or combining data from different sources. They improved the best current method, HyMD, by adding new tricks such as smarter sampling and better ways to organize the rules. These changes made the algorithm run much faster—up to 170 times in some tests. The improved tool is available in an open-source program that can be easily used with Python, letting users add their own ways to measure similarity.
functional dependencymatching dependencysimilarity functionentity resolutiondata deduplicationdata integrationalgorithm optimizationHyMDlattice operationssampling technique
Authors
Alexey Shlyonskikh, Michael Sinelnikov, Daniil Nikolaev, Yurii Litvinov, George Chernishev
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.