News：ニュース速報

2003年5月28日　11:16 AM 更新

Googleのランキング計算を5倍高速化する手法

スタンフォード大学の研究者らが発表した3つの新手法を組み合わせると、GoogleのランキングアルゴリズムPageRankの計算にかかる時間を大幅に短縮できるという

　スタンフォード大学の研究者らがGoogle検索エンジンのページランキング計算を最大5倍高速化できるとする新技法を開発した。個人の嗜好や関心事に合わせたページランキング計算の実現に向けた研究だという。

　同校によると、この研究は3つの論文にまとめられ、ハンガリーのブダペストで5月20日から24日まで開催のWorld Wide Web Conference（WWW 2003）で発表された。

　Googleが採用するランキングアルゴリズム「PageRank」では、10億のWebぺージのランキング計算に数日を要する。Googleでは現在、30億のページのランク付けと検索が行われている。パーソナライズまたはトピックに合わせたランキングをすれば、計算にさらに数日を要することになるが、これによってユーザーが無関係な検索結果を避けて通るための時間が短縮されるという利点が得られる。

　PageRankの高速化に向けて、スタンフォード大学の研究班は3つのテクニックを開発した。まず第1の論文で紹介されているのは「extrapolation（推論）」方式。これはWebのリンク構造について「真実と異なる」仮定を立てることでPageRankの計算を高速化するという手法。仮定が真実と異なるため、厳密に正確なランキング計算が行われるわけではないが、結果は本来のPageRankアルゴリズムを使って補正することが可能だという。スタンフォード大学の研究者らは、このテクニックを使ってPageRankを現実的な環境下で50％、また若干現実性に劣る環境下では最大300％スピードアップできることを実証済みだとしている。

　第2の論文では、「BlockRank」という手法が解説されている。これは「1つのWebサイト上のページのおよそ80％は、同一サイト上のほかのページにリンクが張られている」というWebのリンク構造の特徴に依存したテクニック。この特徴のため、1つのサイトのPageRankを計算して、それら結果を適切な手法でつなぎ合わせたものを、本来のPageRankのスタート地点として採用できるという。この技法により、PageRank計算は現実的に300％スピードアップできるという。

　第3の論文では、「Adaptive PgeRank」という手法が解説されている。PageRankのプロセスの中でも早期に計算が終わるページに関連した計算の重複を除去する手法で、これにより、PageRank計算が最大50％高速化されるとしている。

　研究者の1人、Sepandar Kamvar氏は、「これらの手法すべてを採用すれば、さらなるスピードアップが可能。われわれの初期の実験では、3手法の併用でPageRankの計算速度を最大5倍高速化できることが分かった。ただ、まだ解決すべき問題がいくつかある。われわれの手法はパーソナライズランキングというより、トピックベースのランキングに近い」としている。パーソナライズランキングでは、その複雑さにより、PageRank計算のさらなるスピードアップが要求される。

関連リンク
Stanford Report

[ITmedia]

Copyright © ITmedia, Inc. All Rights Reserved.