为高性能数据探查工具Desbordante添加概率函数依赖发现能力
Extending Desbordante with Probabilistic Functional Dependency Discovery Support
- 提出概率函数依赖（pFD）发现算法，适配脏数据场景
- 实测pFD算法在运行时间和内存上优于传统近似函数依赖方法
- 揭示了pFD与AFD的互补性，适用于高噪声数据清洗任务
数据探查旨在从数据中提取复杂模式，用于数据清洗、去重和异常检测等任务。函数依赖（FD）是经典模式，但对脏数据不敏感。为此，研究者提出近似函数依赖（AFD）和概率函数依赖（pFD）等松弛形式。本文聚焦于在高性能、开源的C++数据探查工具Desbordante中集成pFD发现能力。通过理论分析与实验评估，对比pFD与AFD在典型场景下的表现，验证了pFD在处理不确定性数据时的优势；实现并测试了pFD发现算法的运行时间与内存开销，并与AFD算法进行比较。结果表明，两种方法可互为补充，且在实际应用中具备不同适用边界。
原文摘要 · Abstract (English)
Data profiling aims to extract complex patterns from data for further analysis and use that data in domains such as data cleaning, data deduplication, anomaly detection, and many more. Functional dependencies (FDs) are one of the most well-known patterns. However, they are poorly suited for these tasks, as real data is usually dirty, and the rigid definition of FDs does not allow algorithms to locate them. For this reason, there are several formulations aimed at relaxing FDs to support dirty data, with approximate functional dependency (AFD) being the most popular one. Another formulation is the Probabilistic Functional Dependency (pFD), which we aim to support inside Desbordante - a science-intensive, high-performance and open-source data profiling tool implemented in C++. However, pFDs are relatively poorly studied, compared to AFDs. In this paper we study pFDs, both analytically and empirically. We start by assessing how different pFDs and AFDs are by studying cases in which pFDs have an edge over AFDs. Then, we implement the algorithm for pFD discovery, as well as study its run time and memory consumption. We also compare it with an AFD discovery algorithm. Lastly, we study the output of both algorithms to learn whether or not it is possible to use AFD discovery algorithm to get pFDs and vice versa.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。