{"ID":6536220,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10771","arxiv_id":"2607.10771","title":"Lightning Fast Matching Dependency Discovery with Desbordante","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.","short_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...","url_abs":"https://arxiv.org/abs/2607.10771","url_pdf":"https://arxiv.org/pdf/2607.10771v1","authors":"[\"Alexey Shlyonskikh\",\"Michael Sinelnikov\",\"Daniil Nikolaev\",\"Yurii Litvinov\",\"George Chernishev\"]","published":"2026-07-12T13:59:54Z","proceeding":"cs.DB","tasks":"[\"cs.DB\",\"cs.AI\",\"cs.LG\",\"cs.PF\"]","methods":"[]","has_code":false}