Fast Discovery of Inclusion Dependencies with Desbordante

• URL: http://arxiv.org/abs/2608.02213v1
• Date: Mon, 03 Aug 2026 13:35:33 GMT
• Title: Fast Discovery of Inclusion Dependencies with Desbordante
• Abstract summary: 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.
• Score: 36.993555985790614
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Inclusion dependency is a relation between attributes of tables that indicates possible Primary Key-Foreign Key references. Automatic discovery of inclusion dependencies is a relevant problem for both academic and industrial communities. The core concern for this problem is the efficiency of discovery process, since it is a computationally expensive task. However, existing studies only address the algorithmic side, while leaving out the implementation aspect. At the same time, engineering details are at least as important as the algorithmic ones for achieving good performance. In this paper, we describe techniques for efficient implementation of two algorithms for discovery of inclusion dependencies - Spider and Faida. The first one is a classic algorithm whose ideas lie in the foundation of many other inclusion dependency discovery algorithms. We propose an efficient parallelization technique, which greatly speeds up the algorithm while simultaneously reducing its memory consumption. The second one is the state-of-the-art approximate algorithm, which we approach by applying four types of optimizations: data buffering, SIMD-enabled execution, careful hash-table selection and parallelization. In order to experimentally evaluate our techniques, we have implemented these algorithms in Desbordante - an open-source science-intensive data profiler written in C++. For Spider, we have evaluated several different options, and in case of Faida we have demonstrated that all our optimization techniques yield results. We also compared our implementations with Metanome - a Java-based data profiler. Overall, we report up to 5x improvement in terms of run time reduction for Spider and up to 8x for Faida.

Related papers

• Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms [0.0]
  We study two algorithms for OD discovery which target different OD axiomatizations - FASTOD and ORDER.<n>We implement these algorithms inside Desbordante - a science-intensive, high-performance, and open-source data profiling tool developed in C++.<n> Experiments have demonstrated a performance improvement of up to 3x obtained by reimplemented versions, and, with the application of our techniques, up to 10x.
  arXiv  Detail & Related papers  (2026-07-26T12:36:31Z)
• 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)
• optimize_anything: A Universal API for Optimizing any Text Parameter [98.42497715725356]
  We show a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs.<n>We show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm.
  arXiv  Detail & Related papers  (2026-05-19T10:18:12Z)
• Relation-aware Ensemble Learning for Knowledge Graph Embedding [68.94900786314666]
  We propose to learn an ensemble by leveraging existing methods in a relation-aware manner. exploring these semantics using relation-aware ensemble leads to a much larger search space than general ensemble methods. We propose a divide-search-combine algorithm RelEns-DSC that searches the relation-wise ensemble weights independently.
  arXiv  Detail & Related papers  (2023-10-13T07:40:12Z)
• Leveraging Data Mining Algorithms to Recommend Source Code Changes [7.959841510571622]
  This paper proposes an automatic method for recommending source code changes using four data mining algorithms. We compare the algorithms in terms of performance (Precision, Recall and F-measure) and execution time. Apriori seems appropriate for large-scale projects, whereas Eclat appears to be suitable for small-scale projects.
  arXiv  Detail & Related papers  (2023-04-29T18:38:23Z)
• Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
  We study techniques to develop efficient learning algorithms for data-driven algorithm design. Our approach involves two novel ingredients -- an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes. We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.
  arXiv  Detail & Related papers  (2022-04-07T17:27:18Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification. We design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-09T02:33:36Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  We present three new algorithms for constructing differentially private synthetic data. The algorithms satisfy differential privacy even in the worst case. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
  arXiv  Detail & Related papers  (2020-07-10T15:46:05Z)

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.