【文章內(nèi)容簡(jiǎn)介】 了限制響應(yīng)時(shí)間，一旦某個(gè)數(shù)量(現(xiàn)在是40,000)的匹配文檔被找到，搜索器自動(dòng)跳到圖4中的第8步。這意味著有可能返回次優(yōu)的結(jié)果。我們現(xiàn)在在研究新的方法來(lái)解決這個(gè)問題。在過去，我們根據(jù)PageRank值排序，有較好的效果。（Query）。，從每個(gè)單詞的全桶(full barrel)文檔列表開始查找，跳到第4步。，跳到第4步。，然后返回評(píng)分最高的k個(gè)。圖4 Google查詢?cè)u(píng)估Google比典型的搜索引擎維護(hù)了根多的web文檔的信息。每一個(gè)命中列表（hitlist）包含了位置，字體和大小寫信息。而且，我們綜合考慮了超鏈接文本命中和頁(yè)面的PageRank值。把所有的信息綜合成一個(gè)評(píng)分是很困難的。我們?cè)O(shè)計(jì)了評(píng)分函數(shù)保證沒有一個(gè)因素有太大的影響。首先，考慮簡(jiǎn)單的情況——一個(gè)單詞的查詢。為了對(duì)一個(gè)單詞的查詢計(jì)算文檔的分值，Google首先為這個(gè)單詞查看這個(gè)文檔的命中列表。Google將命中分為不同類型（標(biāo)題，錨，URL，普通文本大字體，普通文本小字體，……），每一種類型都有自己的類型權(quán)重值（typeweight）。類型權(quán)重值構(gòu)成一個(gè)由類型尋址（indexed）的向量。Google數(shù)出命中列表中每種類型命中的數(shù)量。每個(gè)數(shù)量轉(zhuǎn)化成一個(gè)數(shù)量權(quán)重（countweight）。數(shù)量權(quán)重開始隨著數(shù)量線性增長(zhǎng)，但是很快停止增長(zhǎng)，以保證單詞命中數(shù)多于某個(gè)數(shù)量之后對(duì)權(quán)重不再有影響。我們通過數(shù)量權(quán)重向量和類型權(quán)重向量的點(diǎn)乘為一個(gè)文檔算出一個(gè)IR分?jǐn)?shù)。最后這個(gè)IR分?jǐn)?shù)與PageRank綜合產(chǎn)生這個(gè)文檔最終的評(píng)分。對(duì)于一個(gè)多詞搜索，情況要更復(fù)雜?，F(xiàn)在，多個(gè)命中列表必須一次掃描完，這樣一個(gè)文檔中較近的命中才能比相距較遠(yuǎn)的命中有更高的評(píng)分。多個(gè)命中列表里的命中結(jié)合起來(lái)才能匹配出相鄰的命中。對(duì)每一個(gè)命中的匹配集(matched set)，會(huì)計(jì)算出一個(gè)接近度。接近度是基于兩個(gè)命中在文檔（或錨文本）中相隔多遠(yuǎn)計(jì)算的，但是被分為10個(gè)等級(jí)從短語(yǔ)匹配到“一點(diǎn)都不近”。不光要為每一種類型的命中計(jì)數(shù)，還要為每一種類型和接近度都計(jì)數(shù)。每一個(gè)類型和接近度的組有一個(gè)類型接近度權(quán)重（typeproxweight）。數(shù)量被轉(zhuǎn)化成數(shù)量權(quán)重。我們通過對(duì)數(shù)量權(quán)重和類型接近度權(quán)重做點(diǎn)乘計(jì)算出IR分值。所有這些數(shù)字和矩陣都會(huì)在特殊的調(diào)試模式下與搜索結(jié)果一起顯示出來(lái)。這些顯示結(jié)果在開發(fā)評(píng)分系統(tǒng)的時(shí)候很有幫助反饋評(píng)分函數(shù)有很多參數(shù)比如類型權(quán)重和類型接近度權(quán)重。找出這些參數(shù)的權(quán)重值簡(jiǎn)直就跟妖術(shù)一樣。為了調(diào)整這些參數(shù)，我們?cè)谒阉饕胬镉幸粋€(gè)用戶反饋機(jī)制。一個(gè)被信任的用戶可以選擇性地評(píng)價(jià)所有的返回結(jié)果。這個(gè)反饋被記錄下來(lái)。然后在我們改變?cè)u(píng)分系統(tǒng)的時(shí)候，我們能看到修改對(duì)之前評(píng)價(jià)過的搜索結(jié)果的影響。盡管這樣并不完美，但是這也給我們一些改變?cè)u(píng)分函數(shù)來(lái)影響搜索結(jié)果的想法。5結(jié)果與表現(xiàn)衡量一個(gè)搜索引擎最重要的標(biāo)準(zhǔn)是其搜索結(jié)果的質(zhì)量。雖然如何做一個(gè)完整的用戶評(píng)估超越了本文的范圍，但是我們?cè)贕oogle身上得到的經(jīng)驗(yàn)，表明它提供結(jié)果，比主要商用搜索引擎對(duì)絕大多數(shù)搜索提供的結(jié)果更好。圖表4表示的Google對(duì)于搜索“”的結(jié)果，作為一個(gè)例子可以說明，對(duì)PageRank, anchor text（關(guān)鍵詞）,和proximity（相似度）的使用。這樣的搜索結(jié)果顯示了Google的特色。搜索結(jié)果被服務(wù)器串聯(lián)在一起。這樣的方法當(dāng)在需要對(duì)結(jié)果集篩選時(shí)非常有用。，有理由相信這個(gè)來(lái)源含有本次該搜索中被期望找到的結(jié)果。當(dāng)前，更不用說正確的結(jié)果。注意，第一個(gè)搜索到的連接沒有標(biāo)題，是因?yàn)樗皇亲ト〉媒Y(jié)果，而是Google基于anchor text決定這個(gè)結(jié)果是查詢所期望得到的好結(jié)果。同樣的，第15號(hào)結(jié)果是一個(gè)電子郵件地址，當(dāng)然這也是基于超鏈接的結(jié)果，而非可抓取得結(jié)果。所有結(jié)果都是合理的高質(zhì)量頁(yè)面，而且最后檢查，沒有壞連接。這主要?dú)w功于他們有很高的PageRank。PageRank的百分比使用紅色條形圖表示。最后，這里的結(jié)果中，沒有只有Bill沒有Clinton或只有Clinton沒有Bill的，這是因?yàn)槲覀冊(cè)陉P(guān)鍵詞出現(xiàn)時(shí)使用了非常重要的proximity。當(dāng)然對(duì)一個(gè)實(shí)際的對(duì)搜索引擎的質(zhì)量測(cè)試應(yīng)該包括廣泛的對(duì)用戶研究或者對(duì)搜索結(jié)果的分析，但是我們沒有時(shí)間做以上析。但是我們邀請(qǐng)讀者在自己測(cè)試Google。除搜索質(zhì)量外，Gooogle被設(shè)計(jì)為能夠消化互聯(lián)網(wǎng)規(guī)模不斷增長(zhǎng)帶來(lái)的效能問題。一方面，使用高效存儲(chǔ)。表一是對(duì)Google的統(tǒng)計(jì)與存儲(chǔ)需求的詳細(xì)分類，由于壓縮后的存儲(chǔ)體積為53GB，為源數(shù)據(jù)的三分之一多一點(diǎn)。就當(dāng)前的硬盤價(jià)格來(lái)說可以為有用資源提供廉價(jià)的相關(guān)存儲(chǔ)設(shè)備。更重要的是，搜索引擎使用的所有數(shù)據(jù)的總合需要相應(yīng)的存儲(chǔ)大約為55GB。此外，大多數(shù)查詢能被要求充分使用短反向索引[short inverted index]，在更好的編碼與壓縮文檔索引后，一個(gè)高質(zhì)量的網(wǎng)絡(luò)搜索引擎可能只需要一臺(tái)有7GB存儲(chǔ)空間的新電腦。這對(duì)搜索引擎的抓取與索引來(lái)說很重要。這樣信息被轉(zhuǎn)化為數(shù)據(jù)的速度以及系統(tǒng)主要部分改變后被測(cè)試的速度都相對(duì)更快。就Google來(lái)說，主要操作包括：抓取，索引和排序。一旦硬盤被填滿、或命名服務(wù)器崩潰，或者其它問題導(dǎo)致系統(tǒng)停止，都很難度量抓取所需要化費(fèi)的時(shí)間。全部花費(fèi)在下載2千6百萬(wàn)個(gè)頁(yè)面[包括錯(cuò)誤頁(yè)面]的時(shí)間大概是9天。但是如果系統(tǒng)運(yùn)行更為流暢，這個(gè)過程還可以更快，最后的1千1百個(gè)頁(yè)面只使用了63個(gè)小時(shí)，平均4百萬(wàn)每天。索引的運(yùn)行速度快于抓取速度的重要原因是我們花費(fèi)了足夠的時(shí)間來(lái)優(yōu)化索引程序，使它不要成為瓶頸。優(yōu)化包括對(duì)本地硬盤上的文檔的索引進(jìn)行大規(guī)模的升級(jí)和替換關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。索引的速度達(dá)到大概54頁(yè)每秒。排序可以完全平行作業(yè)，使用四臺(tái)機(jī)器，整個(gè)處理時(shí)間花費(fèi)近24個(gè)小時(shí)。提高搜索性能并不是本次我們研究的重點(diǎn)。當(dāng)前版本的Google返回多數(shù)查詢結(jié)果的時(shí)間是1到10秒。這個(gè)時(shí)間主要受到硬盤IO以及NFS[網(wǎng)絡(luò)文件系統(tǒng)，當(dāng)硬盤安置到許多機(jī)器上時(shí)使用]的限制。進(jìn)一步說，Google沒有做任何優(yōu)化，例如查詢緩沖區(qū)，常用詞匯子索引，和其它常用的優(yōu)化技術(shù)。我們傾向于通過分布式，硬件，軟件，和算法的改進(jìn)來(lái)提高Google的速度。我們的目標(biāo)是每秒能處理幾百個(gè)請(qǐng)求。表2有幾個(gè)現(xiàn)在版本Google響應(yīng)查詢時(shí)間的例子。它們說明IO緩沖區(qū)對(duì)再次搜索速度的影響。6結(jié)論Google設(shè)計(jì)成可伸縮的搜索引擎。主要目標(biāo)是在快速發(fā)展的World Wide Web上提供高質(zhì)量的搜索結(jié)果。Google應(yīng)用了一些技術(shù)改進(jìn)搜索質(zhì)量包括PageRank，鏈接描述文字，相鄰信息。進(jìn)一步說，Google是一個(gè)收集網(wǎng)頁(yè)，建立索引，執(zhí)行搜索請(qǐng)求的完整的體系結(jié)構(gòu)。未來(lái)的工作大型Web搜索引擎是個(gè)復(fù)雜的系統(tǒng)，還有很多事情要做。我們直接的目標(biāo)是提高搜索效率，覆蓋大約100000000個(gè)網(wǎng)頁(yè)。一些簡(jiǎn)單的改進(jìn)提高了效率包括請(qǐng)求緩沖區(qū)，巧妙地分配磁盤空間，子索引。另一個(gè)需要研究的領(lǐng)域是更新。我們必須有一個(gè)巧妙的算法來(lái)決定哪些舊網(wǎng)頁(yè)需要重新抓取，哪些新網(wǎng)頁(yè)需要被抓取。這個(gè)目標(biāo)已經(jīng)由實(shí)現(xiàn)了。受需求驅(qū)動(dòng)，用代理cache創(chuàng)建搜索數(shù)據(jù)庫(kù)是一個(gè)有前途的研究領(lǐng)域。我們計(jì)劃加一些簡(jiǎn)單的已經(jīng)被商業(yè)搜索引擎支持的特征，例如布爾算術(shù)符號(hào)，否定，填充。然而另外一些應(yīng)用剛剛開始探索，例如相關(guān)反饋，聚類（Google現(xiàn)在支持簡(jiǎn)單的基于主機(jī)名的聚類）。我們還計(jì)劃支持用戶上下文（象用戶地址），結(jié)果摘要。我們正在擴(kuò)大鏈接結(jié)構(gòu)和鏈接文本的應(yīng)用。簡(jiǎn)單的實(shí)驗(yàn)證明，通過增加用戶主頁(yè)的權(quán)重或書簽，PageRank可以個(gè)性化。對(duì)于鏈接文本，我們正在試驗(yàn)用鏈接周圍的文本加入到鏈接文本。Web搜索引擎提供了豐富的研究課題。如此之多以至于我們不能在此一一列舉，因此在不久的將來(lái)，我們希望所做的工作不止本節(jié)提到的。高質(zhì)量搜索當(dāng)今Web搜索引擎用戶所面臨的最大問題是搜索結(jié)果的質(zhì)量。結(jié)果常常是好笑的，并且超出用戶的眼界，他們常?；倚膯蕷饫速M(fèi)了寶貴的時(shí)間。例如，一個(gè)最流行的商業(yè)搜索引擎搜索“Bill Clillton”的結(jié)果是the Bill Clinton Joke of the Day: April 14, 1997。Google的設(shè)計(jì)目標(biāo)是隨著Web的快速發(fā)展提供高質(zhì)量的搜索結(jié)果，容易找到信息。為此，Google大量應(yīng)用超文本信息包括鏈接結(jié)構(gòu)和鏈接文本。Google還用到了相鄰性和字號(hào)信息。評(píng)價(jià)搜索引擎是困難的，我們主觀地發(fā)現(xiàn)Google的搜索質(zhì)量比當(dāng)今商業(yè)搜索引擎高。通過PageRank分析鏈接結(jié)構(gòu)使Google能夠評(píng)價(jià)網(wǎng)頁(yè)的質(zhì)量。用鏈接文本描述鏈接所指向的網(wǎng)頁(yè)有助于搜索引擎返回相關(guān)的結(jié)果（某種程度上提高了質(zhì)量）。最后，利用相鄰性信息大大提高了很多搜索的相關(guān)性。除了搜索質(zhì)量，Google設(shè)計(jì)成可升級(jí)的?？臻g和時(shí)間必須高效，處理整個(gè)Web時(shí)固定的幾個(gè)因素非常重要。實(shí)現(xiàn)Google系統(tǒng)，CPU、訪存、內(nèi)存容量、磁盤尋道時(shí)間、磁盤吞吐量、磁盤容量、網(wǎng)絡(luò)IO都是瓶頸。在一些操作中，已經(jīng)改進(jìn)的Google克服了一些瓶頸。Google的主要數(shù)據(jù)結(jié)構(gòu)能夠有效利用存儲(chǔ)空間。進(jìn)一步，網(wǎng)頁(yè)爬行，索引，排序已經(jīng)足夠建立大部分web索引，共2千四百萬(wàn)個(gè)網(wǎng)頁(yè)，用時(shí)不到一星期。我們希望能在一個(gè)月內(nèi)建立一億網(wǎng)頁(yè)的索引。Google不僅是高質(zhì)量的搜索引擎，它還是研究工具。Google搜集的數(shù)據(jù)已經(jīng)用在許多其它論文中，提交給學(xué)術(shù)會(huì)議和許多其它方式。最近的研究，例如，提出了Web查詢的局限性，不需要網(wǎng)絡(luò)就可以回答。這說明Google不僅是重要的研究工具，而且必不可少，應(yīng)用廣泛。我們希望Google是全世界研究者的資源，帶動(dòng)搜索引擎技術(shù)的更新?lián)Q代。7致謝Scott Hassan and Alan Steremberg評(píng)價(jià)Google的改進(jìn)。他們的才智無(wú)可替代，作者由衷地感謝他們。感謝Hector GarciaMolina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase開發(fā)組的支持和富有深刻見解的討論。最后感謝IBM，Intel，Sun和投資者的慷慨支持，為我們提供設(shè)備。這里所描述的研究是Stanford綜合數(shù)字圖書館計(jì)劃的一部分，由國(guó)家科學(xué)自然基金支持，合作協(xié)議號(hào)IRI9411306。DARPA，NASA，Interva研究，Stanford數(shù)字圖書館計(jì)劃的工業(yè)合作伙伴也為這項(xiàng)合作協(xié)議提供了資金。引用Best of the Web 1994 Navigators Bill Clinton Joke of the Day: April 14, 1997. ~cjburke/clinton/.Bzip2 Homepage Google Search Engine Harvest Mauldin, Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert Interview The Effect of Cellular Phone Use Upon Driver Attention Search Engine Watch RFC 1950 (zlib) ftp://Robots Exclusion Protocol: Web Growth Summary: Yahoo! [Abiteboul 97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory.Delphi,Greece1997.[Bagdikian 97] Ben H. Bagdikian. The Media Monopoly. 5th Edition. Publisher: Beacon, ISBN: 0807061557[Chakrabarti 98] , , , , P. Raghavan and S. Rajagopalan. Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. Seventh International Web Conference (WWW 98).Brisbane,Australia, April 1418, 1998.[Cho 98] Junghoo Cho, Hector GarciaMolina,LawrencePage. Efficient Crawling Through URL Ordering. Seventh International Web Conference (WWW 98).Brisbane,Australia, April 1418, 1998.[Gravano 94] Luis Gravano, Hector GarciaMolina, and A. Tomasic. The Effectiveness of GlOSS for the TextDatabase Discovery Problem. Proc. of the 1994 ACM SIGMOD International Conference On Management Of Data, 1994.[Kleinberg 98] Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc. ACMSIAM Symposium on Discrete Algorithms, 1998.[Marchiori 97] Massimo Marchiori. The Quest for Correct Information on the Web: Hyper