优化顺序依赖发现算法，提速10倍并降低近3倍内存占用。
Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms
- 重写算法并优化实现，提升计算效率
- 实测性能最高提升10倍，内存降低2.9倍
- 适合数据清洗与数据库优化场景使用
科学密集型数据探查关注数据集中各类模式的发现与验证。本文聚焦于一种关键模式——顺序依赖（OD），即一组列的顺序由另一组列决定。该模式在数据库查询优化、数据清洗、去重和异常检测中具有重要价值。现有方法仅从算法角度出发，忽视了实现层面的性能瓶颈。由于该问题计算开销巨大，实现优化对推动其工业应用至关重要。本文研究了两种针对不同OD公理体系的算法：FASTOD 和 ORDER。我们首先用 C++ 重实现以加速并减少内存消耗，接着分析瓶颈并提出多项改进技术。所有算法均集成至 Desbordante——一个用 C++ 实现的高性能开源科学数据探查工具。实验表明，重实现版本最高可提升性能达 3 倍；结合本文技术后，性能最高提升达 10 倍，内存消耗降低最多 2.9 倍。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。