Googleで使われている「PageRank」高速化手法をStanford大学の研究者が発見

■URL
http://www.nsf.gov/od/lpa/news/03/pr0356.htm
http://www.stanford.edu/~sdkamvar/research.html
http://dbpubs.stanford.edu:8090/aux/index-en.html

　米国Stanford大学の研究者グループが、Googleで使われているページランキング手法「PageRank」を大幅に高速化する手法を発見したと発表した。この高速化手法を使うことでPageRankを最大で5倍程度高速化でき、その結果将来的にはGoogleに代表されるサーチエンジンを用途別にカスタマイズするサービスなどに発展する可能性を秘めている。

　この研究を発表したのは、Stanford大学の大学院生Sepander Kamvar氏とTaher Haveliwala氏、数値解析で著名なGene Golub氏とコンピューターサイエンスの教授Christopher Manning氏である。

　Googleで使われているPageRankでは、現在のところ10億ページをランキングするのに数日かかってしまう。Googleは現在30億ページをランキングしているため、これだけのページを個人向けにカスタマイズしたり、トピック別にランキングを行なうとすると、現在の技術では数日間の計算がそれぞれ必要になるため現実的ではない。しかし高速化できるとすると、例えば法律専門、スポーツ専門など用途別のサーチエンジンを簡単に作ることや、探している情報毎にインデックスのランキングを入れ替えられるようになる可能性がある。

　このため、このStanford大学のチームでは数値線形代数に新たなテクニックを持ち込んだ。1つ目は、Webのリンク構造に関して正確ではないが真実にかなり近い推定を行なうことによって、大まかなPageRankを計算する手法。この結果は正確な計算結果に近いため、これに改善を加えることで十分実用的な結果として利用することができる。これにより50％の計算速度向上が可能だという。

　2番目に研究者たちは、Webサイトの80％のページは同じサイトのページにリンクしている事実に気が付いた。この性質を利用することで、PageRankの計算を大幅に簡略化でき、合計300％の速度向上が可能だという。さらにPageRankを計算する際に非常に計算量が多いページと少ないページがあり、この性質を利用して不必要な計算を省くことにより50％の速度向上が可能となった。これら3つの手法を組み合わせることで、最大でPageRankの計算を5倍程度高速化できるという。

　これらの論文は、Stanford大学データベースグループのサーバー上で閲覧することができる。

(2003/5/15)

[Reported by 青木大我 (taiga@scientist.com)]