論文の概要: MCPrioQ: A lock-free algorithm for online sparse markov-chains

• arxiv url: http://arxiv.org/abs/2304.14801v1
• Date: Fri, 28 Apr 2023 12:19:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-01 14:19:01.944541
• Title: MCPrioQ: A lock-free algorithm for online sparse markov-chains
• Title（参考訳）: MCPrioQ: オンラインスパースマルコフチェーンのためのロックフリーアルゴリズム
• Authors: Jesper Derehag, {\AA}ke Johansson
• Abstract要約: MCPrioQは、オンラインおよび継続的学習を可能にする、ロックフリーのスパースマーコブチェーンである。 特に、下降確率順で$n$-itemsのルックアップを推奨するシステムに適している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In high performance systems it is sometimes hard to build very large graphs that are efficient both with respect to memory and compute. This paper proposes a data structure called Markov-chain-priority-queue (MCPrioQ), which is a lock-free sparse markov-chain that enables online and continuous learning with time-complexity of $O(1)$ for updates and $O(CDF^{-1}(t))$ inference. MCPrioQ is especially suitable for recommender-systems for lookups of $n$-items in descending probability order. The concurrent updates are achieved using hash-tables and atomic instructions and the lookups are achieved through a novel priority-queue which allows for approximately correct results even during concurrent updates. The approximatly correct and lock-free property is maintained by a read-copy-update scheme, but where the semantics have been slightly updated to allow for swap of elements rather than the traditional pop-insert scheme.
• Abstract（参考訳）: 高性能システムでは、メモリと計算の両方において効率的である非常に大きなグラフを構築するのが難しいことがある。 本稿では,ロックフリーなスパースマルコフチェーンであるmarkov-chain-priority-queue(mcprioq)と呼ばれるデータ構造を提案する。 MCPrioQは、下降確率順で$n$-itemsのルックアップを推奨するシステムに特に適している。 同時更新はハッシュテーブルとアトミック命令を使用して達成され、同時更新時でもほぼ正しい結果が得られる新しい優先度キューによって行われる。 近似的正確かつロックフリーなプロパティは、読み取りコピー更新スキームによって維持されるが、セマンティクスがわずかに更新され、従来のポップ・インサート・スキームよりも要素のスワップが可能になった。

関連論文リスト

• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  重み付き隣接行列の学習可能な関数としてトポロジカルマスクをパラメータ化する方法を示す。 私たちの効率的なマスキングアルゴリズムは、画像およびポイントクラウドデータのタスクに対して、強力なパフォーマンス向上を提供します。
  論文  参考訳（メタデータ） (2024-10-04T14:24:06Z)
• Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recycling [53.58854856174773]
  投機的復号化(英: Speculative decoding)は、推測と検証のパラダイムを通じて推論を加速するアプローチである。 トケンリサイクルは、候補トークンを隣接行列に格納し、幅優先探索アルゴリズムを用いる。 既存の列車不要の手法を30%上回り、訓練方法さえ25%上回っている。
  論文  参考訳（メタデータ） (2024-08-16T12:20:56Z)
• A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention [43.211427581302715]
  大規模言語モデルにおける文脈長を増大させるため,HiP(Hierarchically Pruned Attention)を提案する。 HiPは注意機構の時間的複雑さを$O(T log T)$に減らし、空間的複雑さを$O(T)$に減らし、$T$はシーケンス長である。 HiPは, 劣化を最小限に抑えつつ, プリフィルとデコードの両方のレイテンシとメモリ使用率を著しく低減することを示す。
  論文  参考訳（メタデータ） (2024-06-14T08:32:45Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• Queue Scheduling with Adversarial Bandit Learning [20.606599586119835]
  K$キューからなるワンホップ単一サーバキューシステムについて検討する。 我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。 ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-03T07:17:09Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  自動回帰言語モデルは、回答を生成するデファクト標準として現れています。 これまでの研究は、探索空間を階層構造に分割する方法を探究してきた。 本研究では,検索空間の任意の構造を強制しない代替として,経路内のすべてのngramを識別子として使用することを提案する。
  論文  参考訳（メタデータ） (2022-04-22T10:45:01Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  複合イベント認識(CER)システムは、イベントのリアルタイムストリーム上のパターンを"即時"検出する能力によって、過去20年間に人気が高まっている。 このような現象が実際にCERエンジンによって検出される前に、パターンがいつ発生するかを予測する方法が不足している。 複雑なイベント予測の問題に対処しようとする形式的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-09-01T09:52:31Z)
• Time-aware Large Kernel Convolutions [41.19006428608901]
  Time-Aware Large Kernel (TaLK) Convolutionsは、カーネルの総和の大きさを予測するために学習する新しい適応的畳み込み演算である。 提案手法は, 大規模標準機械翻訳, 抽象要約, 言語モデリングデータセットにおいて評価される。
  論文  参考訳（メタデータ） (2020-02-08T15:30:28Z)

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

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