优化匹配依赖发现算法，速度提升超40倍。
Lightning Fast Matching Dependency Discovery with Desbordante
- 引入新采样与高效查找技术，加速依赖推断。
- 在多个数据集上实现平均40倍以上提速，最高达170倍。
- 支持自定义相似度函数，适合数据清洗与集成场景。
匹配依赖是函数依赖的泛化，允许用户使用自定义相似度函数匹配属性，广泛应用于实体解析、去重、数据集成和模式匹配等数据质量问题。然而，其发现过程计算量巨大，限制了实际应用。本文针对当前最先进的HyMD算法，提出多项优化：1）一种新型采样技术以提升记录对推断效率；2）更快的泛化查找方法；3）改进的依赖表示形式。这些优化涵盖技术和科学层面，尤其提升格结构相关操作速度。我们在开源高性能数据探查工具Desbordante中实现优化后的HyMD。实验表明，相比现有最优实现，平均提速超过40倍，部分情况超过170倍。改进版本已可直接使用，支持双向Python接口，用户可在Python中调用C++实现，并自定义匹配函数。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。