Efficient Discovery of Conditional Dependencies with Desbordante

• URL: http://arxiv.org/abs/2607.04030v1
• Date: Sat, 04 Jul 2026 21:15:59 GMT
• Title: Efficient Discovery of Conditional Dependencies with Desbordante
• Abstract summary: 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++.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Fast Discovery of Inclusion Dependencies with Desbordante [36.993555985790614]
  We describe techniques for efficient implementation of two algorithms for discovery of inclusion dependencies - Spider and Faida.<n>We propose an efficient parallelization technique, which greatly speeds up the algorithm while simultaneously reducing its memory consumption.<n>We report up to 5x improvement in terms of run time reduction for Spider and up to 8x for Faida.
  arXiv  Detail & Related papers  (2026-08-03T13:35:33Z)
• Lightning Fast Matching Dependency Discovery with Desbordante [0.0]
  We describe a number of optimization techniques for HyMD, the state-of-the-art algorithm for the discovery of matching dependencies.<n>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.<n> 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.
  arXiv  Detail & Related papers  (2026-07-12T13:59:54Z)
• 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)
• SimpleMem: Efficient Lifelong Memory for LLM Agents [73.74399447715052]
  We introduce SimpleMem, an efficient memory framework based on semantic lossless compression.<n>We propose a three-stage pipeline designed to maximize information density and token utilization.<n> Experiments on benchmark datasets show that our method consistently outperforms baseline approaches in accuracy, retrieval efficiency, and inference cost.
  arXiv  Detail & Related papers  (2026-01-05T21:02:49Z)
• Efficient Conformance Checking of Rich Data-Aware Declare Specifications (Extended) [49.46686813437884]
  We show that it is possible to compute data-aware optimal alignments in a rich setting with general data types and data conditions.<n>This is achieved by carefully combining the two best-known approaches to deal with control flow and data dependencies.
  arXiv  Detail & Related papers  (2025-06-30T10:16:21Z)
• OpenMLDB: A Real-Time Relational Data Feature Computation System for Online ML [35.15348680407141]
  This paper presents OpenMLDB, a feature computation system deployed in 4Paradigm's SageOne platform.<n>Technically, OpenMLDB first employs a unified query plan generator for consistent computation results across the offline and online stages.<n>OpenMLDB provides an online execution engine that resolves performance bottlenecks caused by long window computations.
  arXiv  Detail & Related papers  (2025-01-15T05:20:01Z)
• Data-Juicer 2.0: Cloud-Scale Adaptive Data Processing for and with Foundation Models [83.65386456026441]
  Data-Juicer 2.0 is a data processing system backed by 100+ data processing operators spanning text, image, video, and audio modalities.<n>It supports more critical tasks including data analysis, synthesis, annotation, and foundation model post-training.<n>The system is publicly available and has been widely adopted in diverse research fields and real-world products such as Alibaba Cloud PAI.
  arXiv  Detail & Related papers  (2024-12-23T08:29:57Z)
• CrackSCF: Lightweight Cascaded Fusion Network for Robust and Efficient Structural Crack Segmentation [36.93774494071781]
  CrackSCF is a lightweight Cascaded Fusion Crack Network designed to achieve robust crack segmentation.<n>This approach efficiently captures local patterns while operating with a minimal computational footprint.<n>The experimental results show that the CrackSCF method consistently outperforms the existing methods.
  arXiv  Detail & Related papers  (2024-08-23T03:21:51Z)
• TrueDeep: A systematic approach of crack detection with less data [0.0]
  We show that by incorporating domain knowledge along with deep learning architectures, we can achieve similar performance with less data. Our algorithms, developed with 23% of the overall data, have a similar performance on the test data and significantly better performance on multiple blind datasets.
  arXiv  Detail & Related papers  (2023-05-30T14:51:58Z)
• Going beyond research datasets: Novel intent discovery in the industry setting [60.90117614762879]
  This paper proposes methods to improve the intent discovery pipeline deployed in a large e-commerce platform. We show the benefit of pre-training language models on in-domain data: both self-supervised and with weak supervision. We also devise the best method to utilize the conversational structure (i.e., question and answer) of real-life datasets during fine-tuning for clustering tasks, which we call Conv.
  arXiv  Detail & Related papers  (2023-05-09T14:21:29Z)
• Efficient Wind Speed Nowcasting with GPU-Accelerated Nearest Neighbors Algorithm [0.0]
  This paper proposes a simple yet efficient high-altitude wind nowcasting pipeline. It processes efficiently a vast amount of live data recorded by airplanes over the whole airspace. It creates a unique context for each point in the dataset and then extrapolates from it.
  arXiv  Detail & Related papers  (2021-12-20T09:15:27Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  Federated Learning (FL) has become a popular paradigm for learning from distributed data. To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
  arXiv  Detail & Related papers  (2020-05-22T23:07:42Z)
• New advances in enumerative biclustering algorithms with online partitioning [80.22629846165306]
  This paper further extends RIn-Close_CVC, a biclustering algorithm capable of performing an efficient, complete, correct and non-redundant enumeration of maximal biclusters with constant values on columns in numerical datasets. The improved algorithm is called RIn-Close_CVC3, keeps those attractive properties of RIn-Close_CVC, and is characterized by: a drastic reduction in memory usage; a consistent gain in runtime.
  arXiv  Detail & Related papers  (2020-03-07T14:54:26Z)

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.