We got a really interesting and very expansive question

とても興味深い質問を

from RobertvH in Munich.

いただきました。

RobertvH wants to know--

「こんにちは、Google のインデックスやフィルタリングの中で

Hi Matt, could you please explain how Google's ranking

ランキングやサイト評価が

and website evaluation process works starting with the

どのように行われているか教えてください。

crawling and analysis of a site, crawling time lines,

例えば、クロールの開始やサイトの解析、 クロールのタイミングや頻度、優先順位に

frequencies, priorities, indexing and filtering

どのように影響を与えるのでしょうか？」

processes within the databases, et cetera?

つまり、Google についてすべてのことを

OK.

教えてください、ということですね？

So that's basically just like, tell me

これはとても広い領域に関係する質問であり

everything about Google.

お答えするには様々な内容に触れる必要があるため、 一言では答えられません。

Right?

私は新人エンジニアの オリエンテーションを担当していますが、

That's a really expansive question.

これらのトピック全体について話をしたら 1 時間以上かかるでしょう。

It covers a lot of different ground.

さらに、それぞれについて細かく話をしたら

And in fact, I have given orientation lectures to

各トピックでも 1 時間以上話すことができるでしょう。

engineers when they come in.

ですので今回は的を絞って

And I can talk for an hour about all those different

どのように Google 検索が動いているか、 その基本についてご説明いたします。

topics, and even talk for an hour about a very small subset

クロールやインデックス、検索結果の表示がどのように行われていて

of those topics.

それらがどのように組み合わされているかについてお話します。

So let me talk for a while and see how much of a feel I can

まず、すばらしい検索エンジンを作るうえで

give you for how the Google infrastructure works, how it

重要な要素は 3 つあります。

all fits together, how our crawling and indexing and

（1） ウェブを広く、深くクロールし

serving pipeline works.

（2） ページをインデックスし

Let's dive right in.

（3） それらのページにランク付けをして

So there's three things that you really want to do well if

検索クエリに対して、最も関連性の高いページを 最初に表示することが必要です。

you want to be the world's best search engine.

実は、意外かもしれませんが

You want to crawl the web comprehensively and deeply.

クロールというのはみなさんが思っているよりも難しいものです。

You want to index those pages.

Google が設立されてまもない頃、私が入社した 2000年頃は

And then you want to rank or serve those pages and return

Web 全体のクロールに 3 か月から 4 か月もかかってしまっていました。

the most relevant ones first.

そしてこれを解決するため、

Crawling is actually more difficult

緊急プロジェクトを結成しなければなりませんでした。

than you might think.

その中で、たどり着いたのが、

Whenever Google started, whenever I joined back in

PageRank をもとに クロールの順番に優先度をつけるという方向性でした。

2000, we didn't manage to crawl the web for something

この方法だと、より高い PageRank を持つサイト、

like three or four months.

つまりはより多くのリンクを獲得し、

And we had to have a war room.

高い評判を得ているサイトが比較的早く発見され、

But a good way to think about the mental model is we

クロールされることになります。

basically take page rank as the primary determinant.

よって PageRank に忠実にクロールすると

And the more page rank you have-- that is, the more

CNN や The New York Times などの

people who link to you and the more reputable those people

PageRank のとても高いサイトがより早くクロールされます。

are-- the more likely it is we're going to discover your

かつてのことを思い返すと

page relatively early in the crawl.

クロールが完了するまでに 30日

In fact, you could imagine crawling in strict page rank

つまり数週間もかかっていました。

order, and you'd get the CNNs of the world and The New York

そしてインデックスに約 1 週間

Times of the world and really very high page rank sites.

データを吐き出すのにまた 1 週間...。

And if you think about how things used to be, we used to

これが、かつて「Google ダンス」と呼ばれた現象の原因でした。

crawl for 30 days.

ユーザーは古いデータを持つデータ センターに当たることもあれば 新しいものに当たることもあり、

So we'd crawl for several weeks.

それによって検索順位が異なるという事態が生じていたのです。

And then we would index for about a week.

今はこうした問題を解決するために 様々な興味深い工夫が行われています。

And then we would push that data out.

たとえば CNN のページを想像してください。

And that would take about a week.

30日もかけてようやくクロールをしたのちに、

And so that was what the Google dance was.

新しい情報やユーザーがよく訪れるような重要な情報を 見つけるために

Sometimes you'd hit one data center that had old data.

もう一度クロールしなくてはいけない、といった状況を 考えてみましょう。

And sometimes you'd hit a data center that had new data.

こうした状況は、多くの場合スマートとは言えないでしょう。

Now there's various interesting tricks

クロールに 30日もかかるのでは

that you can do.

データが古くなってしまいます。

