論文の概要: Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms
- arxiv url: http://arxiv.org/abs/2607.23632v1
- Date: Sun, 26 Jul 2026 12:36:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-28 22:34:15.174905
- Title: Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms
- Title（参考訳）: Desbordanteのオーダー: 順序依存探索アルゴリズムの効率的な実装手法
- Abstract要約: 本研究では,FOSTODとORDERの2種類のODの公理化を対象とするOD発見アルゴリズムについて検討した。
Desbordante - C++で開発された、科学集約的で高性能でオープンソースのデータプロファイリングツールである。
実験では、再実装したバージョンによって得られた最大3倍の性能向上を実証し、我々の技術の適用により、最大10倍の性能向上を実現した。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 科学集約的なデータプロファイリングは、データセット内のさまざまなパターンの発見と検証に焦点を当てている。
本研究は、順序依存(OD)というパターンの発見について考察する。
簡単に言うと、ODは列のリストが別の列に従って順序付けられていることを述べています。
データベースクエリの最適化、データのクリーニングと重複解消、異常検出などに使われる。
既存の発見手法は,実装面に焦点をあてることなく,アルゴリズムの観点からのみこの問題にアプローチしている。
同時に、この問題は非常に計算集約的であるため、ODを産業利用に近づけるため、この部分は無視すべきではない。
本稿では,FOSTODとORDERという,異なるOD公理化を対象とするOD発見アルゴリズムについて検討する。
まず、これらのアルゴリズムをC++で再実装して、メモリ消費を高速化し、削減することから始めます。
次にボトルネックを分析し、パフォーマンスをさらに向上するテクニックをいくつか提案する。
Desbordante - C++で開発された,科学集約的で高性能でオープンソースのデータプロファイリングツールである。
実験では、再実装したバージョンによって得られた最大3倍の性能向上を実証し、我々の技術の適用により、最大10倍の性能向上を実現した。
メモリ消費は2.9倍まで低下した。
関連論文リスト
- Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts [41.19401563581682]
非方向エッジ重み付きグラフの最小カット問題は、カットエッジの重み付け和を最小化しながら、ノードの集合を2ブロックに分割するように要求する。
我々の最も高速な正確なアルゴリズムは、問題に対するより良いバウンダリを得るために不正確なアルゴリズムを使用します。
オープンソースパッケージのVieCutで利用可能であり、実世界のインスタンスでは、並列実行時に2.5倍、最大12.9倍の速度で、それまでの最速の解決器を上回っている。
論文 参考訳（メタデータ） (2026-09-07T08:26:05Z) - Fast Discovery of Inclusion Dependencies with Desbordante [36.993555985790614]
本稿では,スパイダーとファイダの2つのアルゴリズムを効率的に実装する手法について述べる。
本稿では,メモリ消費を同時に削減しつつアルゴリズムを大幅に高速化する,効率的な並列化手法を提案する。
本報告では, スパイダーの実行時間短縮率を最大5倍, ファイダの最大8倍に改善した。
論文 参考訳（メタデータ） (2026-08-03T13:35:33Z) - Lightning Fast Matching Dependency Discovery with Desbordante [0.0]
本稿では,HyMDの最適化手法について述べる。
中でも最も重要なものは,1)新しいサンプリング手法,2)より高速な一般化検索手法,3)依存性の表現の改善である。
実験により、平均的な最先端の実装よりも40倍以上のスピードアップが可能であり、場合によっては170倍以上のスピードアップに達することが実証された。
論文 参考訳（メタデータ） (2026-07-12T13:59:54Z) - Efficient Conformance Checking of Rich Data-Aware Declare Specifications (Extended) [49.46686813437884]
一般的なデータ型やデータ条件とリッチな設定で,データを考慮した最適アライメントを計算可能であることを示す。
これは、制御フローとデータ依存関係を扱うために、よく知られた2つのアプローチを慎重に組み合わせることで達成される。
論文 参考訳（メタデータ） (2025-06-30T10:16:21Z) - AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。
具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。
これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
論文 参考訳（メタデータ） (2024-03-06T15:06:11Z) - Decreasing the Computing Time of Bayesian Optimization using
Generalizable Memory Pruning [56.334116591082896]
本稿では,任意のサロゲートモデルと取得関数で使用可能なメモリプルーニングとバウンダリ最適化のラッパーを示す。
BOを高次元または大規模データセット上で実行することは、この時間の複雑さのために難解になる。
すべてのモデル実装はMIT Supercloudの最先端コンピューティングハードウェア上で実行される。
論文 参考訳（メタデータ） (2023-09-08T14:05:56Z) - Improving and Benchmarking Offline Reinforcement Learning Algorithms [87.67996706673674]
この作業は、低レベルの選択とデータセットによって引き起こされるギャップを埋めることを目的としている。
3つの代表アルゴリズムを用いて20の実装選択を実証的に検討する。
CRR+とCQL+の2つの変種がD4RL上で新たな最先端を実現している。
論文 参考訳（メタデータ） (2023-06-01T17:58:46Z) - Leveraging Data Mining Algorithms to Recommend Source Code Changes [7.959841510571622]
本論文では、4つのデータマイニングアルゴリズムを用いてソースコード変更を推奨する自動手法を提案する。
性能(精度,リコール,F測定)と実行時間の比較を行った。
Aprioriは大規模プロジェクトに適しているように見えるが、Eclatは小規模プロジェクトに適しているようだ。
論文 参考訳（メタデータ） (2023-04-29T18:38:23Z) - DPER: Efficient Parameter Estimation for Randomly Missing Data [0.24466725954625884]
本稿では,1クラス・複数クラスのランダムに欠落したデータセットに対して,最大推定値(MLE)を求めるアルゴリズムを提案する。
我々のアルゴリズムは、データを通して複数のイテレーションを必要としないので、他の方法よりも時間のかかることを約束します。
論文 参考訳（メタデータ） (2021-06-06T16:37:48Z) - Learning to Optimize: A Primer and A Benchmark [94.29436694770953]
最適化への学習(L2O)は、機械学習を活用して最適化方法を開発する新しいアプローチです。
この記事では、継続的最適化のためのL2Oの総合的な調査とベンチマークを行う。
論文 参考訳（メタデータ） (2021-03-23T20:46:20Z) - Towards Understanding the Behaviors of Optimal Deep Active Learning
Algorithms [19.65665942630067]
アクティブラーニング(AL)アルゴリズムは、モデルがデータ選択プロセスを導くため、より少ないデータでより良いパフォーマンスを達成できます。
alの最適形状についてはほとんど研究されていないため、研究者たちはモデルがどこが不足しているかを理解するのに役立つだろう。
我々は,この最適オラクルを探索し,いくつかのタスクで解析するシミュレーションアニーリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-29T22:56:42Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。
アルゴリズムは最悪の場合でも差分プライバシーを満たす。
現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
論文 参考訳（メタデータ） (2020-07-10T15:46:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。