論文の概要: Extended Depth-First Representations of $k^2$-trees

• arxiv url: http://arxiv.org/abs/2607.28136v1
• Date: Thu, 30 Jul 2026 12:45:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.567156
• Title: Extended Depth-First Representations of $k^2$-trees
• Title（参考訳）: 拡張深さ-$k^2$-ツリーの第一表現
• Abstract要約: 本稿では,k2$-treesのメモリローカリティと運用効率に着目した。 そこで我々は,4種類の$k2$-treesの深さ優先表現について提案する:平易な深さ優先レイアウト (EDF-1) ,バランスの取れた親和性表現 (BP) ,圧縮された変種 (CEDF, CBP) である。 我々は,古典的なレベルの$k2$-treesやDFUDSベースの表現に対して,実行時間,ディスク空間,およびピークメモリ使用法を実験的に評価した。
• 参考スコア（独自算出の注目度）: 1.487278256718463
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study static, computation-friendly, lossless compression formats for graphs, focusing on memory locality and operational efficiency of $k^2$-trees. We observe that their traditional level-wise layouts suffer from poor cache performance due to weak locality, especially in operations such as matrix-vector and matrix-matrix operations. To address this limitation, we propose four depth-first representations of $k^2$-trees: a plain depth-first layout (EDF-1), a balanced-parenthesis representation (BP), and their compressed variants (CEDF and CBP). We further introduce a linear-time compression method based on suffix and LCP arrays to identify and compress identical subtrees. We experimentally evaluate the execution time, the disk space, and the peak-memory usage of our approaches against classical level-wise $k^2$-trees and DFUDS-based representations across two real and one synthetic dataset (i.e., Web Graphs, Wikidata, and random adjacency matrices) over the above linear-algebra operations. Results show that our depth-first layouts are competitive and often superior than known approaches: CEDF achieves the best compression in most settings, EDF-1 and CEDF reduce the peak memory usage consistently, and performance varies by workload, with different layouts excelling in different operations and data regimes. Overall, this work demonstrates that depth-first layouts of $k^2$-trees provide a practical and efficient alternative to traditional layouts, improving both compression and computational performance in matrix operations.
• Abstract（参考訳）: 本稿では,グラフの静的,計算にやさしい,ロスレスな圧縮形式について検討し,メモリの局所性と$k^2$-treesの操作効率に着目した。 特に行列ベクトル演算や行列行列行列演算のような演算において,従来の階層構造では局所性が弱いため,キャッシュ性能が低いことが観察された。 この制限に対処するため, プレインディープファーストレイアウト (EDF-1) , 平衡パーシス表現 (BP) , 圧縮変種 (CEDF, CBP) の4つの深さ優先表現を提案する。 さらに、接尾辞とLCP配列に基づく線形時間圧縮手法を導入し、同一のサブツリーを同定・圧縮する。 上記の線形代数演算に対して、2つの実数と1つの合成データセット(Web Graphs, Wikidata, ランダム隣接行列)にまたがる古典的なレベルの$k^2$-treesおよびDFUDSに基づく表現に対する我々のアプローチの実行時間,ディスク空間,およびピークメモリ使用率を実験的に評価した。 CEDFは、ほとんどの設定で最高の圧縮を実現し、EDF-1とCEDFは、ピークメモリの使用を一貫して減らし、性能はワークロードによって異なり、異なる操作やデータ構造で優れたレイアウトを持つ。 全体として、この研究は、$k^2$-treesの深さ優先のレイアウトが従来のレイアウトに代わる実用的で効率的な代替手段となり、行列演算における圧縮と計算性能が向上することを示した。

関連論文リスト

• CLIP-Map: Structured Matrix Mapping for Parameter-Efficient CLIP Compression [70.45437536012015]
  Contrastive Language-Image Pre-Training (CLIP) はコンピュータビジョンタスクに広く応用されている。 CLIPは高いメモリと計算コストに悩まされており、リソース制限されたアプリケーションシナリオの使用を禁止している。 本稿では,新しいCLIP圧縮フレームワークであるCLIP-Mapを提案する。
  論文  参考訳（メタデータ） (2026-02-05T17:25:16Z)
• GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
  一般化空間伝搬ネットワーク(GSPN)は2次自己アテンションを直線走査型伝搬方式に置き換えることでこの問題に対処する。 GSPN-2は、視覚アプリケーションにおけるグローバル空間コンテキストをモデル化するための新しい効率フロンティアを確立する。
  論文  参考訳（メタデータ） (2025-11-28T07:26:45Z)
• FFT-based Dynamic Subspace Selection for Low-Rank Adaptive Optimization of Large Language Models [49.397861654088636]
  低次元空間へのSVD/QRベースの勾配射影を近似する2段階の手順を提案する。 当社の戦略はランタイムの高速化とメモリ使用量の削減を,さまざまなモデルサイズで最大25%削減できることが示されています。
  論文  参考訳（メタデータ） (2025-05-23T14:37:00Z)
• Error Feedback Can Accurately Compress Preconditioners [43.60787513716217]
  ディープ・ネットワークの規模での損失に関する2次情報を活用することは、ディープ・ラーニングのための電流の性能を改善するための主要なアプローチの1つである。 しかし、GGT (Full-Matrix Adagrad) やM-FAC (Matrix-Free Approximate Curvature) のような、正確な完全行列プリコンディショニングのための既存のアプローチは、小規模モデルにも適用した場合に膨大なストレージコストを被る。 本稿では, コンバージェンスを損なうことなく, プリコンディショナーを最大2桁圧縮できる新しい, 効率的なエラーフィードバック手法により, この問題に対処する。
  論文  参考訳（メタデータ） (2023-06-09T17:58:47Z)
• A Generic Network Compression Framework for Sequential Recommender Systems [71.81962915192022]
  シークエンシャルレコメンデーションシステム(SRS)は,ユーザの動的関心を捉え,高品質なレコメンデーションを生成する上で重要な技術となっている。 CpRecと呼ばれる圧縮されたシーケンシャルレコメンデーションフレームワークを提案する。 大規模なアブレーション研究により、提案したCpRecは実世界のSRSデータセットにおいて最大4$sim$8倍の圧縮速度を達成できることを示した。
  論文  参考訳（メタデータ） (2020-04-21T08:40:55Z)

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

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