論文の概要: Redundancy-Driven Top-$k$ Functional Dependency Discovery

• arxiv url: http://arxiv.org/abs/2601.10130v1
• Date: Thu, 15 Jan 2026 07:16:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-16 19:43:19.030609
• Title: Redundancy-Driven Top-$k$ Functional Dependency Discovery
• Title（参考訳）: 冗長性駆動型Top-k$関数型依存性発見
• Authors: Xiaolong Wan, Xixian Han,
• Abstract要約: 関数依存(FD)は関係データベースの基本的制約であり、多くのデータ管理タスクに使用される。 ほとんどのFD発見アルゴリズムは、すべての有効な依存関係を見つけるが、2つの問題を引き起こす。 SDP(Selective-Discovery-and-Prune)を提案する。
• 参考スコア（独自算出の注目度）: 5.126404609788543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Functional dependencies (FDs) are basic constraints in relational databases and are used for many data management tasks. Most FD discovery algorithms find all valid dependencies, but this causes two problems. First, the computational cost is prohibitive: computational complexity grows quadratically with the number of tuples and exponentially with the number of attributes, making discovery slow on large-scale and high-dimensional data. Second, the result set can be huge, making it hard to identify useful dependencies. We propose SDP (Selective-Discovery-and-Prune), which discovers the top-$k$ FDs ranked by redundancy count. Redundancy count measures how much duplicated information an FD explains and connects directly to storage overhead and update anomalies. SDP uses an upper bound on redundancy to prune the search space. It is proved that this upper bound is monotone: adding attributes refines partitions and thus decreases the bound. Once the bound falls below the top-$k$ threshold, the entire branch can be skipped. We improve SDP with three optimizations: ordering attributes by partition cardinality, using pairwise statistics in a Partition Cardinality Matrix to tighten bounds, and a global scheduler to explore promising branches first. Experiments on over 40 datasets show that SDP is much faster and uses less memory than exhaustive methods.
• Abstract（参考訳）: 関数依存(FD)は関係データベースの基本的制約であり、多くのデータ管理タスクに使用される。 ほとんどのFD発見アルゴリズムは、すべての有効な依存関係を見つけるが、2つの問題を引き起こす。 計算複雑性はタプルの数で2次的に増加し、属性の数で指数関数的に増加するため、大規模データや高次元データでは発見が遅くなる。 第二に、結果セットは巨大になり、有用な依存関係を特定するのが難しくなります。 SDP(Selective-Discovery-and-Prune)を提案する。 冗長性カウントは、FDが説明し、ストレージオーバーヘッドに直接接続し、異常を更新する重複情報の量を測定する。 SDPは、検索空間をプルークするために冗長性上の上限を使用する。 この上界が単調であることが証明され、属性を追加すると分割が洗練され、したがって境界が減少する。 ひとたびバウンドがトップ$k$のしきい値を下回ると、ブランチ全体がスキップされる。 分割基数による属性の順序付け,分割カーディナリティ行列のペア統計を用いた境界の厳密化,将来性のある分岐を探索するグローバルスケジューラの3つの最適化により,SDPを改善した。 40以上のデータセットの実験では、SDPは徹底的な方法よりもはるかに高速で、メモリ使用量が少ないことが示されている。

関連論文リスト

• Kernel Representation and Similarity Measure for Incomplete Data [55.62595187178638]
  不完全データの類似性を測定することは、Webマイニング、レコメンデーションシステム、ユーザー行動分析において基本的な課題である。 従来のアプローチでは、不完全なデータを破棄するか、事前処理のステップとして計算を実行するかのいずれかであり、情報損失と類似性のバイアスが生じる。 本稿では,カーネルの特徴空間における不完全データ間の類似性を,元の空間における明示的な計算なしで直接計算する,新しい類似度尺度を提案する。
  論文  参考訳（メタデータ） (2025-10-15T09:41:23Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAGは、質問駆動セマンティックグラフ分割と協調サブグラフ検索による制限に対処するマルチエージェントRAGフレームワークである。 革新的なフレームワークは、まずリンク情報のセマンティック分割を作成し、次にタイプ特化知識ベースを使用してマルチエージェントRAGを実現する。 属性対応グラフセグメンテーションは、知識グラフを意味的に一貫性のあるサブグラフに分割し、サブグラフが異なるクエリタイプと整合することを保証する。 階層的なマージモジュールは、論理的検証を通じて、部分グラフ由来の解答間の矛盾を解消する。
  論文  参考訳（メタデータ） (2025-05-20T06:44:34Z)
• LIRA: A Learning-based Query-aware Partition Framework for Large-scale ANN Search [14.354312183838642]
  クエリフェーズでは、クエリの距離ランクに基づいてパーティションを探索し、セントロイドをパーティションする方法が一般的である。 パーティション構築フェーズでは、すべてのパーティションベースのメソッドは、クエリの最も近い隣人を複数のパーティションに分離する境界問題に直面します。 我々はLearnIngベースのqueRy-aware pArtitionフレームワークであるLIRAを提案する。
  論文  参考訳（メタデータ） (2025-03-30T12:03:57Z)
• Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches [12.184984662899868]
  相関凸最適化(SCO)問題を再考する。 DP-SCO(ポリログ因子まで)の最適速度を1つのエポックで達成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-04T18:59:42Z)
• Efficiently Computing Similarities to Private Datasets [19.99000806126529]
  微分プライベートモデルトレーニングの多くの方法は、クエリポイント(公開データや合成データなど)とプライベートデータとの類似性を計算することに依存している。 類似関数$f$と大きな高次元プライベートデータセット$XサブセットmathbbRd$を与えられた場合、任意のクエリ$y$に対して、X f(x,y)$のsum_xを近似した差分プライベート(DP)データ構造を出力する。
  論文  参考訳（メタデータ） (2024-03-13T19:19:19Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。 具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。 これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
  論文  参考訳（メタデータ） (2024-03-06T15:06:11Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。 近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。 ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2023-09-21T21:51:55Z)
• Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
  本稿では,共有並列計算問題に対する新しいアプローチを提案する。 2つの戦略を統一されたフレームワークに組み合わせることで、DPSGDはより良い取引計算フレームワークになります。 深層学習(DRL)問題と深層学習(DRL)問題(アドバンテージアクター - A2C)についてDPSGDにより潜在ゲインを達成できる。
  論文  参考訳（メタデータ） (2022-10-06T13:06:08Z)
• Learning Aggregation Functions [78.47770735205134]
  任意の濃度の集合に対する学習可能なアグリゲータであるLAF(Learning Aggregation Function)を紹介する。 半合成および実データを用いて,LAFが最先端の和(max-)分解アーキテクチャより優れていることを示す実験を報告する。
  論文  参考訳（メタデータ） (2020-12-15T18:28:53Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。 BACCは計算複雑性が低い数値的に安定であることが証明されている。 特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
  論文  参考訳（メタデータ） (2020-09-17T14:23:38Z)
• From Open Set to Closed Set: Supervised Spatial Divide-and-Conquer for Object Counting [84.23313278891568]
  本研究では,空間分割コンカレントネットワーク(SS-DCNet)の概念を導入し,オープンセットカウントをクローズドセット問題に変換する。 SS-DCNetはクローズドセットからしか学べないが、S-DCを介してオープンセットシナリオにうまく一般化できる。 本稿では, 理論解析と玩具データの制御実験を行い, クローズド・セット・モデリングがなぜ意味を持つのかを実証する。
  論文  参考訳（メタデータ） (2020-01-07T04:36:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。