21

Nutch を使用して特定のサイトをクロールする、非常に小さいニッチな検索エンジンを構築しようとしています。一部のサイトはニュース/ブログ サイトです。たとえば、techcrunch.com をクロールし、フロントページまたはメイン ページのいずれかを保存してインデックスに登録すると、数時間以内にそのページのインデックスが古くなります。

Google などの大規模な検索エンジンには、頻繁に更新されるページを非常に頻繁に (1 時間ごとに) 再クロールするアルゴリズムがありますか? それとも、頻繁に更新されるページのスコアが非常に低く、返されないようにするだけですか?

自分のアプリケーションでこれを処理するにはどうすればよいですか?

4

4 に答える 4

30

良い質問。WWWこれは実際に研究コミュニティで活発なトピックです。関連する手法は、再クロール戦略またはページ更新ポリシーと呼ばれます。

私が知っているように、文献で考慮された 3 つの異なる要因があります。

  • 変更頻度(Web ページのコンテンツが更新される頻度)
    • [1]: データの「鮮度」の概念を形式化し、a を使用しpoisson processて Web ページの変化をモデル化します。
    • [2]: 周波数推定器
    • [3]: スケジューリング ポリシーの詳細
  • 関連性(更新されたページ コンテンツが検索結果にどの程度影響するか)
    • [4]: 検索エンジンに問い合わせるユーザーのユーザー エクスペリエンスの品質を最大化する
    • [5]: (ほぼ) 最適なクロール頻度を決定する
  • 情報の寿命 (時間の経過とともに Web ページに現れたり消えたりするコンテンツの断片の寿命。変更頻度とは強く相関していないことが示されています)
    • [6]: 一時的なコンテンツと永続的なコンテンツを区別する

アプリケーションとユーザーにとってどちらの要素がより重要かを判断する必要がある場合があります。詳細については、以下のリファレンスを確認してください。


編集: [2] で言及されている周波数推定器について簡単に説明します。これに基づいて、他の論文で何が役立つかを理解できるはずです。:)

私が以下に指摘した順序に従って、この論文を読んでください。ある程度の確率と統計 101 を知っている限り、理解するのは難しくありません (推定式だけを使用すれば、それほど難しくないかもしれません)。

ステップ 1.セクション6.4 -- Web クローラーへの適用に進んでください。ここで Cho は、Web ページの変更頻度を推定するための 3 つのアプローチを挙げました。

  • 統一ポリシー: クローラーは、毎週 1 回の頻度ですべてのページを再訪問します。
  • 単純なポリシー: 最初の 5 回の訪問で、クローラーは毎週 1 回の頻度で各ページを訪問します。5 回の訪問の後、クローラーは単純な推定器 (セクション 4.1) を使用してページの変更頻度を推定します。
  • 当社のポリシー: クローラーは、提案された推定量 (セクション 4.2) を使用して変更頻度を推定します。

ステップ 2. 単純なポリシー。セクション 4 に進んでください。

直感的には、X/T( X:検出された変更の数、T:監視期間) を変更の推定頻度として使用できます。

サブシーケンスのセクション 4.1 は、この推定がバイアスされている7、一貫性がない8、非効率的9であることを証明しました。

ステップ 3. 改良された推定器。セクション 4.2 に進んでください。新しい推定器は次のようになります。ここに画像の説明を入力

ここで、\bar Xn - X(要素が変更されなかったアクセスの数) でnあり、 はアクセスの数です。したがって、この式を使用して、変更頻度を推定してください。サブセクションの残りの部分では、証明を理解する必要はありません。

ステップ 4. セクション 4.3 とセクション 5 で説明されているいくつかのトリックと便利なテクニックがあり、役に立つかもしれません。セクション 4.3 では、不規則な間隔を処理する方法について説明しました。セクション 5 では、次の質問を解決しました: 要素の最終更新日が利用可能な場合、それを使用して変更頻度を推定するにはどうすればよいですか? 最終変更日を使用した推定量の提案を以下に示します。

ここに画像の説明を入力

論文の図10の後の上記のアルゴリズムの説明は非常に明確です。

ステップ 5. 興味がある場合は、セクション 6 で実験のセットアップと結果を確認できます。

それだけです。自信がついたら、[1] のフレッシュネス ペーパーを試してみてください。


参考文献

[1] http://oak.cs.ucla.edu/~cho/papers/cho-tods03.pdf

[2] http://oak.cs.ucla.edu/~cho/papers/cho-freq.pdf

