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

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.

Databases (cs.DB); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Performance (cs.PF)

arXiv:2607.23632 [cs.DB]

(or arXiv:2607.23632v1 [cs.DB] for this version)

https://doi.org/10.48550/arXiv.2607.23632 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

35th Conference of Open Innovations Association (FRUCT), Tampere, Finland, 2024, pp. 413-424

https://doi.org/10.23919/FRUCT61870.2024.10516381 Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.