谷歌論文：大規模的超文本網頁搜索引擎的分析
本文是谷歌創始人Sergey和Larry在斯坦福大學計算機系讀博士時的一篇論文。發表于1997年。在網絡中并沒有完整的中文譯本，現將原文和本人翻譯的寥寥幾句和網絡收集的片段(網友xfygx和雷聲大雨點大的無私貢獻)整理和綜合到一起，翻譯時借助了translate.Google.com，因為是技術性的論文，文中有大量的合成的術語和較長的句子，有些進行了意譯而非直譯。
作為Google輝煌的起始，這篇文章非常有紀念價值，但是文中提到的內容因年代久遠，已經和時下最新的技術有了不少差異。但是文中的思想還是有很多借鑒價值。因本人水平有限，對文中內容可能會有理解不當之處，請您查閱英文原版。
大規模的超文本網頁搜索引擎的分析
摘要
在本文中我們討論Google，一個充分利用超文本文件結構進行搜索的大規模搜索引擎的原型。Google可以有效地對網絡資源進行爬行搜索和索引，比目前已經存在的系統有更令人滿意的搜索結果。該原型的數據庫包括2400萬頁面的全文和之間的鏈接，可通過http://google.stanford.edu/訪問。
設計一個搜索引擎是一種具挑戰性的任務。 搜索引擎索索引數以億計的不同類型的網頁并每天給出過千萬的查詢的答案。盡管大型搜索引擎對于網站非常重要，但是已完成的、
對于大型搜索引擎的學術上的研究卻很少。 此外，由于技術上的突飛猛進和網頁的急劇增加，在當前，創建一個搜索引擎和三年前已不可同日而語。本文提供了一種深入的描述，
與 Web增殖快速進展今日創建 Web搜索引擎是三年前很大不同。本文提供了到目前為止，對于我們大型的網頁所搜引擎的深入的描述，這是第一個這樣詳細的公共描述。
除了如何把傳統的搜索技術擴展到前所未有的海量數據，還有新的技術挑戰涉及到了使用超文本中存在的其他附加信息產生更好的搜索結果。本文解決這樣一個問題，如何建立一個可以利用超文本中存在的其他附加信息的實用的大型系統，同時我們也研究一下如何有效處理任何人都能發布他們想發布的包含任何信息的大量自由鏈接的問題。
關鍵字： 互聯網，搜索引擎，文獻檢索，PageRank，Google
1.簡介
(注： 本文由兩個版本--較長的完整版本和一個較短的印刷的版本。 完整版本提供在網絡上和會議的CD-ROM上)。 Web給信息檢索帶來了新的挑戰。Web上的信息量快速增長，同時不斷有毫無經驗的新用戶來體驗Web這門藝術。人們喜歡用超級鏈接來網上沖浪，通常都以象 Yahoo這樣重要的網頁或搜索引擎開始。人工維護的網站列表能有效的覆蓋受歡迎的流行的站點，但是它具有主觀性，建立和維護的代價高，升級慢，不能包括所有深奧的主題?；陉P鍵詞的自動搜索引擎通常返回太多的低質量的匹配。使問題更遭的是，一些廣告為了贏得人們的關注想方設法誤導自動搜索引擎。我們建立了一個大型搜索引擎解決了現有系統中的很多問題。應用超文本結構，提供高質量的查詢結果，我們的系統命名為google，取名自googol的通俗拼法，即10的100次方，這和我們的目標建立一個大型搜索引擎較好的符合。
1.1網絡搜索引擎—升級換代：1994-2000
搜索引擎技術不得不快速升級跟上成倍增長的網站數量。1994年，第一個Web搜索引擎，World Wide Web Worm(WWWW)擁有110，000個網頁和網站可訪問文檔的索引。到1994年11月，頂級的搜索引擎聲稱可以檢索到2萬 (WebCrawler)100萬個網絡文件(來自搜索引擎監視)?？梢灶A見到2000年，可檢索到的網頁將超過10億。同時，搜索引擎的訪問量也會以驚人的速度增長。在1997年的三 四月份，World Wide Web Worm平均每天收到1500個查詢。在1997年11月，Altavista聲稱它每天要處理大約20’百萬個查詢。隨著網絡用戶的增長，可以預見到到2000年，自動搜索引擎每天將處理上億個查詢。我們系統的設計目標要解決許多問題，包括質量和可升級性，引入升級搜索引擎技術，把它升級到如此大量的數據上。
1.2 Google：升級與網絡
建立一個能夠和當今web規模相適應的搜索引擎會面臨許多挑戰。抓網頁技術必須足夠快并且保持是最新的版本。存儲空間必須高效的存儲索引和文檔。索引系統必須能夠高效地處理上百億GB的數據。處理查詢必須快，達到每秒能處理成百上千個查詢
。隨著Web的不斷增長，這些任務變得越來越艱巨。然而硬件的性能和成本也在快速增長，可以部分抵消這些困難。然而，還有幾個值得例外，如磁盤的尋道時間，操作系統的效率。在設計Google的過程中，我們既考慮了網絡的增長速度，又考慮了技術的更新。Google的設計能夠很好的升級處理超大量數據集。它能夠高效地使用存儲空間來存儲索引。優化的數據結構能夠快速有效地存取(請參見4.2節)。進一步，我們希望，相對于所抓取的文本文件和HTML網頁的數量而言，存儲和建立索引的代價盡可能的小(請參閱附錄B)。對于象Google這樣的集中式系統，采取這些措施得到了良好的系統可升級性。
1. 3設計目標
1.3.1 改進搜索質量。
我們的主要目標是提高Web搜索引擎的質量。1994年，有人認為建立全搜索索引就有可能很容易找到任何東西。根據Best of the Web 1994 -- Navigators，“最佳導航服務應更容易找到幾乎任何在網絡上(已經輸入的所有數據)。”。然而1997年的Web就迥然不同。任何最近使用搜索引擎的用戶很容易證實索索引的完整性并不是唯一影響搜索引擎結果的因素。用戶感興趣的搜索結果往往被“垃圾結果”淹沒。實際上，到1997年11月為止，四大商業搜索引擎中只有一個能夠找到它自己(使用自己的搜索自己的名字時返回的前十個結果中有它自己)。導致這一問題的主要原因是文檔的索引數目增加了好幾個數量級，但是用戶能夠看的文檔數卻沒有增加。人們仍然只希望看前面的幾十個搜索結果。因此，當集合增大時，我們就需要高精確度的工具(在返回的前幾十個結果中，相關文檔的數量)。由于是從成千上萬個有點相關的文檔中選出幾十個，實際上，我們希望相關的概念就是指最好的文檔。高精確非常重要，甚至以響應(系統能夠返回的有關文檔的總數)為代價。令人十分樂觀的的是利用超文本鏈接提供的信息有助于改進搜索和其它應用[Marchiori 97] [Spertus 97] [Weiss 96] [Kleinberg 98]。尤其是鏈接結構和鏈接文本，為相關性的判斷和高質量篩選提供了大量的信息。Google既利用了鏈接結構又用到了鏈接文本(請參見2.1和2.2節)。
1.3.2 搜索引擎的學術研究
除了發展迅速，Web越來越商業化。到1993年，只有1.5%的網絡服務是來自.com域名。到1997年，增長超過了60%。同時，搜索引擎從學術領域走進商業。到現在大多數搜索引擎被公司所有，很少發布技術細節。這就導致搜索引擎技術很大程度上仍然是暗箱操作，并傾向做廣告(請參閱附錄A)。對于Google來講我們有一個的主要目標是推動學術領域在此方面的發展和了解。
另一個設計目標是給適合數目的人們一個實用的系統。對我們來說應用十分重要，因為一些研究表明，現代網絡系統中存在大量的有用數據。例如，每天有數千萬個查詢被執行。然而，獲得這些數據卻非常困難，主要因為它們被認為有商業價值。
我們的最終設計目標是構建一個體系結構，可以支持大型 Web數據上的一種新的研究活動。為了支持新研究，Google以壓縮的形式保存了實際所抓到所有的文檔。我們設計Google的主要目標之一就是要建立一個環境使其他研究者能夠很快進入這個領域，處理海量網絡數據，得到滿意的結果，而通過其它方法卻很難得到。系統在短時間內被建立起來，已經有幾篇論文用到了Google建立的數據庫，更多的在起步中。我們的另一個目標是建立一個宇宙空間實驗室似的環境，在這里研究人員甚至學生都可以對我們的海量網絡數據設計或做有趣的實驗。
2.系統功能
Google搜索引擎有兩個重要功能，幫助它產生高精度的搜索結果。首先，應用Web的鏈接結構計算每個網頁的質量等級值，這個等級稱為PageRank，將在98頁詳細描述它。
第二點，Google利用超鏈接改進搜索結果。
2.1 PageRank：帶來網頁排序
網絡的引用(鏈接)圖形是重要的資源， 卻沒有被現有的大多搜索引擎使用。我們建立了一個包含518百萬個超鏈接的圖，它是一個具有重要意義的樣本。這些圖能夠快速地計算網頁的PageRank值，它是一個客觀的標準，較好的符合人們主觀的對一個網頁重要程度的評價，由此對應的是，PageRank值是一個較好的區分通過網絡搜索關鍵字獲得的結果的方法。建立的基礎是通過引用判斷重要性。對于大多數的主題，一個簡單的被限制為網頁標題的文本匹配搜索當使用PageRank區分時得到了極好的結果(從google.stanford.edu可以得到演示)。對于Google主系統中的全文搜索，PageRank也有很大的幫助。
2.1.1PageRank計算的描述：
文獻引用理論應用到Web中，主要由引用或反向鏈接到給定頁來計數。這會反映了該網頁的重要性和質量的近似值。PageRank擴展了這種思想，不平等的計算所有頁面上的鏈接并且通過一個頁面上的所有鏈接。PageRank定義如下:
我們假設頁面T1…Tn指向網頁A(例如，被引用)。參數d是一個設定在0，1之間的制動因子。我們通常設置d為0.85。在下一節有更多關于d的詳情，C(A)定義為網頁A指向其它網頁的鏈接數，網頁A的PageRank值由下式給出：
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
請注意PageRank涵蓋所有網頁的一個概率分布得來，因此所有網頁PageRank和是1。 PageRank或PR(A)可使用一個簡單的迭代算法來計算，相應對應月網頁鏈接矩陣的主特征向量。中等規模的網站計算26萬網頁的 PageRank值要花費幾小時。還有一些技術細節超出了本文論述的范圍。
2.1.2 直覺的解釋
PageRank被看作用戶行為的模型。我們假想一個“隨機上網者”;隨機地給他一個網頁;他漫無目的地命中網頁的鏈接，而從來不點“返回鍵”;最終他覺得煩了，又從另一個隨機的網頁從新開始。隨機訪問一個網頁的可能性就是它的PageRank值。制動因子d是隨機訪問一個網頁煩了的可能性，隨機另選一個網頁。對單個網頁或一組網頁，一個重要的變量加入到制動因子d中。這允許個人可以故意地誤導系統，以得到較高的PageRank值幾乎變成不可能的。我們還有其它的PageRank算法，見98頁。另外的直覺判斷是一個網頁有很多網頁指向它，或者一些PageRank值高的網頁指向它，則這個網頁很重要。 直覺地，在Web中，一個網頁被很多網頁引用，那么這個網頁值得一看。一個網頁被象Yahoo這樣重要的主頁引用即使一次，也值得一看。如果一個網頁的質量不高，或者是死鏈接，象Yahoo這樣的主頁不會鏈向它。PageRank處理了這兩方面因素，并通過網絡鏈接遞歸地傳遞。
2.2鏈接描述文字
我們的搜索引擎對鏈接文本進行了特殊的處理。大多數搜索引擎把鏈接文字和它所鏈向的網頁聯系起來。另外，把它和鏈接所指向的網頁聯系起來。這有幾點好處。第一，通常鏈接描述文字比網頁本身更精確地描述該網頁。第二，鏈接描述文字可能鏈向的文檔不能被文本搜索引擎檢索到， 例如圖像，程序和數據庫。有可能使返回的網頁不能被抓到。注意那抓不到的網頁將會帶來一些問題。在返回給用戶前檢測不了它們的有效性。這種情況搜索引擎可能返回一個根本不存在的網頁，但是有超級鏈接指向它。然而這種結果可以被挑出來的，所以此類的問題很少發生。
鏈接描述文字是對被引用網頁的描述這個思想被用在World Wide Web Worm中，主要因為它有助于搜索非文本信息，能夠用少量的已下載文檔擴大搜索范圍。我們大量應用鏈接描述文字，因為它有助于提高搜索結果的質量。有效地利用鏈接描述文字技術上存在一些困難，因為必須處理大量的數據?，F在我們能抓到24萬個網頁，已經檢索到259萬多個鏈接描述文字。
2.3其它功能
除了PageRank和應用鏈接描述文字外，Google還有其他幾個功能。一,它有所有命中數的位置信息，所以它可以在搜索中廣泛應用鄰近性。第二，Google跟蹤一些可視化外表細節，例如字的字體大小。更大的字的權重要高于其他的。第三，知識庫存儲了原始的全文html網頁。
3相關的工作
網絡檢索研究的歷史簡短。World Wide Web Worm(WWWW)是最早的搜索引擎之一。后來出現了一些用于學術性的搜索引擎，現在它們中的大多數被上市公司擁有。與Web的增長和搜索引擎的重要性相比， 有關當今搜索引擎技術的優秀論文相當少。根據Michael Mauldin(Lycos Inc的首席科學家))，“各種各樣的服務(包括Lycos)非常關注這些數據庫的信息?！彪m然在搜索引擎的某些特點上做了大量工作。具有代表性的工作有，對現有商業搜索引擎的 結果進行傳遞，或建立小型的個性化的搜索引擎。最后有關信息檢索系統的研究很多，尤其在有組織機構集合方面。在下面兩節，我們將討論在信息檢索系統中的哪些領域需要改進以便更好的工作在Web上。
3.1信息檢索
信息檢索系統誕生在幾年前，并發展很好。然而,大多數信息檢索系統的研究針對的是受控制的同質集合 ，例如,主題相關的科學論文或新聞故事。實際上，信息檢索的主要基準，用小規模的、有組織結構的集合作為它們的基準。大型文集基準只有20GB，相比之下，我們抓到的24萬個網頁占147GB。在TREC上工作良好的系統，在Web上卻不一定產生好的結果。例如，標準向量空間模型企圖返回和查詢請求最相近的文檔，把查詢請求和文檔都看作由出現在它們中的詞匯組成的向量。在Web環境下，這種策略常常返回非常短的文檔，這些文檔往往是查詢詞再加幾個字。例如，查詢“Bill Clinton”，返回的網頁只包含“Bill Clinton Sucks”，這是我們從一個主要搜索引擎中看到的。網絡上有些爭議，用戶應該更準確地表達他們想查詢什么，在他們的查詢請求中用更多的詞。我們強烈反對這種觀點。如果用戶提出象“Bill Clinton”這樣的查詢請求，應該得到理想的查詢結果，因為這個主題有許多高質量的信息。像所給的例子，我們認為信息檢索標準需要發展，以便有效地處理Web數據。
3.2有組織結構的集合與網絡的不同點
Web是完全無組織的異構的大量文檔的集合。Web中的文檔無論內在信息還是隱含信息都存在大量的異構性。例如，文檔內部就用了不同的語言(既有人類語言又有程序)，詞匯(
email地址，鏈接，郵政編 碼，電話號碼，產品號)，類型(文本，HTML，PDF，圖像，聲音)，有些甚至是機器創建的文件(log文件，或數據庫的輸出)?？梢詮奈臋n中推斷出
來，但并不包含在文檔中的信息稱為隱含信息。隱含信息包括來源的信譽，更新頻率，質量，訪問量和引用。不但隱含信息的 可能來源各種各樣，而且被檢測的信息也大不相同，相差可達好幾個數量級。例如，一個重要主頁的使用量，象Yahoo每天瀏覽數達到上百萬次，于此相比無名的歷史文章可能十年才被訪問一次。很明顯，搜索引擎對這兩類信息的處理是不同的。 Web與有組織結構集合之間的另外一個明顯區別是，事實上，向Web上傳信息沒有任何限制。靈活利用這點可以發布任何 對搜索引擎影響重大的信息，使路由阻塞，加上為牟利故意操縱搜索引擎，這些已經成為一個嚴重的問題。這些問題還沒有被傳統的封閉的信息檢索系統所提出來。 它關心的是元數據的努力，這在Web搜索引擎中卻不適用，因為網頁中的任何文本都不會向用戶聲稱企圖操縱搜索引擎。甚至有些公司為牟利專門操縱搜索引擎。
4系統分析
首先，我們提供高層次的有關體系結構的討論。然后，詳細描述重要的數據結構。最后，主要應用：抓網頁，索引，搜索將會深度探討。
谷歌論文：大規模的超文本網頁搜索引擎的分析 搜索引擎 Google 好文分享 第1張
圖 1.高層次Google體系結構
4.1Google結構概述
這一節，我們將看看整個系統工作方式的高水平綜述，見圖1。本節不討論應用和數據結構，在后幾節中討論。為了效率大部分Google是用c或c++實現的，既可以在Solaris也可以在Linux上運行。Google系統中，網絡爬蟲(下載網頁)是由幾個分布式crawlers完成的。一個URL服務器負責向crawlers提供URL列表。抓來的網頁交給存儲服務器 storeserver。然后，由存儲服務器壓縮網頁并把它們存到知識庫中。每個網頁都有一個ID，稱作docID，當新URL從網頁中分析出時，就被分配一個docID。由索引器和排序器負責建立索引index function。索引器從知識庫中讀取文檔，對其解壓縮和分析。每個文檔被轉換成一組詞的出現情況，稱作命中hits。Hits紀錄了詞，詞在文檔中的位置，最接近的字號，大小寫。索引器把這些hits分配到一組桶barrel中，產生經過部分排序后的索引。索引器的另一個重要功能是分析網頁中所有的鏈接，將有關的重要信息存在鏈接描述anchors文件中。該文件包含了足夠的信息，可以用來判斷每個鏈接鏈出鏈入節點的信息，和鏈接文本。 URL分解器resolver閱讀鏈接描述anchors文件，并把相對URL轉換成絕對URL，再轉換成docID。為鏈接描述文本編制索引，并與它所 指向的docID關聯起來。同時建立由docID對組成的鏈接數據庫。用于計算所有文檔的PageRank值。用docID分類后的barrels，送給 排序器sorter，再根據wordID進行分類，建立反向索引inverted index。這個操作要恰到好處，以便幾乎不需要暫存空間。排序器還給出docID和偏移量列表，建立反向索引。一個叫DumpLexicon的程序把這 個列表和由索引器產生的字典結合在一起，建立一個新的字典，供搜索器使用。這個搜索器就是利用一個Web服務器，使用由DumpLexicon所生成的字典，利用上述反向索引以及頁面等級PageRank來回答用戶的提問。
4.2 主要數據結構
經過優化的Google數據結構，能夠用較小的代價抓取大量文檔，建立索引和查詢。雖然近幾年CPU和輸入輸出速率迅速提高。磁盤尋道仍然需要10ms。任何時候Google系統的設計都盡可能地避免磁盤尋道。這對數據結構的設計影響很大。
4.2.1 大文件
BigFiles是跨越多個文件系統的虛擬文件，用長度是64位的整型數據尋址。多文件系統之間的空間分配是自動完成的。BigFiles包也處理文件描述符的分配。由于操縱系統不能滿足我們的需要，BigFiles也支持基本的壓縮選項。
4.2.2 知識庫
知識庫包含每個網頁的全部HTML。每個網頁用zlib(見RFC1950)壓縮。 壓縮技術的選擇既要考慮速度又要考慮壓縮率。我們選擇zlib的速度而不是壓縮率很高的bzip。知識庫用bzip的壓縮率接近4：1。而用zlib的壓 縮率是3：1。文檔一個挨著一個的存儲在知識庫中，前綴是docID，長度，URL，見圖2。訪問知識庫不需要其它的數據結構。這有助于數據一致性和升級。用其它數據結構重構系統，我們只需要修改知識庫和crawler錯誤列表文件。
谷歌論文：大規模的超文本網頁搜索引擎的分析 搜索引擎 Google 好文分享 第2張
4.2.3 文檔索引
文檔的索引保持每個文檔有關的信息。 它是固定的寬度 ISAM (索引順序訪問模式)索引。每條記錄包括當前文件狀態，一個指向知識庫的指針，文件校驗和，各種統計表。如果一個文檔已經被抓到，指針指向docinfo文件，該文件的寬度可變，包含了URL和標題。否則指針指向包含這個URL的URL列表。這種設計考慮到簡潔的數據結構，以及在查詢中只需要一個磁盤尋道時間就能夠訪問一條記錄。還有一個文件用于把URL轉換成docID。它是URL校驗和與相應docID的列表，并按照校驗排序。要想知道某個URL的docID，需要計算URL的校驗和，然后在校驗和文件中執行二進制查找，找到它的docID。通過對這個文件進行合并，可以把一批URL轉換成對應的docID。URL分析器用這項技 術把URL轉換成docID。這種成批更新的模式是至關重要的，否則每個鏈接都需要一次查詢，假如用一塊磁盤，322百萬個鏈接的數據集合將 花費一個多月的時間。
4.2.4 辭典
詞典有幾種不同的形式。和以前系統的重要改進是，詞典對內存的要求可以在合理的價格內。當前實現中，一臺256M內存的機器就可以把詞典裝入到內存中。現在的詞典包含14萬詞匯(雖然一些很少用的詞匯沒有加入到詞典中)。它執行分兩部分—詞匯表(串聯在一起，但使用空值隔開)和指針的哈希表的列表的實現。不同的函數詞列表有一些輔助的信息，超出了本文以詳細解釋的范圍。
4.2.5點擊列表
一個命中列表對應著一個單詞在一個文檔中出現的位置、字體和大小寫信息的列表。命中列表占用了正向索引和反向索引的大部分空間，所以怎樣盡可能有效的表示是很重要的。我們考慮了對位置，字體和大小寫信息的多種編碼方式——簡單編碼(3個整數)，壓縮編碼(手工優化分配比特)和霍夫曼編碼(Huffman coding)。命中(hit)的詳情見圖3。
谷歌論文：大規模的超文本網頁搜索引擎的分析 搜索引擎 Google 好文分享 第3張
圖3.正、倒排索引和詞典
我們的壓縮編碼每個命中用到兩個字節(byte)。有兩種命中：特殊命中(fancy hit)和普通命中(plain hit)。特殊命中包括在URL，標題，錨文本和meta標簽上的命中。其他的都是普通命中。一個普通的命中包括一個表示大小寫的比特(bit)，字體大小，和12個bit表示的單詞在文件中的位置(所有比4095大的位置都被標示為4096)。字體在文檔中的相對大小用3個比特表示(實際上只用到7個值，因為111標示一個特殊命中)。一個特殊命中包含一個大小寫比特，字體大小設置為7用來表示它是一個特殊命中，4個比特用來表示特殊命中的類型，8個比特表示位置。對于錨命中，表示位置的8個比特被分成兩部分，4個比特表示在錨文本中的位置，4個比特為錨文本所在docID的哈希(hash)值。由于一個詞并沒有那么多的錨文本，所以短語搜索受到一些限制。我們期望能更新錨命中的存儲方式能讓位置和docID哈希值能有更大的范圍。我們使用在一個文檔中的相對字體大小是因為在搜索時，你并不希望對于內容相同的不同文檔，僅僅因為一個文檔字體比較大而有更高的評級(rank)。
命中列表的長度存在命中的前面。為了節省空間，命中列表的長度在正向索引中與wordID結合，在反向索引中與docID結合。這樣就將長度分別限制在8個比特和5個比特(有一些技巧可以從wordID中借用8個比特)。如果長度超過了這個范圍，會在這些比特中使用轉義碼，在接下來的兩個字節(byte)里才存放真正的長度。
4.2.6 正向索引
正向索引實際上已經部分排序。它被存放在一系列的桶(barrels)里面(我們用了64個)。每個桶保存了一定范圍內的wordID。如果一個文檔包含了屬于某個桶的單詞，它的docID將被記錄在桶里面，后面接著一個wordID的列表和相應的命中列表。這種結構需要一點多余空間，因為存儲了重復的docID，由于桶的數量很小，所以存儲空間的差別很小，但是它能在排序器(sorter)建立最終索引的時候大大節省時間并降低了程序復雜度。更進一步，我們并沒有存儲完整的wordID，而是存儲每個wordID相對于其對應的桶里面最小wordID的差距。這樣我們只用到了24個比特，從而為命中列表長度(hit list length)留出了8個比特。
4.2.7 反向索引
反向索引與正向索引有著相同的桶，但是它們是先經過排序器處理過的。對每一個合法的wordID，詞典包含了一個指向對應的桶的指針。它指向一個docID的列表和相應的命中列表。這個文檔列表顯示了有這個單詞出現的所有文檔。
一個重要的事情是如何對這個文檔列表排序。一個簡單的方法是按照docID排序。在多個單詞的查詢中，這種方法可以快速地完成兩個文檔列表的歸并。另一種方案是按照這個詞在文檔中出現的評分(ranking)排序。這種方式使得單個詞的查詢相當簡單，并且多詞查詢的返回結果也很可能接近開頭。但是，歸并要困難得多。而且，開發也會困難得多，因為每次評分函數變動就需要重新建立整個索引。我們綜合了兩種方案，設計了兩個倒排桶集合——一個集合只包括標題和錨命中，另一個集合包含所有的命中。這樣我們首先檢查第一個桶集合，如果沒有足夠的匹配再檢查那個大一點的。
4.3抓取網頁
運行網絡爬蟲是一項很有挑戰性的任務。這里不光涉及到巧妙的性能和可靠性問題，更重要的，還有社會問題。抓取是一個很脆弱的應用，因為它需要與成百上千各種各樣的web服務器和域名服務器交互，這些都不在系統的控制范圍之內。
為了抓取幾億網頁，Google有一個快速的分布式爬蟲系統。一個單獨的URL服務器(URLserver)為多個爬蟲(crawler,一般是3個)提供URL列表。URL服務器和爬蟲都用Python實現。每個爬蟲同時打開大概300個連接。這樣才能保證足夠快地抓取速度。在高峰時期，系統通過4個爬蟲每秒鐘爬取100個網頁。這大概有600K每秒的數據傳輸。一個主要的性能壓力在DNS查詢。每個爬蟲都維護一個自己的DNS緩存，這樣在它抓取網頁之前就不再需要每次都做DNS查詢。幾百個連接可能處于不同的狀態：查詢DNS，連接主機，發送請求，接受響應。這些因素使得爬蟲成為系統里一個復雜的模塊。它用異步IO來管理事件，用一些隊列來管理頁面抓取的狀態。
事實證明，爬蟲連接了50多萬個服務器，產生了幾千萬條日志信息，會帶來大量的電子郵件和電話。因為很多人在網上，他們并不知道爬蟲是什么，因為這是他們第一次見到。幾乎每天，我們都會收到這樣的電子郵件：“哇，你看了好多我站上的頁面，你覺得怎么樣?”也有很多人并不知道爬蟲禁用協議(robots exclusion protocol)，他們認為可以通過在頁面上聲明“本頁面受版權保護，拒絕索引”就可以保護頁面，不用說，網絡爬蟲很難理解這樣的話。而且，由于涉及到大量的數據，一些意想不到的事情總會發生。比如，我們的系統試圖去抓取一個在線游戲。這導致了游戲中出現大量的垃圾消息!這個問題被證實是很容易解決的。但是往往我們在下載了幾千萬個頁面之后這個問題才被發現。因為網絡頁面和服務器總是在變化中，在爬蟲正式運行在大部分的互聯網站點之前是不可能進行測試的。不變的是，總有一些奇怪的錯誤只會在一個頁面里面出現，并且導致爬蟲崩潰，或者更壞，導致不可預測的或者錯誤的行為。需要訪問大量互聯網站點的系統需要設計得很健壯并且小心地測試。因為大量像爬蟲這樣的系統持續導致問題，所以需要大量的人力專門閱讀電子郵件，處理新出現遇到的問題。
4.4網站索引
解析——任何被設計來解析整個互聯網的解析器都必須處理大量可能的錯誤。從HTML標簽里面的錯別字到一個標簽里面上千字節的0，非ASCII字符，嵌套了幾百層的HTML標簽，還有大量超乎人想象的錯誤和“創意”。為了達到最快的速度，我們沒有使用YACC產生CFG(context free gramma，上下文無關文法)解析器，而是用flex配合它自己的棧生成了一個詞法分析器。開發這樣一個解析器需要大量的工作才能保證它的速度和健壯。
為文檔建立桶索引——每一個文檔解析過后，編碼存入桶里面。每一個單詞被內存里的哈希表——詞典轉化成一個wordID。詞典哈希表新加的內容都被記錄在一個文件里。單詞在被轉化成我wordID的時候，他們在當前文檔中的出現會被翻譯成命中列表，并寫入正排桶(forward barrels)中。建立索引階段的并行操作主要的困難在于詞典需要共享。我們并沒有共享整個詞典，而是在內存里保存一份基本詞典，固定的1千4百萬個單詞，多余的詞寫入一個日志文件。這樣，多個索引器就可以同時運行，最后由一個索引器來處理這個記錄著多余單詞的小日志文件。
排序——為了產生倒排索引，排序器取出各個正排的桶，然后根據wordID排序來產生一個標題和錨命中的倒排桶，和一個全文的倒排桶。每次處理一個桶，所以需要的暫存空間很少。而且，我們簡單地通過用盡可能多的機器運行多個排序器做到排序的并行化，不同的排序器可以同時處理不同的桶。因為桶并不能全部放在主存里面，排序器會根據wordID和docID將它們進一步分割成可以放在內存里面的桶(basket)。接著，排序器將每個桶載入內存，排好序，把內容寫入短的倒排桶和完整的倒排桶。
4.5搜索
搜索的目標是高效地返回高質量的結果。很多大型的商業搜索引擎在效率方面看起來都有很大的進步。所以我們更專注于搜索結果的質量，但是我們相信我們的解決方案只要花一點精力就可以很好的應用到商業的數據上。Google的查詢評估流程如圖4。
為了限制響應時間，一旦某個數量(現在是40,000)的匹配文檔被找到，搜索器自動跳到圖4中的第8步。這意味著有可能返回次優的結果。我們現在在研究新的方法來解決這個問題。在過去，我們根據PageRank值排序，有較好的效果。
1.解析查詢(Query)。
2.把單詞轉化成wordID。
3.從每個單詞的短桶文檔列表開始查找。
4.掃描文檔列表直到有一個文檔匹配了所有的搜索詞語。
5.計算這個文檔對應于查詢的評分。
6.如果我們到達短桶的文檔列表結尾，從每個單詞的全桶(full barrel)文檔列表開始查找，跳到第4步。
7.如果我們沒有到達任何文檔列表的結尾，跳到第4步。
8.根據評分對匹配的文檔排序，然后返回評分最高的k個。
谷歌論文：大規模的超文本網頁搜索引擎的分析 搜索引擎 Google 好文分享 第4張
圖4 Google查詢評估
4.5.1評分系統
Google比典型的搜索引擎維護了根多的web文檔的信息。每一個命中列表(hitlist)包含了位置，字體和大小寫信息。而且，我們綜合考慮了超鏈接文本命中和頁面的PageRank值。把所有的信息綜合成一個評分是很困難的。我們設計了評分函數保證沒有一個因素有太大的影響。首先，考慮簡單的情況——一個單詞的查詢。為了對一個單詞的查詢計算文檔的分值，Google首先為這個單詞查看這個文檔的命中列表。Google將命中分為不同類型(標題，錨，URL，普通文本大字體，普通文本小字體，……)，每一種類型都有自己的類型權重值(type-weight)。類型權重值構成一個由類型尋址(indexed)的向量。Google數出命中列表中每種類型命中的數量。每個數量轉化成一個數量權重(count-weight)。數量權重開始隨著數量線性增長，但是很快停止增長，以保證單詞命中數多于某個數量之后對權重不再有影響。我們通過數量權重向量和類型權重向量的點乘為一個文檔算出一個IR分數。最后這個IR分數與PageRank綜合產生這個文檔最終的評分。
對于一個多詞搜索，情況要更復雜。現在，多個命中列表必須一次掃描完，這樣一個文檔中較近的命中才能比相距較遠的命中有更高的評分。多個命中列表里的命中結合起來才能匹配出相鄰的命中。對每一個命中的匹配集(matched set)，會計算出一個接近度。接近度是基于兩個命中在文檔(或錨文本)中相隔多遠計算的，但是被分為10個等級從短語匹配到“一點都不近”。不光要為每一種類型的命中計數，還要為每一種類型和接近度都計數。每一個類型和接近度的組有一個類型-接近度權重(type-prox-weight)。數量被轉化成數量權重。我們通過對數量權重和類型-接近度權重做點乘計算出IR分值。所有這些數字和矩陣都會在特殊的調試模式下與搜索結果一起顯示出來。這些顯示結果在開發評分系統的時候很有幫助
4.5.2 反饋
評分函數有很多參數比如類型權重和類型-接近度權重。找出這些參數的權重值簡直就跟妖術一樣。為了調整這些參數，我們在搜索引擎里有一個用戶反饋機制。一個被信任的用戶可以選擇性地評價所有的返回結果。這個反饋被記錄下來。然后在我們改變評分系統的時候，我們能看到修改對之前評價過的搜索結果的影響。盡管這樣并不完美，但是這也給我們一些改變評分函數來影響搜索結果的想法。
5結果與表現
衡量一個搜索引擎最重要的標準是其搜索結果的質量。雖然如何做一個完整的用戶評估超越了本文的范圍，但是我們在Google身上得到的經驗，表明它提供結果，比主要商用搜索引擎對絕大多數搜索提供的結果更好。圖表4表示的Google對于搜索“比爾.克林頓”的結果，作為一個例子可以說明，對PageRank, anchor text(關鍵詞),和proximity(相似度)的使用。這樣的搜索結果顯示了Google的特色。搜索結果被服務器串聯在一起。這樣的方法當在需要對結果集篩選時非常有用。很大數量的結果會來自域名whitehouse.gov，有理由相信這個來源含有本次該搜索中被期望找到的結果。當前，絕大多數主要的商用搜索引擎不會返回任何來自whitehouse.gov的結果，更不用說正確的結果。注意，第一個搜索到的連接沒有標題，是因為它不是抓取得結果，而是Google基于anchor text決定這個結果是查詢所期望得到的好結果。同樣的，第15號結果是一個電子郵件地址，當然這也是基于超鏈接的結果，而非可抓取得結果。
所有結果都是合理的高質量頁面，而且最后檢查，沒有壞連接。這主要歸功于他們有很高的PageRank。PageRank的百分比使用紅色條形圖表示。最后，這里的結果中，沒有只有Bill沒有Clinton或只有Clinton沒有Bill的，這是因為我們在關鍵詞出現時使用了非常重要的proximity。當然對一個實際的對搜索引擎的質量測試應該包括廣泛的對用戶研究或者對搜索結果的分析，但是我們沒有時間做以上析。但是我們邀請讀者在http://google.stanford.edu/flp自己測試Google。
5.1存儲需求
除搜索質量外，Gooogle被設計為能夠消化互聯網規模不斷增長帶來的效能問題。一方面，使用高效存儲。表一是對Google的統計與存儲需求的詳細分類，由于壓縮后的存儲體積為53GB，為源數據的三分之一多一點。就當前的硬盤價格來說可以為有用資源提供廉價的相關存儲設備。更重要的是，搜索引擎使用的所有數據的總合需要相應的存儲大約為55GB。此外，大多數查詢能被要求充分使用短反向索引[short inverted index]，在更好的編碼與壓縮文檔索引后，一個高質量的網絡搜索引擎可能只需要一臺有7GB存儲空間的新電腦。
5.2系統性能
這對搜索引擎的抓取與索引來說很重要。這樣信息被轉化為數據的速度以及系統主要部分改變后被測試的速度都相對更快。就Google來說，主要操作包括：抓取，索引和排序。一旦硬盤被填滿、或命名服務器崩潰，或者其它問題導致系統停止，都很難度量抓取所需要化費的時間。全部花費在下載2千6百萬個頁面[包括錯誤頁面]的時間大概是9天。但是如果系統運行更為流暢，這個過程還可以更快，最后的1千1百個頁面只使用了63個小時，平均4百萬每天，每秒48.5頁。索引的運行速度快于抓取速度的重要原因是我們花費了足夠的時間來優化索引程序，使它不要成為瓶頸。優化包括對本地硬盤上的文檔的索引進行大規模的升級和替換關鍵的數據結構。索引的速度達到大概54頁每秒。排序可以完全平行作業，使用四臺機器，整個處理時間花費近24個小時。
5.3搜索性能
提高搜索性能并不是本次我們研究的重點。當前版本的Google返回多數查詢結果的時間是1到10秒。這個時間主要受到硬盤IO以及NFS[網絡文件系統，當硬盤安置到許多機器上時使用]的限制。進一步說，Google沒有做任何優化，例如查詢緩沖區，常用詞匯子索引，和其它常用的優化技術。我們傾向于通過分布式，硬件，軟件，和算法的改進來提高Google的速度。我們的目標是每秒能處理幾百個請求。表2有幾個現在版本Google響應查詢時間的例子。它們說明IO緩沖區對再次搜索速度的影響。
6結論
Google設計成可伸縮的搜索引擎。主要目標是在快速發展的World Wide Web上提供高質量的搜索結果。Google應用了一些技術改進搜索質量包括PageRank，鏈接描述文字，相鄰信
息。進一步說，Google是一個收集網頁，建立索引，執行搜索請求的完整的體系結構。
6.1未來的工作
大 型Web搜索引擎是個復雜的系統，還有很多事情要做。我們直接的目標是提高搜索效率，覆蓋大約100000000個網頁。一些簡單的改進提高了效率包括請 求緩沖區，巧妙地分配
磁盤空間，子索引。另一個需要研究的領域是更新。我們必須有一個巧妙的算法來決定哪些舊網頁需要重新抓取，哪些新網頁需要被抓取。這 個目標已經由實現了。受需求驅動，
用代理cache創建搜索數據庫是一個有前途的研究領域。我們計劃加一些簡單的已經被商業搜索引擎支持的特征，例如布爾 算術符號，否定，填充。然而另外一些應用剛剛開始探
索，例如相關反饋，聚類(Google現在支持簡單的基于主機名的聚類)。我們還計劃支持用戶上下文 (象用戶地址)，結果摘要。我們正在擴大鏈接結構和鏈接文本的應用。簡單
的實驗證明，通過增加用戶主頁的權重或書簽，PageRank可以個性化。對于鏈 接文本，我們正在試驗用鏈接周圍的文本加入到鏈接文本。Web搜索引擎提供了豐富的研究課題。如
此之多以至于我們不能在此一一列舉，因此在不久的將來，我們希望所做的工作不止本節提到的。
6.2高質量搜索
當 今Web搜索引擎用戶所面臨的最大問題是搜索結果的質量。結果常常是好笑的，并且超出用戶的眼界，他們常?；倚膯蕷饫速M了寶貴的時間。例如，一個最流行的商業搜索引擎
搜索“Bill Clillton”的結果是the Bill Clinton Joke of the Day: April 14, 1997。Google的設計目標是隨著Web的快速發展提供高質量的搜索結果，容易找到信息。為此，
Google大量應用超文本信息包括鏈接結構和鏈接 文本。Google還用到了相鄰性和字號信息。評價搜索引擎是困難的，我們主觀地發現Google的搜索質量比當今商業搜索引擎高。通過PageRank分析鏈接結構使Google能夠評價網頁的質量。用鏈接文本描述鏈接所指向的網頁有助于搜索引擎返回相關的結果(某種程度上提高了質量)。最后，利用相鄰性信息大
大提高了很多搜索的相關性。
6.3可升級的體系結構
除 了搜索質量，Google設計成可升級的?？臻g和時間必須高效，處理整個Web時固定的幾個因素非常重要。實現Google系統，CPU、訪存、內存容 量、磁盤尋道時間、磁盤吞吐量
、磁盤容量、網絡IO都是瓶頸。在一些操作中，已經改進的Google克服了一些瓶頸。Google的主要數據結構能夠有效利用存儲空間。進一步，網頁爬行，索引，排序已經足夠建立大部分web索引，共2千四百萬個網頁，用時不到一星期。我們希望能在一個月內建立 一億網頁的索引。
6.4研究工具
Google不僅是高質量的搜索引擎，它還是研究工具。Google搜集的數據已經用在許多其它論文中，提交給學術會議和許多其它方式。最近的研究，例如，提出了Web查詢的局限性
，不需要網絡就可以回答。這說明Google不僅是重要的研究工具，而且必不可少，應用廣泛。我們希望Google是全世界研究者的資源，帶動搜索引擎技術的更新換代。
7致謝
Scott Hassan and Alan Steremberg評價Google的改進。他們的才智無可替代，作者由衷地感謝他們。感謝Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase開發組的支持和富有深刻見解的討論。最后感謝IBM，Intel，Sun和投資者的慷慨支持，為我們提供設備。這里 所描述的研究是Stanford綜合數字圖書館計劃的一部分，由國家科學自然基金支持，合作協議號IRI-9411306。DARPA，NASA，Interva研究，Stanford數字圖書館計劃的工業合作伙伴也為這項合作協議提供了資金。
引用
Best of the Web 1994 -- Navigators http://botw.org/1994/awards/navigators.html
Bill Clinton Joke of the Day: April 14, 1997. http://www.io.com/~cjburke/clinton/970414.html.
Bzip2 Homepage http://www.muraroa.demon.co.uk/
Google Search Engine http://google.stanford.edu/
Harvest http://harvest.transarc.com/
Mauldin, Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert Interview http://www.computer.org/pubs/expert/1997/trends/x1008/mauldin.htm
The Effect of Cellular Phone Use Upon Driver Attention http://www.webfirst.com/aaa/text/cell/cell0toc.htm
Search Engine Watch http://www.searchenginewatch.com/
RFC 1950 (zlib) ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html
Robots Exclusion Protocol: http://info.we**rawler.com/mak/projects/robots/exclusion.htm
Web Growth Summary: http://www.mit.edu/people/mkgray/net/web-growth-summary.html
Yahoo! http://www.yahoo.com/
[Abiteboul 97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory. Delphi, Greece 1997.
[Bagdikian 97] Ben H. Bagdikian. The Media Monopoly. 5th Edition. Publisher: Beacon, ISBN: 0807061557
[Chakrabarti 98] S.Chakrabarti, B.Dom, D.Gibson, J.Kleinberg, P. Raghavan and S. Rajagopalan. Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998.
[Cho 98] Junghoo Cho, Hector Garcia-Molina, Lawrence Page. Efficient Crawling Through URL Ordering. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998.
[Gravano 94] Luis Gravano, Hector Garcia-Molina, and A. Tomasic. The Effectiveness of GlOSS for the Text-Database 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. ACM-SIAM Symposium on Discrete Algorithms, 1998.
[Marchiori 97] Massimo Marchiori. The Quest for Correct Information on the Web: Hyper Search Engines. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997.
[McBryan 94] Oliver A. McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN, Geneva (Switzerland), May 25-26-27 1994. http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps
[Page 98] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Manuscript in progress. http://google.stanford.edu/~backrub/pageranksub.ps
[Pinkerton 94] Brian Pinkerton, Finding What People Want: Experiences with the WebCrawler. The Second International WWW Conference Chicago, USA, October 17-20, 1994. http://info.we**rawler.com/bp/WWW94.html
[Spertus 97] Ellen Spertus. ParaSite: Mining Structural Information on the Web. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997.
[TREC 96] Proceedings of the fifth Text REtrieval Conference (TREC-5). Gaithersburg, Maryland, November 20-22, 1996. Publisher: Department of Commerce, National Institute of Standards and Technology. Editors: D. K. Harman and E. M. Voorhees. Full text at: http://trec.nist.gov/
[Witten 94] Ian H Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. New York: Van Nostrand Reinhold, 1994.
[Weiss 96] Ron Weiss, Bienvenido Velez, Mark A. Sheldon, Chanathip Manprempre, Peter Szilagyi, Andrzej Duda, and David K. Gifford. HyPursuit: A Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering. Proceedings of the 7th ACM Conference on Hypertext. New York, 1996.
個人簡歷
谷歌論文：大規模的超文本網頁搜索引擎的分析 搜索引擎 Google 好文分享 第5張
Sergey Brin于1993年獲得美國馬蘭里大學帕克分校數學與計算機專業理學學士學位。他于1995年獲得理科碩士成為斯坦福大學計算機科學博士候選人。他是國家科學基礎研究生獎學金的獲得者。他的的研究領域包括搜索引擎、從非結構化來源提取信息以及對大型文本數據和科學資料進行數據挖掘。
Lawrence Page生于密歇根州東部的蘭辛市并于1995年獲得了密歇根大學計算機工程的工學學士學位。他目前是斯坦福大學計算機科學博士候選人。他的一些研究方向包括web鏈接結構、人機交互、搜索引擎、可擴展性的信息訪問接口,個人數據挖掘方法。
8附錄A廣告及形形色色的動機
目前,商業搜索引擎主要的營業模式是廣告。廣告業務模式的目標并不總是為用戶提供高質量的搜索。例如,在我們的搜索引擎的原型中名列前茅的結果關于手機的是”使用手機對駕駛員的注意力的影響”,一個研究作了較為詳細的解釋了在駕駛時關于使用手機交談的的干擾和風險。這個查詢結果排名如此之高,因為根據PageRank算法它在網絡上被引用的近似值判定了它是十分重要。很明顯，這對于給手機做廣告的廣告商賺錢的搜索引擎來說比較困難，因為我們的系統返回的那些支付了廣告費的頁面。我們認為廣告資助的搜索引擎會偏向的廣告商和遠離消費者的需求，因為即使對于專家來說評估搜索引擎也是很困難的，因為搜索引擎的偏向是特別狡猾的。
一個典型的例子是OpenText搜索引擎,據報道，它向公司出售使特定的查詢在搜索結果列表前面的權利。這種類型的偏向比做廣告更加陰險，因為這將導致誰都不清楚排名是有價值的還是愿意付費的那些。這種商業模式導致了恐慌和OpenText搜索引擎的終結。但市場可以接納較低程度的偏向。比如，搜索引擎可以在那些“友好”的公司的查詢結果中添加一個因子并從其競爭對手中減少因子。這種類型的偏見是非常難以被發現,但仍能有顯著影響市場。廣告收益的誘惑經常導致低質量的搜索結果。例如，我們注意到一個大型航空公司的名字用來查詢時主要的搜索引擎不會返回它的主頁，盡管它已經為它名字的查詢此支付了昂貴的而廣告費。一個優秀的搜索引擎不會把廣告當做必需的雖然這可能導致它從航空公司獲得的收益受損。一般來說，從消費者的角度，為了他們可以查找到想要的東西，搜索引擎需要更少的廣告。這就是削弱現有當前搜索引擎廣告支持業務的原因。然而，依舊總會從那些希望顧客選擇商品的廣告客戶那里取得收益，或者還有其他一些較好的新的方式。但是我們相信這個論點，廣告引起太多問題的原因是它對于搜索引擎的競爭是至關重要的。在理論上是無需干涉的。
9附錄B伸縮性
9.1Google的可伸縮性
我們把Google設計成具有近期能夠處理一億網頁的可伸縮性。我們目前得到了磁盤和機器所需的款額，我們也考慮了大部分數據結構的易擴展性。然而,在100的網頁,我們將會非常接近了對各種操作系統的限制，在常見的的操作系統中(現在我們跑在Solaris與Linux)。這些包括諸如可尋址的內存,打開的文件描述符的數目,網絡帶寬和插座,以及其他許多人。我們相信擴展多到超過一億萬頁時將大大增加我們系統的復雜性。
9.2集中索引結構的可伸縮性
計算機性能的提高是它能夠以合理的成本對大量文本進行索引，當然，更多的帶寬密集型其他媒體，如視頻很可能會越來越普遍。
但是，同生產成本較低的文本相比，媒體，如視頻文件，文本可能仍然非常普遍。此外，很可能很快就會有語音識別，通過合理的工作的文字轉換成語音，擴大現有的文字數量。這一切為集中索引提供了令人驚異的可能性。 下面是一個說明性的示例。 我們假設我們要索引的美國每個人一年中寫下的任何事。 我們假設在美國有2.5億人，他們寫每日平均10 k。 這將花費空間850 TB。還假定索引萬億字節現在可以做一個合理的費用。我們還假定索引方法的文字是線性的，或接近線性的復雜性。鑒于所有這些假設，我們可以計算需要多長時間才可以指數的850TB字節的合理費用承擔一定的增長因素。摩爾定律在1965年被定義為每18個月翻一番的處理器的功耗。它過去一直明顯的符合事實，不僅僅是處理器，還有磁盤等對其他重要的系統參數。如果我們假設，摩爾定律在未來一直得到驗證，我們只需要10多倍，或15年才能達到我們索引的美國每個人一年中寫下的任何事的的目標且價格是一個小公司可以承擔的。當然，硬件專家們有些擔心摩爾定律可能無法繼續在未來15年一直被遵守，但肯定了許多令人感興趣的集中應用，即使我們只能達到我們假設的例子的一部分成果。
當然，一個分布式的系統比如 G l oss或Harvest通常會給索引帶來高效和較好的技術解決方案，但由于過高的安裝設置和管理成本，似乎難說服全世界都使用這些系統。然而，減少管理成本還是很有大有可能的。 如果發生這種情況，并且每個人都開始運行一個分布式的索引系統搜索會當然改善大幅。
因為，計算機不斷的發展，人們受限于只能打字和說話，文本索引增加的比例比當前會更多。當然，計算機生成的內容可能無限，但只索引大量的人共生成內容似乎極其有用。 因此，我們樂觀的認為，我們集中式的Web搜索引擎結構將改善和有助于搜素文本信息的能力，并隨著時間的推移擴展，未來搜索會很光明。
來源：盧松松博客