[3] http://hal.inria.fr/docs/00/07/33/72/PDF/RR-3317.pdf

[4] http://wwwconference.org/proceedings/www2005/docs/p401.pdf

[5] http://www.columbia.edu/~js1353/pubs/wolf-www02.pdf

[6] http://infolab.stanford.edu/~olston/publications/www08.pdf

于 2012-10-24T06:19:48.340 に答える
6

Google のアルゴリズムはほとんどが閉じられており、それがどのように行われるかはわかりません。

有向グラフの概念を使用してクローラーを作成し、再クロール率をページの中心度に基づいて作成しました。Web サイトは、ページをノード、ハイパーリンクをエッジとする有向グラフと見なすことができます。中心性の高いノードは、おそらくより頻繁に更新されるページになります。少なくとも、それは仮定です。

これは、URL とそれらの間のリンクを保存することで実装できます。クロールしてリンクを破棄しないと、サイトごとのグラフが大きくなります。サイトごとのノードごとに (正規化された) イン度とアウト度を計算すると、どのページがより頻繁に再クロールするのが最も興味深いかがわかります。

于 2012-10-25T18:14:10.017 に答える
3

更新頻度に関するフロントページごとの統計を保持するようにしてください。更新の検出は簡単です。ETag/Last-Modifiedを保存​​し、次のリクエストでIf-None-Match/If-Updated-Sinceヘッダーを送り返すだけです。移動平均の更新頻度(たとえば、過去24回のクロール)を維持することで、フロントページの更新頻度をかなり正確に判断できます。

フロントページをクロールした後、次の更新がいつ予定されているかを判断し、その前後に新しいクロールジョブをバケットに配置します(通常、1時間のバケットは、高速と丁寧のバランスが取れています)。1時間ごとに、対応するバケットを取得して、ジョブをジョブキューに追加します。このように、クローラーをいくつでも持つことができ、それでも個々のクロールのスケジュールを制御できます。

于 2012-10-19T19:04:45.897 に答える
2

私はどう考えてもこのトピックの専門家ではありませんが、サイトマップはこの問題を軽減する 1 つの方法です。

最も簡単に言えば、XML サイトマップ (通常はサイトマップと呼ばれ、大文字の S が付く) は、Web サイト上のページのリストです。サイトマップを作成して送信すると、Google の通常のクロール プロセスでは検出できない URL を含め、サイト上のすべてのページを Google が認識できるようになります。さらに、サイトマップを使用して、動画、画像、モバイル、ニュースなど、サイト上の特定の種類のコンテンツに関するメタデータを Google に提供することもできます。

Google はこれを、特にニュース サイトのクロールを支援するために使用します。サイトマップの詳細についてはこちら、Google ニュースとサイトマップの詳細についてはこちらをご覧ください

通常、Sitemaps.xml は Web サイトの robots.txt にあります。たとえば、TechCrunch のサイトマップは

http://techcrunch.com/sitemap.xml

これにより、この問題は定期的に xml を解析することになります。robots.txt で見つからない場合は、いつでもウェブ マスターに連絡して、提供されるかどうかを確認できます。

UPDATE 1 2012 年 10 月 24 日午前 10 時 45 分、

チーム メンバーの 1 人と話をしたところ、この問題をどのように処理しているかについて、追加の洞察を得ることができました。これは単純な問題ではなく、多くの部分的な解決策が必要であることを本当に繰り返したい.

私たちが行っているもう 1 つのことは、特定のドメインの変更についていくつかの「インデックス ページ」を監視することです。たとえば、ニューヨーク・タイムズを見てみましょう。トップ レベル ドメインのインデックス ページを 1 つ作成します。

http://www.nytimes.com/

ページを見ると、World、US、Politics、Business などのサブエリアが追加されていることがわかります。これらすべての追加のインデックス ページを作成します。ビジネスには、Global、DealBook、Markets、Economy などの追加のネストされたインデックス ページがあります。URL に 20 以上のインデックス ページがあることは珍しくありません。インデックスに追加された追加の URL に気付いた場合は、それらをキューに追加してクロールします。

クロールする Web サイトごとに手動でこれを行う必要がある場合があるため、明らかにこれは非常にイライラします。解決策の支払いを検討することをお勧めします。私たちはSuprFeedrを使用しており、非常に満足しています。

また、多くの Web サイトでは、ページをクロールする効果的な方法である RSS を提供しています。ウェブマスターに連絡して、簡単な解決策がないかどうかを確認することをお勧めします.

于 2012-10-24T06:29:14.417 に答える