Extending Desbordante with Probabilistic Functional Dependency Discovery Support

• URL: http://arxiv.org/abs/2607.23636v1
• Date: Sun, 26 Jul 2026 13:01:48 GMT
• Title: Extending Desbordante with Probabilistic Functional Dependency Discovery Support
• Abstract summary: We aim to support Probabilistic Functional Dependency inside Desbordante.<n>In this paper we study pFDs, both analytically and empirically.<n>We implement the algorithm for pFD discovery, as well as study its run time and memory consumption.
• Score: 0.05219568203653524
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Efficient Discovery of Conditional Dependencies with Desbordante [0.0]
  Conditional functional dependencies (CFDs) are functional dependencies with a restricted scope.<n>We build on the state-of-the-art CFDFinder algorithm and introduce a set of algorithmic and engineering improvements, including a parallelization strategy.<n>Our implementation is integrated into Desbordante - a high-performance open-source data profiler written in C++.
  arXiv  Detail & Related papers  (2026-07-04T21:15:59Z)
• VRAG-DFD: Verifiable Retrieval-Augmentation for MLLM-based Deepfake Detection [49.88962095967614]
  We propose the VRAG-DFD framework with accurate dynamic forgery knowledge retrieval and powerful critical reasoning capabilities.<n>In terms of data, we constructed two datasets with RAG: Forensic Knowledge Database (FKD) for DFD knowledge annotation, and Forensic Chain-of-Thought dataset (F-CoT) for critical CoT construction.<n>In terms of performance, VRAG-DFD achieved SOTA and competitive performance on DFD generalization testing.
  arXiv  Detail & Related papers  (2026-04-15T09:27:49Z)
• FDIF: Formula-Driven supervised Learning with Implicit Functions for 3D Medical Image Segmentation [15.58096401866496]
  Deep learning-based 3D medical image segmentation methods relies on large-scale labeled datasets.<n>Formula-Driven Supervised Learning method offers an appealing alternative by generating training data and labels directly from mathematical formulas.<n>We introduce Formula-Driven supervised learning with Implicit Functions (FDIF), a framework that enables scalable pre-training without using any real data and medical expert annotations.
  arXiv  Detail & Related papers  (2026-03-24T13:45:39Z)
• Redundancy-Driven Top-$k$ Functional Dependency Discovery [5.126404609788543]
  Functional dependencies (FDs) are basic constraints in relational databases and are used for many data management tasks.<n>Most FD discovery algorithms find all valid dependencies, but this causes two problems.<n>We propose SDP (Selective-Discovery-and-Prune), which discovers the top-$k$ FDs ranked by redundancy count.
  arXiv  Detail & Related papers  (2026-01-15T07:16:01Z)
• Efficiently Computing Similarities to Private Datasets [19.99000806126529]
  Many methods in differentially private model training rely on computing the similarity between a query point (such as public or synthetic data) and private data. We study the following fundamental algorithmic problem: Given a similarity function $f$ and a large high-dimensional private dataset $X subset mathbbRd$, output a differentially private (DP) data structure which approximates $sum_x in X f(x,y)$ for any query $y$.
  arXiv  Detail & Related papers  (2024-03-13T19:19:19Z)
• Can LLMs Separate Instructions From Data? And What Do We Even Mean By That? [60.50127555651554]
  Large Language Models (LLMs) show impressive results in numerous practical applications, but they lack essential safety features.<n>This makes them vulnerable to manipulations such as indirect prompt injections and generally unsuitable for safety-critical tasks.<n>We introduce a formal measure for instruction-data separation and an empirical variant that is calculable from a model's outputs.
  arXiv  Detail & Related papers  (2024-03-11T15:48:56Z)
• Federated Causal Discovery from Heterogeneous Data [70.31070224690399]
  We propose a novel FCD method attempting to accommodate arbitrary causal models and heterogeneous data. These approaches involve constructing summary statistics as a proxy of the raw data to protect data privacy. We conduct extensive experiments on synthetic and real datasets to show the efficacy of our method.
  arXiv  Detail & Related papers  (2024-02-20T18:53:53Z)
• Time-Series Forecasting: Unleashing Long-Term Dependencies with Fractionally Differenced Data [0.0]
  This study introduces a novel forecasting strategy that leverages the power of fractional differencing (FD) FD preserves memory in series while stabilizing it for modeling purposes. Supervised classification algorithms were employed to validate the performance of FD series.
  arXiv  Detail & Related papers  (2023-09-23T15:42:54Z)
• Score-based Diffusion Models in Function Space [137.70916238028306]
  Diffusion models have recently emerged as a powerful framework for generative modeling.<n>This work introduces a mathematically rigorous framework called Denoising Diffusion Operators (DDOs) for training diffusion models in function space.<n>We show that the corresponding discretized algorithm generates accurate samples at a fixed cost independent of the data resolution.
  arXiv  Detail & Related papers  (2023-02-14T23:50:53Z)
• Measuring dissimilarity with diffeomorphism invariance [94.02751799024684]
  We introduce DID, a pairwise dissimilarity measure applicable to a wide range of data spaces. We prove that DID enjoys properties which make it relevant for theoretical study and practical use.
  arXiv  Detail & Related papers  (2022-02-11T13:51:30Z)
• Federated Doubly Stochastic Kernel Learning for Vertically Partitioned Data [93.76907759950608]
  We propose a doubly kernel learning algorithm for vertically partitioned data. We show that FDSKL is significantly faster than state-of-the-art federated learning methods when dealing with kernels.
  arXiv  Detail & Related papers  (2020-08-14T05:46:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.