高效发现数据中的条件依赖关系，加速百倍并节省内存。
Efficient Discovery of Conditional Dependencies with Desbordante
- 基于并行化优化的新型算法ParCFDFinder，提升处理效率。
- 相比旧版快318倍（平均118倍），内存占用减少23倍（平均14倍）。
- 可直接在普通电脑上快速分析数十万行数据，适合数据质量工具开发者。
条件函数依赖（CFDs）是作用于特定上下文的函数依赖，对数据质量任务、复杂完整性约束建模及数据洞察提取具有重要意义。本文研究了CFD发现问题，其计算成本高。我们基于现有最优算法CFDFinder，引入一系列算法与工程改进，包括并行策略，构建出ParCFDFinder。该实现集成于Desbordante——一个用C++编写的高性能开源数据探查工具，提供Python接口，使用户可在任意Python程序中调用CFD发现功能。实验表明，相比现有的Java实现Metanome，本方法在速度上提升达318倍（平均118倍），内存消耗降低23倍（平均14倍）。将ParCFDFinder集成至Desbordante，首次实现可在普通机器上合理时间内完成含数十万行数据的CFD发现。
原文摘要 · Abstract (English)
Conditional functional dependencies (CFDs) are functional dependencies with a restricted scope: they specify the context in which a dependency holds and are useful for data-quality tasks, specifying complex integrity constraints, and extracting valuable insights from data. We study the CFD discovery problem, which is computationally demanding. We build on the state-of-the-art CFDFinder algorithm and introduce a set of algorithmic and engineering improvements, including a parallelization strategy, to produce ParCFDFinder. Our implementation is integrated into Desbordante - a high-performance open-source data profiler written in C++ that exposes a Python interface, enabling CFD discovery to be invoked from any Python program. Experimental results show that our enhancements speed up the algorithm by up to $318\times$ ($118\times$ on average) and reduce memory usage by up to $23\times$ ($14\times$ on average) compared with the existing Java-based implementation of Metanome. Integrating ParCFDFinder into Desbordante makes it possible, for the first time, to conveniently discover CFDs on datasets with hundreds of thousands of rows on a commodity machine within a reasonable time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。