論文の概要: Online Algorithms for Estimating Change Rates of Web Pages

• arxiv url: http://arxiv.org/abs/2009.08142v2
• Date: Thu, 4 Nov 2021 19:59:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 09:00:12.770615
• Title: Online Algorithms for Estimating Change Rates of Web Pages
• Title（参考訳）: Webページの変化率推定のためのオンラインアルゴリズム
• Authors: Konstantin Avrachenkov, Kishor Patil, Gugan Thoppe
• Abstract要約: 有限帯域の可用性とサーバの制限により、異なるページをクロールする頻度が制限される。 これらは、正確なページ変更率の知識を前提とするか、MLEのような非効率な手法を使って同じことを推定する。 ページ変更率をオンラインで推定するための3つの新しいスキームを提供する。
• 参考スコア（独自算出の注目度）: 2.4923006485141284
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: A search engine maintains local copies of different web pages to provide quick search results. This local cache is kept up-to-date by a web crawler that frequently visits these different pages to track changes in them. Ideally, the local copy should be updated as soon as a page changes on the web. However, finite bandwidth availability and server restrictions limit how frequently different pages can be crawled. This brings forth the following optimization problem: maximize the freshness of the local cache subject to the crawling frequencies being within prescribed bounds. While tractable algorithms do exist to solve this problem, these either assume the knowledge of exact page change rates or use inefficient methods such as MLE for estimating the same. We address this issue here. We provide three novel schemes for online estimation of page change rates, all of which have extremely low running times per iteration. The first is based on the law of large numbers and the second on stochastic approximation. The third is an extension of the second and includes a heavy-ball momentum term. All these schemes only need partial information about the page change process, i.e., they only need to know if the page has changed or not since the last crawled instance. Our main theoretical results concern asymptotic convergence and convergence rates of these three schemes. In fact, our work is the first to show convergence of the original stochastic heavy-ball method when neither the gradient nor the noise variance is uniformly bounded. We also provide some numerical experiments (based on real and synthetic data) to demonstrate the superiority of our proposed estimators over existing ones such as MLE. We emphasize that our algorithms are also readily applicable to the synchronization of databases and network inventory management.
• Abstract（参考訳）: 検索エンジンは、異なるWebページのローカルコピーを保持し、素早く検索結果を提供する。 このローカルキャッシュはwebクローラによって更新され、変更を追跡するためにこれらの異なるページを頻繁に訪問する。 理想的には、web上のページが変わったらすぐにローカルコピーを更新するべきです。 しかしながら、有限帯域幅の可用性とサーバ制限は、異なるページをクロールする頻度を制限する。 ローカルキャッシュの鮮度を最大化する クローリング周波数が所定の境界内にある場合に、ローカルキャッシュの鮮度を最大化する。 抽出可能なアルゴリズムはこの問題を解決するために存在するが、これらは正確なページ変更率の知識を仮定するか、MLEのような非効率な手法を用いて同じことを推定する。 ここでこの問題に対処する。 我々は,ページ変更率をオンラインで推定するための3つの新しい手法を提案する。 第一は、大数の法則と第二は確率近似に基づく。 第3項は第2項の拡張であり、重い球運動量項を含む。 これらのスキームはすべて、ページ変更プロセスに関する部分的な情報のみを必要とする。つまり、最後のクロールされたインスタンス以降、ページが変更されたかどうかを知る必要がある。 我々の主要な理論結果は、これら3つのスキームの漸近収束と収束率に関するものである。 実際、我々の研究は、勾配やノイズ分散が一様有界でない場合、元の確率的重球法の収束を示す最初の方法である。 また,提案する推定器がmleなど既存のものよりも優れていることを示す数値実験(実データおよび合成データに基づく)も実施する。 当社のアルゴリズムはデータベースの同期やネットワークインベントリ管理にも容易に適用可能であることを強調する。

関連論文リスト

• Online Weighted Paging with Unknown Weights [15.525560291268219]
  ページの重みを事前に知るのではなく、むしろ重みサンプルから学習するオンライン重み付きページングのアルゴリズムを提示する。 私たちの仕事は、コストサンプリングを含む他の問題に対して、オンラインアルゴリズムに刺激を与えることができると信じています。
  論文  参考訳（メタデータ） (2024-10-28T17:57:40Z)
