Fast Discovery of Inclusion Dependencies with Desbordante

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.

Multi-turn RL with Structural and Performance Aware Rewards for CUDA Kernel Generation

Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as a powerful technique to enhance the reasoning capacity of LLMs for optimized code generation. However, existing RLVR approaches primarily rely on outcome-based signals such as correctness and speedup, overlooking performance-critical structural properties of programs that are essential for generating optimized code. In this work, we propose CudaPerf, a reflective RL framework that incorporates both verifiable execution rewards and structural code-aware rewards derived from parallelization features (e.g., memory coalescing, occupancy, Arithmatic Intensity, and synchronization patterns). CudaPerf operates in two stages: (1) an offline pairwise ranking module that learns to distinguish strong and weak program candidates via contrastive comparisons, and (2) an online RL training phase that jointly optimizes for correctness, performance, and structural efficiency through a unified reward signal. To further enhance learning, CudaPerf utilizes iterative refinement using execution feedback enabling progressive improvement of generated candidates. We also introduce a dataset comprising 2.9k C to CUDA and 1k PyTorch to CUDA programs, each paired with diverse input configurations and multiple CUDA implementations encompassing diverse optimization strategies. CudaPerf is evaluated across multiple benchmarks comprising both C to CUDA and PyTorch to CUDA transformations. Empirical findings suggest that CudaPerf significantly outperforms strong baselines, including Qwen-3-32B (for C to CUDA) and CUDA Agent (for PyTorch to CUDA) by achieving up to 5X & 3.32X improvements in speedup, and 17% & 7% improvements in correctness, respectively.

Efficient Discovery of Conditional Dependencies with Desbordante

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.

Scalable Maximal Frequent Episode Mining with Desbordante

Episode mining aims to extract subsequences of events that possess certain distinctive properties and constitute facts valuable to the user. Maximal frequent episode mining concentrates on discovery of frequently-appearing subsequences, which are not included into any other larger frequent subsequence. The state-of-the-art for this problem is the MaxFEM algorithm which enumerates possible subsequences, while applying various pruning techniques to accelerate the search. However, this is a computationally-intensive problem: reducing the minimum number of required subsequence occurrences or increasing the length of the subsequence both substantially raise running time, which limits practical use of MaxFEM. In this paper we describe our efforts in designing a high-performing algorithm for this problem. For this we: 1) develop an efficient C++ implementation of MaxFEM, and 2) devise an efficient technique to parallelizing it. As the result, we propose an improved parallel MaxFEM variant, which we call ParMaxFEM. Additionally, we integrate the improved algorithm into Desbordante - a high-performance, open-source data profiler with deep Python integration that treats patterns as first-class entities and allows users to develop their custom programs that can include discovery and validation of patterns. To evaluate our approach we compare both C++ implementations with the original SPMF implementation. Experiments demonstrated that our reimplemented version provides up to $8\times$ speedup over the SPMF baseline, while our parallelization technique provides up to $35\times$ improvement overall (on 8 cores).