Lightning Fast Matching Dependency Discovery with Desbordante

This paper presents optimizations for HyMD, a state-of-the-art algorithm for discovering matching dependencies, which generalize functional dependencies by allowing custom similarity functions between attributes. The work introduces a new sampling technique, faster generalization lookup, and a more efficient dependency representation. The optimized implementation is integrated into Desbordante, an open-source, high-performance data profiler. According to the paper’s abstract, experiments achieved an average speedup of more than 40x over the previous state-of-the-art implementation, with some cases exceeding 170x. The system also provides bidirectional Python integration and supports user-defined matching functions implemented in Python.