For example, after you've crawled for 30 days, you can

そこで 2003 年頃に Update Fritz といわれる アップデートの一部として

imagine recrawling the high page rank guys so you can see

クロールの方法を変更し、

if there's anything new or important that's hit on the

ユーザーにとって興味深い情報を持った、 極めて重要なウェブサイトのグループを 毎日クロールするようになりました。

CNN home page.

イメージとしてはウェブを一定の数のグループに分け、

But for the most part, this is not fantastic.

その中の一部のグループについて

Right?

毎日クロールして更新する、といったものを想像してください。

Because if you're trying to crawl the web and it takes you

しかしこれではその他の部分は古いままになってしまいます。

30 days, you're going to be out-of-date.

そこで、選ばれたページを高頻度でクロールするのと並行して

So eventually, in 2003, I believe, we switched as part

他の部分も少しずつクロールして更新するようにしました。

of an update called Update Fritz to crawling a fairly

この方法はとてもうまくいきました。

interesting significant chunk of the web every day.

すべてのクロールが終わるのを待たずに

And so if you imagine breaking the web into a certain number

少しずつインデックスを更新していくことが できるようになったからです。

of segments, you could imagine crawling that part of the web

こうした仕組みはさらに進化し

and refreshing it every night.

今ではページに何かアップデートがあれば

And so at any given point, your main base index would

すぐに見つけ出せるようになっており、

only be so out of date.

情報を新鮮な状態にすることができています。

Because then you'd loop back around and you'd refresh that.

また、かつてはメインやベースのインデックス以外に

And that works very, very well.

補足結果や補足インデックスと呼ばれるものも存在しました。

Instead of waiting for everything to finish, you're

こちらのほうはクロールや更新を頻繁に行ってはいませんでしたが

incrementally updating your index.

膨大な情報がありました。

And we've gotten even better over time.

つまり最新のデータとメインのインデックス、そして

So at this point, we can get very, very fresh.

頻繁には更新されませんが大量のデータが格納されている

Any time we see updates, we can usually

補足インデックスが存在しました。

find them very quickly.

以上がクロールの仕組みの概要です。

And in the old days, you would have not just a main or a base

さて、クロールについての説明は完了しました。

index, but you could have what were called supplemental

次はそのデータをインデックス化するプロセスについてです。

results, or the supplemental index.

ウェブ上のあるページについて考えていきましょう。 インデックスでは基本的に情報を単語の語順によって 整理していきます。

And that was something that we wouldn't crawl and refresh

例として「Katy Perry」 という言葉が

quite as often.

クロールされたページの中にあるとします。

But it was a lot more documents.

そのページの中で

And so you could almost imagine having really fresh

Katy と Perry は隣り合って書かれているとします。

content, a layer of our main index, and then more documents

インデックスのプロセスでは

that are not refreshed quite as often, but there's a lot

Katy がどのページにあり

more of them.

Perry がどのページにあるのかを

So that's just a little bit about the crawl and how to

把握する必要があります。

crawl comprehensively.

たとえば

What you do then is you pass things around.

Katy がページ「1」「2」「89」

And you basically say, OK, I have crawled a large fraction

「555」「789」に含まれていて

of the web.

Perry がページ 「2」「8」

And within that web you have, for example, one document.

「73」「555」「1000」に含まれているとします。

And indexing is basically taking things in word order.

インデックスのプロセスでは、

Well, let's just work through an example.

それぞれの単語が含まれているページを

Suppose you say Katy Perry.

単語ごとに並べていきます。

In a document, Katy Perry appears right

この段階で、

next to each other.

それぞれの単語が含まれているページがリスト化されています。

But what you want in an index is which documents does the

では検索ボックスに Katy Perry と

word Katy appear in, and which documents does the word

打ちこんだとします。

Perry appear in?

マッチするページはどれでしょう？

So you might say Katy appears in documents 1, and 2, and 89,

ページ 1 は Katy を含みますが Perry がないので

and 555, and 789.

違います。

And Perry might appear in documents number 2, and 8, and

ページ 2 は Katy も Perry もあるので

73, and 555, and 1,000.

検索結果に表示する候補となります。

And so the whole process of doing the index is reversing,

ページ 8 は Perry はありますが Katy がありません。

so that instead of having the documents in word order, you

89 と 73 も同様の理由で

have the words, and they have it in document order.

候補になりません。

So it's, OK, these are all the documents that a

555 には Katy も Perry も入っています。

word appears in.

789 と 1000 は候補にはなりません。

Now when someone comes to Google and they type in Katy

Google の検索ボックスに

Perry, you want to say, OK, what documents might match

Chicken Little, Britney Spears, Matt Cutts, Katy Perry などのクエリが打ち込まれると

Katy Perry?

