什麼是算法來搜索索引的多個值？

Question

這實際上是我正在處理的一個真正的問題，但爲了簡單起見，我們假裝我是Google。

假設用戶搜索「nanoscale tupperware」。沒有很多頁面，只有大約3k。但是，有200萬頁「納米級」和400萬「特百惠」。儘管如此，谷歌在0.3秒內爲我找到了3k。

它是如何做到的？

我知道的唯一算法是獲取「nanoscale」的文檔，獲取「tupperware」的文檔，然後執行列表合併。但那是O（N + M），或者O（5,000,000），看起來有點慢。特別是如果我在桌面上運行它而不是超高速集羣。

那麼Google究竟在做什麼，他們的速度主要是因爲他們在他們的大規模分佈式集羣上運行這種昂貴的計算？

或者有沒有更好的算法，我不知道？維基百科和谷歌沒有爲我提供任何東西。

編輯：

由於人們似乎把重點放在我的問題的谷歌方面，我想我會在實際的條款再說一遍。

我有幾個非常大的（數百萬項）索引實現爲鍵/值對。鍵是簡單的詞，值是文檔集。一個常見的用例是在不同索引上對多個搜索結果進行交集：難點在於獲取文檔集的交集。

我可以重新實現我的索引，但是我想要的 - 這主要是一個學術項目。

Answer 1

你描述它的方式，你已經有了一個inverted index，每個術語（文檔列表）都有一個發佈列表。我並不知道比合並每個術語的發佈列表合併更好的解決方案，並且據我所知，這就是像Lucene一樣的全文索引解決方案。有一對夫婦明顯的優化，你可以在這裏做，雖然：

1. 如果你能在內存中存儲數據集中，甚至是跨多臺機器分佈，可以非常快速地merge join結果集的確，相比於被什麼了磁盤搜索需要。
2. '天真'合併連接算法在每次不匹配時將一個指針向前移動一個位置，但是如果您的發佈列表本身已編入索引，則可以通過獲取單個當前值的最大值並尋找在所有其他發佈列表中的第一個值大於或等於該密鑰 - 可能會忽略數百萬個不相關的結果。這被稱爲zig-zag merge join。

Answer 2

你所描述的內容叫n-grams。

Google使用稱爲PageRank的算法來搜索和排序使用MapReduce實現的結果。

以上所有這些話題都在Stackoverflow上詳細討論過。查看它們應該相當容易。

這可能不會幫你一大堆，因爲你可能沒有一個龐大的分佈式系統來運行MapReduce，但是因爲你沒有真正給我們提供關於你想要什麼的任何細節index，很難提出適合你的問題的東西。