論文の概要: 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など既存のものよりも優れていることを示す数値実験(実データおよび合成データに基づく)も実施する。
当社のアルゴリズムはデータベースの同期やネットワークインベントリ管理にも容易に適用可能であることを強調する。
関連論文リスト
- BayOTIDE: Bayesian Online Multivariate Time series Imputation with
functional decomposition [32.949946593688864]
交通やエネルギーといった現実のシナリオでは、値やノイズが欠けている巨大な時系列データが広く観測され、不規則にサンプリングされる。
多くの計算法が提案されているが、そのほとんどは局所的な水平線で動作するため、長いシーケンスを適合サイズのパッチのバッチに分割することでモデルが訓練される。
ほとんど全ての手法は、観測は通常のタイムスタンプでサンプリングされ、異なるアプリケーションから生じる複雑な不規則なサンプル時系列を扱うことができないと仮定する。
論文 参考訳(メタデータ) (2023-08-28T21:17:12Z) - Correlating sparse sensing for large-scale traffic speed estimation: A
Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
本稿では,Laplacian enhanced Low-rank tensor (LETC) フレームワークを提案する。
次に,提案したモデルをネットワークワイド・クリグにスケールアップするために,複数の有効な数値手法を用いて効率的な解アルゴリズムを設計する。
論文 参考訳(メタデータ) (2022-10-21T07:25:57Z) - 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) - Accelerating Deep Learning Classification with Error-controlled
Approximate-key Caching [72.50506500576746]
我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。
近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。
我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
論文 参考訳(メタデータ) (2021-12-13T13:49:11Z) - Fast Online Changepoint Detection via Functional Pruning CUSUM
statistics [2.867517731896504]
関数型オンラインCuSUM(FOCuS)は、すべてのウィンドウサイズ、または変更サイズで可能なすべての値に対して、以前のメソッドを同時に実行することと等価である。
FOCuSが平均シナリオの様々な変化にどのように適用できるかを示し、その実用性を実証する。
論文 参考訳(メタデータ) (2021-10-15T17:08:06Z) - ADOM: Accelerated Decentralized Optimization Method for Time-Varying
Networks [124.33353902111939]
本稿では,時間変動ネットワーク上の滑らかかつ強凸分散最適化のための高速化手法である adom を提案する。
ネットワーク構造のみに依存する一定の要因まで、その通信は加速されたNesterovメソッドのそれと同じです。
論文 参考訳(メタデータ) (2021-02-18T09:37:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。