Google はそうした言葉をページ内や

Well, document one has Katy, but it doesn't have Perry.

バック リンクのアンカー テキストなどに含む

So it's out.

ページを見つけ出します。

Document number two has both Katy and Perry, so that's a

こうしたページの抽出が終わると

possibility.

次はこれらをランク付けします。

Document eight has Perry but not Katy.

これが厄介です。

89 and 73 are out because they don't have the right

Google は PageRank やその他 200 を超える要素をもとに

combination of words.

ランキングを行い

555 has both Katy and Perry.

信頼できるページを見つけます。

And then these two are also out.

あるページは非常に高い PageRank を持っているため

And so when someone comes to Google and they type in

高い評判を獲得していますが

Chicken Little, Britney Spears, Matt Cutts, Katy

"Perry" という用語が一度使われているのみです。

Perry, whatever it is, we find the documents that we believe

Katy はページ上の

have those words, either on the page or maybe in back

どこか別の離れた箇所にたまたま存在していました。

links, in anchor text pointing to that document.

一方別のページでは Katy と Perry が

Once you've done what's called document selection, you try to

隣り合って表示されていて ユーザーが求めているものと近いことが予想されます。

figure out, how should you rank those?

また評価も高く

And that's really tricky.

多くのバック リンクを受けています。

We use page rank as well as over 200 other factors in our

このような場合 Google では、

rankings to try to say, OK, maybe this document is really

評価の高いページかどうか、 そしてユーザーが入力したクエリとの関連性は高いかという観点から

authoritative.

バランスをとってランク付けをおこないます。

It has a lot of reputation because it has

最も適切なページを見つけ出すための

a lot of page rank.

200 以上の異なるランキングの要素の組み合わせ、

But it only has the word Perry once.

これがいわゆる「秘伝のレシピ」のようなものです。

And it just happens to have the word Katy somewhere else

Google 検索は 1 日に

on the page.

何億回も使用されます。

Whereas here is a document that has the word Katy and

その際 Google はユーザーに最も近い データ センターを見つけるようにしています。

Perry right next to each other, so there's proximity.

そして、ユーザーはたとえば Katy Perry といった 検索クエリを打ち込みます。

And it's got a lot of reputation.

Google はそうしたクエリを何百もの異なるマシンに同時に送り

It's got a lot of links pointing to it.

インデックスしたページのうち、

So we try to balance that off.

各マシンが担当している一部を検索します。

You want to find reputable documents that are also about

そして最も適切だと思われるページを

what the user typed in.

それぞれのマシンが見つけ

And that's kind of the secret sauce, trying to figure out a

その結果を返します。

way to combine those 200 different ranking signals in

では、その中でも最高の結果とはどれになるのでしょう？

order to find the most relevant document.

それはとても難しく、干草の山の中で針を探すようなものです。

So at any given time, hundreds of millions of times a day,

すべてのインデックスの中で検索クエリに

someone comes to Google.

最も適したページとはどれでしょうか？

We try to find the closest data center to them.

ページを選んだあとは ユーザーにわかりやすいスニペットと共に表示します。

They type in something like Katy Perry.

またスニペット内のキーワードを強調表示もします。

We send that query out to hundreds of different machines

そして、これら全てのプロセスを たったの 0.5 秒以下で行っているのです。

all at once, which look through their little tiny

さて YouTube で説明できるのはこれくらいでしょうか。

fraction of the web that we've indexed.

クロールやインデックス

And we find, OK, these are the documents that

0.5 秒以下で検索結果を導き出すための

we think best match.

巨大なデータの並行処理の仕組みなどが

All those machines return their matches.

少しおわかりいただけたかと思います。

And we say, OK, what's the creme de la creme?

Google や Google 検索の仕組み

What's the needle in the haystack?

PageRank については

What's the best page that matches this query across our

多くの記事や論文なども書かれています。

entire index?

しかし、もしあなたがこうしたテーマに興味があるのであれば

And then we take that page and we try to show it with a

[email protected] や

useful snippet.

http://www.google.co.jp/intl/ja/about/jobs/ から求人に応募して

So you show the key words in the context of the document.

直接学んでみるのはいかがでしょうか?

And you get it all back in under half a second.

それではご覧いただきありがとうございました。

So that's probably about as long as we can go on without

straining YouTube.

But that just gives you a little bit of a feel about how

the crawling system works, how we index documents, how things

get returned in under half a second through that massive

parallelization.

I hope that helps.

And if you want to know more, there's a whole bunch of

articles and academic papers about Google, and page rank,

and how Google works.

But you can also apply to--

there's jobs@google.com, I think, or google.com/jobs, if

you're interested in learning a lot more about how search

engines work.

OK.

Thanks very much.