反轉索引評估順序

Question

我在某個地方讀到，當你有一個倒排索引時（例如，你有一個brutus頁面的排序列表，caesar的排序列表頁面和calpurnia頁面的排序列表），你做凱撒和布魯特斯和卡爾彭尼亞，如果卡爾伯尼亞和布魯托斯的頁數少於凱撒的頁數，那麼你應該做凱撒和（粗野和卡爾尼亞），這意味着你應該評估後者和第一。一般來說，無論何時你有一系列的AND，你總是首先評估具有最低頁數的對。這背後的推理是什麼？爲什麼這是有效的？

Answer 1

對於每個倒轉索引的情況都不是這樣。如果你需要順序掃描整個倒排索引，那麼你首先要做哪個發佈列表交集並不重要。

但是，假設反轉列表存儲在索引關係中的場景。然後，評估文檔出現次數較少的一對將等於加入具有較高選擇性的關係，從而提高評估效率。

直觀地說，當我們交叉較小的列表時，我們創建了一個更強的過濾器，它被用作索引的源來查找匹配。

假設我們有興趣評估關鍵字查詢a b c，其中a,b和c是文檔中的單詞。此外，假設文件匹配的數量如下：

a --> 20 
b --> 100 
c --> 1000 
a+b --> 10 
a+c --> 15 
b+c --> 50 
a+b+c --> 5 

注意(a JOIN b)有大小10和(b JOIN c)有大小50。因此，第一個將要求10訪問c索引，而第二個需要50訪問索引a。但是，使用基於散列的或基於樹的索引，對索引的訪問在成本上差別不大，通常在單個I/O中完成。

Answer 2

要認識到的一個重要的事情是，由於您已經提到的排序，對於任何給定的文檔ID，倒排列表可以是搜索非常有效（通常以對數時間），例如使用二進制搜索。

要看到的是，效果，假設查詢caesar AND brutus，並且假設有OCC _凱撒頁caesar和OCC _布魯頁brutus（即OCC _X表示的頁面的長度列表中的術語X）。爲了示例的目的，現在假定occ _caesar> occ _brutus，即caesar在內容中比brutus更頻繁地出現。

你做什麼，然後通過對brutus第一和搜索在頁面列表caesar他們每個人的所有頁面是迭代。如果確實列表可以在對數時間內搜索，這意味着你需要

OCC _布魯特斯 *日誌（OCC _凱撒）

計算步驟來標識包含兩方面的所有頁面。

如果您有反向完成了（即通過caesar列表進行迭代，尋找它的每一個在brutus列表頁），較小的數量將在對數落得和更大數量將成爲一個因素，所以評估所需的總時間會更長。 （a）列表不僅僅是排序而且是壓縮的，這使得搜索變得更加困難，（b）列表的一部分可能存儲在磁盤而不是內存中，這意味着磁盤訪問的總數比計算步驟的總數要重要得多。因此，上述算法可能不適用於其最純粹的形式，但其原理如上所述。