• Towards Synchronous Memorizability and Generalizability with Site-Modulated Diffusion Replay for Cross-Site Continual Segmentation [50.70671908078593]
  本稿では,同期記憶可能性と一般化可能性(SMG-Learning)に学ぶ新しい学習パラダイムを提案する。 我々は,過去の地点での記憶可能性を確保するために方位勾配アライメントと,目に見えない地点での一般化性を高めるために任意の勾配アライメントを作成する。 実験により,本手法は,他の最先端手法よりも,記憶可能性と一般性の両方を効果的に向上させることが示された。
  論文  参考訳（メタデータ） (2024-06-26T03:10:57Z)
• Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making [66.27188304203217]
  時間的距離は、計画、制御、強化学習のための多くのアルゴリズムの中心にある。 このような時間的距離を設定内で定義しようとする以前の試みは、重要な制限によって妨げられている。 比較学習によって学習された後継特徴が,三角形の不等式を満たす時間的距離を形成することを示す。
  論文  参考訳（メタデータ） (2024-06-24T19:36:45Z)
• Learning-to-Cache: Accelerating Diffusion Transformer via Layer Caching [56.286064975443026]
  拡散変圧器内の多数の層をキャッシュ機構で計算することで、モデルパラメータを更新しなくても容易に除去できる。 本稿では,拡散変圧器の動的手法でキャッシングを学習するL2C(Learningto-Cache)を提案する。 実験の結果,L2C は DDIM や DPM-r など,キャッシュベースの従来の手法と同等の推論速度で性能を向上することがわかった。
  論文  参考訳（メタデータ） (2024-06-03T18:49:57Z)
• Multi-Agent Reinforcement Learning with Hierarchical Coordination for Emergency Responder Stationing [8.293120269016834]
  緊急対応者管理システム(ERM)は、医療援助の要請を受けたときに対応者を派遣する。 ERMシステムは、任意のギャップをカバーするために予め指定された待機場所間で応答器を積極的に再配置することができる。 プロアクティブな再配置における最先端のアプローチは、空間分解とオンラインモンテカルロ木探索に基づく階層的なアプローチである。 同じ階層的な分解に基づく新しい強化学習(RL)アプローチを導入するが、オンライン検索を学習に置き換える。
  論文  参考訳（メタデータ） (2024-05-21T21:15:45Z)
• BayOTIDE: Bayesian Online Multivariate Time series Imputation with functional decomposition [31.096125530322933]
  交通やエネルギーといった現実のシナリオでは、値やノイズが欠けている巨大な時系列データが広く観測され、不規則にサンプリングされる。 多くの計算法が提案されているが、そのほとんどは局所的な地平線で動作する。 ほとんど全ての手法は、観測は通常のタイムスタンプでサンプリングされ、複雑な不規則なサンプル時系列を扱うことができないと仮定する。
  論文  参考訳（メタデータ） (2023-08-28T21:17:12Z)
• Dynamic Graph Learning Based on Hierarchical Memory for Origin-Destination Demand Prediction [12.72319550363076]
  本稿では,OD要求予測のための動的グラフ表現学習フレームワークを提案する。 特に、階層型メモリ更新器が最初に提案され、各ノードのタイムアウェア表現が維持される。 時間的伝搬機構は、ランダムな時間的経路に沿って隣接ノードの表現を集約する。 目的関数は、最新のノードに従って将来のOD要求を導出するように設計されている。
  論文  参考訳（メタデータ） (2022-05-29T07:52:35Z)
• Continual Test-Time Domain Adaptation [94.51284735268597]
  テスト時ドメイン適応は、ソースデータを使用しずに、ソース事前訓練されたモデルをターゲットドメインに適応することを目的としている。 CoTTAは実装が容易で、市販の事前訓練モデルに簡単に組み込むことができる。
  論文  参考訳（メタデータ） (2022-03-25T11:42:02Z)
• AdamP: Slowing Down the Slowdown for Momentum Optimizers on Scale-invariant Weights [53.8489656709356]
  正規化技術は現代の深層学習の恩恵である。 しかし、運動量を導入することで、スケール不変の重みに対する効果的なステップサイズが急速に小さくなることがしばしば見過ごされる。 本稿では,この2つの材料の組み合わせが,有効ステップサイズと準最適モデル性能の早期劣化につながることを検証した。
  論文  参考訳（メタデータ） (2020-06-15T08:35:15Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Change Rate Estimation and Optimal Freshness in Web Page Crawling [2.4923006485141284]
  有限帯域幅の可用性とサーバの制限は クローリング周波数にいくつかの制約を課します 理想的なクローリングレートは、ローカルキャッシュの鮮度を最大化するものである。 ページ変更率のオンライン推定のための2つの新しいスキームを提供する。
  論文  参考訳（メタデータ） (2020-04-05T11:48:38Z)

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

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