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

2026-07-26 · Yakov Kuzin, Dmitriy Shcheka, Michael Polyntsov, Kirill Stupakov, Mikhail Firsov, George Chernishev arxiv

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.

📄 PDF Abstract BibTeX arXiv:2607.23632

Code (0)

등록된 구현이 없습니다.

Tasks

Anomaly Detection

Lightning Fast Matching Dependency Discovery with Desbordante

2026-07-12 · Alexey Shlyonskikh, Michael Sinelnikov, Daniil Nikolaev, Yurii Litvinov 외 arxiv

Matching dependency is a generalization of the functional dependency concept, which allows users to apply custom similarity functions for matching individual attributes. Matching dependencies have a wide range of applica…

Entity Resolution

Efficient Discovery of Conditional Dependencies with Desbordante

2026-07-04 · Ivan Kozhukov, Dmitry Fedoseev, Maksim Emelyanov, Artem Smola 외 arxiv

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 con…

Extending Desbordante with Probabilistic Functional Dependency Discovery Support

2026-07-26 · Ilia Barutkin, Maxim Fofanov, Sergey Belokonny, Vladislav Makeev 외 arxiv

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 o…

Anomaly Detection

Scalable Maximal Frequent Episode Mining with Desbordante

2026-07-03 · Maxim Ivanov, Matvei Smirnov, Alisa Strazdina, George Chernishev arxiv

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-appeari…

Desbordante: from benchmarking suite to high-performance science-intensive data profiler (preprint)

2023-01-14 · George Chernishev, Michael Polyntsov, Anton Chizhov, Kirill Stupakov 외

Pioneering data profiling systems such as Metanome and OpenClean brought public attention to science-intensive data profiling. This type of profiling aims to extract complex patterns (primitives) such as functional depen…

Benchmarking