論文の概要: Space efficient implementation of hypergraph dualization in the D-basis algorithm

• arxiv url: http://arxiv.org/abs/2512.06988v1
• Date: Sun, 07 Dec 2025 20:47:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-09 22:03:54.619149
• Title: Space efficient implementation of hypergraph dualization in the D-basis algorithm
• Title（参考訳）: D-basisアルゴリズムにおけるハイパーグラフ双対化の空間効率向上
• Authors: Skylar Homan, Anoop Krishnadas, Kira Adaricheva,
• Abstract要約: 我々は,Small Spaceと呼ばれる$D$-basisアルゴリズムの新たな実装を提案する。 新しいバージョンでは、唯一の出力は、$D$-basisからの影響の先行する属性の頻度である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a new implementation of the $D$-basis algorithm called the Small Space which considerably reduces the algorithm's memory usage for data analysis applications. The previous implementation delivers the complete set of implications that hold on the set of attributes of an input binary table. In the new version, the only output is the frequencies of attributes that appear in the antecedents of implications from the $D$-basis, with a fixed consequent attribute. Such frequencies, rather than the implications themselves, became the primary focus in analysis of datasets where the $D$-basis has been applied over the last decade. The $D$-basis employs a hypergraph dualization algorithm, and a dualization implementation known as Reverse Search allows for the gradual computation of frequencies without the need for storing all discovered implications. We demonstrate the effectiveness of the Small Space implementation by comparing the runtimes and maximum memory usage of this new version with the current implementation.
• Abstract（参考訳）: 本稿では,データ解析アプリケーションにおけるメモリ使用量を大幅に削減する,Small Spaceと呼ばれる$D$-basisアルゴリズムの実装を提案する。 以前の実装では、入力バイナリテーブルの属性のセットを保持する、完全な意味のセットを提供していました。 新しいバージョンでは、唯一の出力は、$D$-basisの先行する属性の周波数であり、固定された属性を持つ。 このような周波数は、意味ではなく、過去10年間に$D$-basisが適用されたデータセットの分析において、主要な焦点となった。 D$-basisはハイパーグラフの双対化アルゴリズムを採用しており、Reverse Searchと呼ばれる双対化実装は、発見されるすべての含意を格納することなく、周波数の漸進的な計算を可能にする。 本研究では,この新バージョンのランタイムと最大メモリ使用量を比較することで,Small Spaceの実装の有効性を実証する。

関連論文リスト

• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。 提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-31T05:02:33Z)
• Text Anomaly Detection with Simplified Isolation Kernel [58.13924648777626]
  2段階のアプローチでは、事前訓練された大きな言語モデル埋め込みと異常検出を組み合わせている。 大規模言語モデルによって抽出された高次元密度埋め込みは、かなりのメモリ要件と高い計算時間のために課題を提起する。 本稿では,高次元密度埋め込みを低次元スパース表現にマッピングする簡易分離カーネル(SIK)を提案する。
  論文  参考訳（メタデータ） (2025-10-15T06:35:54Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Performance Evaluation and Comparison of a New Regression Algorithm [4.125187280299247]
  新たに提案した回帰アルゴリズムの性能を,従来の4つの機械学習アルゴリズムと比較した。 GitHubリポジトリにソースコードを提供したので、読者は結果の複製を自由にできます。
  論文  参考訳（メタデータ） (2023-06-15T13:01:16Z)
• Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
  我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。 提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
  論文  参考訳（メタデータ） (2023-03-01T18:49:10Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。 我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
  論文  参考訳（メタデータ） (2021-05-18T05:23:53Z)
• Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
  多次元回帰を用いた固定設計の基本問題について検討する。 我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
  論文  参考訳（メタデータ） (2020-03-24T19:39:34Z)

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

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