アーカイブ / RAG
誤報と見逃しを含む更新通知から、次に巡回するWebページを選ぶ
Effective crawling with CI signals
Effective crawling with CI signalsの原論文から掲載した図です。細部はクリックして拡大できます。
原論文の図の説明を読む
Figure 1. Histogram of precision and recall for URLs with sitemap signals. The histogram is computed by weighting the pages with their importance.
概要
- 誤報と見逃しを含む更新通知を、前回巡回後の経過時間とともにページごとの巡回価値へ反映する。
- 一定間隔で価値が最大のページを選び、総巡回頻度を一定にする方針を示す。
- 著者らは既存データで通知の不完全さを測定したが、主要な性能比較の数値と条件は確認できた本文の範囲では不明である。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、Effective crawling with CI signalsの仕組み
- 01URLと通知履歴
- 02新しさを推定
- 03巡回価値を比較
- 04URLを再取得
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
Webページの保存済みコピーを閲覧時に新しく保つには、限られた通信量で再取得する順番を決める必要がある。変わっていないページの取得は巡回枠を使い、更新後の取得が遅れると古いコピーを返す。
サイトマップなどの更新通知は判断材料になるが、実際の変更を見逃したり、変更がないのに届いたりする。ページによって通知の質が違っても、閲覧時の新しさを考慮して巡回枠を配ることが課題となる。
手法
各ページについて、前回の巡回からの経過時間と、その後に届いた通知数から、保存済みコピーがまだ新しい確率を推定する。モデルでは通知に誤報と見逃しがある。通知の信頼度を使い、通知１件による新しさの低下を、巡回後に経過した時間に換算して扱う。
続いて、ページの変更率と閲覧要求率も含めて巡回価値を計算し、一定の巡回時刻ごとに価値が最大の１ページを選ぶ。例えば、あるURLに通知が届いても、それだけで取得先を確定せず、他のURLと価値を比べる。ここでの価値は、限られた巡回枠をそのページへ使う判断のための指標である。
新規性
著者らは、誤報と見逃しを含む更新通知を組み込んだモデルで、通信量の上限を守る連続時間の最適巡回方針を導いた。通知の質がページごとに異なることも扱う。
さらに、その方針を基に、一定間隔で各ページの巡回価値を比べる手順を示した。各ページの計算を分けて行い、最後に最大値を選べること、巡回間隔を保ったまま総帯域の変更に適応できることを主張する。
従来手法との違い
Azarらの2018年の方法は、ページの変更率と閲覧要求率を使って巡回を決める。ページごとに固定頻度で巡回する方針に加え、総巡回頻度を一定にする方法も示している。
Kolobovらの2019年の方法は、通知のあるページでは変更を漏れなく正確に知らせると仮定する。本手法は通知の誤報と見逃しを扱い、前回の巡回後に届いた通知を次のページ選択に反映する。著者らはAzarらの方法に対する小さいが有意な改善を報告するが、確認できた本文の範囲では比較条件と改善幅は分からない。
実験結果
著者らが出発点とした既存データには、２週間に集中的に巡回した18,532,314件のURLが含まれる。通知のあるURLは４％だが、ページの重要度で重み付けすると26.4％を占める。著者らが、そのデータで「完全」とされていたサイトマップの通知を測ると、適合率は0.2未満、再現率は0.5未満だった。
適合率は通知が実際の変更に対応する割合、再現率は変更に通知が伴う割合を表す。著者らは半合成データでの実験と、Azarらの方法に対する小さいが有意な改善を報告する。確認できた本文の範囲では、その比較に使った評価指標、数値、条件は示されていない。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：社内検索で参照する公開Webページの再取得順を決める。必要な入力は対象URL、閲覧要求と過去の巡回時刻、巡回で確かめた変更、サイトマップなどの通知履歴、許容する巡回頻度である。
通知源と巡回ログを観測手段とし、内容比較による変更の有無を判定記録として蓄積する。次に選ばれたURLを取得し、確認した内容を検索用データへ反映する。回答時の情報が新しくなるかは、この用途で検証する仮説である。
応用先の候補からNauhに相談できます。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：対象URLを小さく絞り、閲覧要求、巡回時刻と取得内容、更新通知を時刻付きで集める。内容の差をどう変更と数えるかを先に決め、巡回で確かめた変更の有無を判定記録にする。これらの履歴から変更率と通知の誤報・見逃しを推定し、ページごとの巡回価値に反映する。
同じ巡回回数の下で、通知を使わずページ別の頻度で再取得する方法と比べる。閲覧要求時に保存コピーが最新だった割合と、時間帯ごとの巡回回数を測る。通知品質が異なるURL群でも結果を確認し、対象を広げる前に推定値を更新する。
限界と課題
著者らは、通常のモデルで使うページの変更率の推定を研究対象外と明記する。また、変更と閲覧要求を独立した確率過程として扱い、対象URLの集合を固定して議論する。
編集上の検証事項は、実際の履歴にこの仮定が合うか、通知品質が時期によって変わるか、どの内容差分を変更と判定するかである。確認できた本文の範囲では、主要な性能比較の評価指標、数値、実験条件、計算負荷の数値は確認できない。
出典
元のタイトル・要旨を確認する（英語）
A Scalable Crawling Algorithm Utilizing Noisy Change-Indicating Signals
Web refresh crawling is the problem of keeping a cache of web pages fresh, that is, having the most recent copy available when a page is requested, given a limited bandwidth available to the crawler. Under the assumption that the change and request events, resp., to each web page follow independent Poisson processes, the optimal scheduling policy was derived by Azar et al. 2018. In this paper, we study an extension of this problem where side information indicating content changes, such as various types of web pings, for example, signals from sitemaps, content delivery networks, etc., is available. Incorporating such side information into the crawling policy is challenging, because (i) the signals can be noisy with false positive events and with missing change events; and (ii) the crawler should achieve a fair performance over web pages regardless of the quality of the side information, which might differ from web page to web page. We propose a scalable crawling algorithm which (i) uses the noisy side information in an optimal way under mild assumptions; (ii) can be deployed without heavy centralized computation; (iii) is able to crawl web pages at a constant total rate without spikes in the total bandwidth usage over any time interval, and automatically adapt to the new optimal solution when the total bandwidth changes without centralized computation. Experiments clearly demonstrate the versatility of our approach.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-10-01