論文の概要: Fast Discovery of Inclusion Dependencies with Desbordante
- arxiv url: http://arxiv.org/abs/2608.02213v1
- Date: Mon, 03 Aug 2026 13:35:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.578971
- Title: Fast Discovery of Inclusion Dependencies with Desbordante
- Title（参考訳）: Desbordanteによるインクルージョン依存の高速発見
- Abstract要約: 本稿では,スパイダーとファイダの2つのアルゴリズムを効率的に実装する手法について述べる。
本稿では,メモリ消費を同時に削減しつつアルゴリズムを大幅に高速化する,効率的な並列化手法を提案する。
本報告では, スパイダーの実行時間短縮率を最大5倍, ファイダの最大8倍に改善した。
- 参考スコア（独自算出の注目度）: 36.993555985790614
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: 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.
- Abstract（参考訳）: インクルージョン依存は、可能なプライマリキーのキー参照を示すテーブルの属性の間の関係である。
包括的依存関係の自動発見は、学術と工業の両方のコミュニティにとって、関連する問題である。
この問題に対する主な懸念は、計算に高価なタスクであるため、発見プロセスの効率性である。
しかし、既存の研究は、実装の側面を残しながら、アルゴリズム的な側面にのみ対処している。
同時に、エンジニアリングの詳細は、パフォーマンスを達成するためのアルゴリズムと同じくらい、少なくとも重要である。
本稿では,Spider と Faida という2つのアルゴリズムを効率的に実装する手法について述べる。
1つは古典的なアルゴリズムであり、そのアイデアは、他の多くの包摂的依存性発見アルゴリズムの基礎にある。
本稿では,メモリ消費を同時に削減しつつアルゴリズムを大幅に高速化する,効率的な並列化手法を提案する。
2つ目は最先端近似アルゴリズムであり,データバッファリング,SIMD対応実行,ハッシュテーブルの選択と並列化の4種類の最適化を適用することでアプローチする。
この手法を実験的に評価するために、C++で書かれたオープンソースのサイエンス集約データプロファイラであるDesbordanteにこれらのアルゴリズムを実装した。
スパイダーにとって、我々はいくつかの異なる選択肢を評価し、Faidaの場合、最適化手法がすべて結果をもたらすことを示した。
また、JavaベースのデータプロファイラであるMetanomeと実装を比較しました。
総じて,スパイダーの実行時間短縮の点で最大5倍,ファイダでは最大8倍の改善が報告された。
関連論文リスト
- Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms [0.0]
本研究では,FOSTODとORDERの2種類のODの公理化を対象とするOD発見アルゴリズムについて検討した。
Desbordante - C++で開発された、科学集約的で高性能でオープンソースのデータプロファイリングツールである。
実験では、再実装したバージョンによって得られた最大3倍の性能向上を実証し、我々の技術の適用により、最大10倍の性能向上を実現した。
論文 参考訳（メタデータ） (2026-07-26T12:36:31Z) - Lightning Fast Matching Dependency Discovery with Desbordante [0.0]
本稿では,HyMDの最適化手法について述べる。
中でも最も重要なものは,1)新しいサンプリング手法,2)より高速な一般化検索手法,3)依存性の表現の改善である。
実験により、平均的な最先端の実装よりも40倍以上のスピードアップが可能であり、場合によっては170倍以上のスピードアップに達することが実証された。
論文 参考訳（メタデータ） (2026-07-12T13:59:54Z) - optimize_anything: A Universal API for Optimizing any Text Parameter [98.42497715725356]
単一タスク検索をサポートする1つのAIベースの最適化システム、クロスプロブレム転送によるマルチタスク検索、および目に見えない入力への一般化を示す。
LLMに基づく検索によるテキストの最適化は汎用的な問題解決パラダイムであることを示す。
論文 参考訳（メタデータ） (2026-05-19T10:18:12Z) - Relation-aware Ensemble Learning for Knowledge Graph Embedding [68.94900786314666]
我々は,既存の手法を関係性に配慮した方法で活用し,アンサンブルを学習することを提案する。
関係認識アンサンブルを用いてこれらのセマンティクスを探索すると、一般的なアンサンブル法よりもはるかに大きな検索空間が得られる。
本稿では,リレーショナルなアンサンブル重みを独立に検索する分割探索合成アルゴリズムRelEns-DSCを提案する。
論文 参考訳（メタデータ） (2023-10-13T07:40:12Z) - Leveraging Data Mining Algorithms to Recommend Source Code Changes [7.959841510571622]
本論文では、4つのデータマイニングアルゴリズムを用いてソースコード変更を推奨する自動手法を提案する。
性能(精度,リコール,F測定)と実行時間の比較を行った。
Aprioriは大規模プロジェクトに適しているように見えるが、Eclatは小規模プロジェクトに適しているようだ。
論文 参考訳（メタデータ） (2023-04-29T18:38:23Z) - Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。
提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。
本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
論文 参考訳（メタデータ） (2022-04-07T17:27:18Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。
アルゴリズムは最悪の場合でも差分プライバシーを満たす。
現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
論文 参考訳（メタデータ） (2020-07-10T15:46:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。