Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms

• URL: http://arxiv.org/abs/2607.23632v1
• Date: Sun, 26 Jul 2026 12:36:31 GMT
• Title: Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Science-intensive data profiling focuses on discovery and validation of various patterns in datasets. This study considers discovery of one such pattern - order dependency (OD). Simply put, OD states that some list of columns is ordered according to another one. It is of use for database query optimization, data cleaning and deduplication, anomaly detection, and much more. Existing discovery methods have approached this problem solely from the algorithmic standpoint, without focusing on the implementation side. At the same time, this problem is very computationally intensive, and therefore this part should not be ignored, as it brings ODs closer to industrial use. In this paper, we study two algorithms for OD discovery which target different OD axiomatizations - FASTOD and ORDER. We start by reimplementing these algorithms in C++ in order to speed them up and lower their memory consumption. We then analyze their bottlenecks and propose several techniques which improve their performance even further. To perform evaluation, we have implemented these algorithms inside Desbordante - a science-intensive, high-performance, and open-source data profiling tool developed in C++. Experiments have demonstrated a performance improvement of up to 3x obtained by reimplemented versions, and, with the application of our techniques, up to 10x. Memory consumption has been lowered by up to 2.9x.

Related papers

• Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts [41.19401563581682]
  A minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges.<n>Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem.<n>It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel.
  arXiv  Detail & Related papers  (2026-09-07T08:26:05Z)
• 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)
• 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)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  We show that by efficiently parallelizing existing causal discovery methods, we can scale them to thousands of dimensions. Specifically, we focus on the causal ordering subprocedure in DirectLiNGAM and implement GPU kernels to accelerate it. This allows us to apply DirectLiNGAM to causal inference on large-scale gene expression data with genetic interventions yielding competitive results.
  arXiv  Detail & Related papers  (2024-03-06T15:06:11Z)
• Decreasing the Computing Time of Bayesian Optimization using Generalizable Memory Pruning [56.334116591082896]
  We show a wrapper of memory pruning and bounded optimization capable of being used with any surrogate model and acquisition function. Running BO on high-dimensional or massive data sets becomes intractable due to this time complexity. All model implementations are run on the MIT Supercloud state-of-the-art computing hardware.
  arXiv  Detail & Related papers  (2023-09-08T14:05:56Z)
• Improving and Benchmarking Offline Reinforcement Learning Algorithms [87.67996706673674]
  This work aims to bridge the gaps caused by low-level choices and datasets. We empirically investigate 20 implementation choices using three representative algorithms. We find two variants CRR+ and CQL+ achieving new state-of-the-art on D4RL.
  arXiv  Detail & Related papers  (2023-06-01T17:58:46Z)
• 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)
• DPER: Efficient Parameter Estimation for Randomly Missing Data [0.24466725954625884]
  We propose novel algorithms to find the maximum likelihood estimates (MLEs) for a one-class/multiple-class randomly missing data set. Our algorithms do not require multiple iterations through the data, thus promising to be less time-consuming than other methods.
  arXiv  Detail & Related papers  (2021-06-06T16:37:48Z)
• Learning to Optimize: A Primer and A Benchmark [94.29436694770953]
  Learning to optimize (L2O) is an emerging approach that leverages machine learning to develop optimization methods. This article is poised to be the first comprehensive survey and benchmark of L2O for continuous optimization.
  arXiv  Detail & Related papers  (2021-03-23T20:46:20Z)
• Towards Understanding the Behaviors of Optimal Deep Active Learning Algorithms [19.65665942630067]
  Active learning (AL) algorithms may achieve better performance with fewer data because the model guides the data selection process. There is little study on what the optimal AL looks like, which would help researchers understand where their models fall short. We present a simulated annealing algorithm to search for this optimal oracle and analyze it for several tasks.
  arXiv  Detail & Related papers  (2020-12-29T22:56:42Z)
• 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.