反转索引评估顺序

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）列表的一部分可能存储在磁盘而不是内存中，这意味着磁盘访问的总数比计算步骤的总数要重要得多。因此，上述算法可能不适用于其最纯粹的形式，但其原理如上所述。