1

我在某处读到，当你有一个倒排索引时（例如，你有一个 brutus 页面的排序列表、一个 caesar 页面的排序列表和一个 calpurnia 页面的排序列表），当你做 caesar AND brutus AND calpurnia , 如果 calpurnia 和 brutus 的页数少于 caesar 的页数，那么你应该做 caesar AND (brutus and calpurnia)，这意味着你应该先评估后者。通常，每当您有一系列 AND 时，您总是首先评估具有最少页数的对。这背后的原因是什么？为什么这样有效？

4

2 回答 2

0

对于倒排索引的每种情况，情况并非如此。如果您需要顺序扫描整个倒排索引，那么您首先执行哪个帖子列表交集无关紧要。

但是，假设倒排列表存储在索引关系中。然后评估具有较少文档出现次数的对将等于加入具有较高选择性的关系，从而提高评估效率。

直观地说，当我们与较小的列表相交时，我们会创建一个更强大的过滤器，用作索引的提要以查找匹配项。

假设我们有兴趣评估关键字 query 、a b cwhere和are words 在文档中。还假设匹配的文档数如下：abc

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

注意(a JOIN b)has size10和(b JOIN c)has size 50。因此第一个需要10访问索引 on c，而第二个需要50访问索引 on a。但是使用基于散列或基于树的索引，对索引的这种访问在成本上没有太大差异，并且通常在单个 I/O 中完成。

于 2011-04-16T01:55:25.523 回答
0

要意识到的重要一点是，由于您已经提到的排序，可以非常有效地（通常以对数时间）搜索倒排列表以查找任何给定的文档 ID，例如使用二进制搜索。

要查看其效果，假设一个 query caesar AND brutus，并假设有occ caesar pages forcaesar和occ brutus pages for brutus（即occ X表示术语 X 的页面列表的长度）。现在假设，为了这个例子， occ caesar > occ brutus，即caesar在内容中出现的频率比brutus.

然后，您要做的是遍历所有页面 for brutus first，并在页面列表中搜索caesar每个页面。如果确实可以在对数时间内搜索列表，这意味着您需要

occ brutus * log( occ凯撒)

计算步骤来识别包含这两个术语的所有页面。

如果您反向执行（即遍历caesar列表并搜索列表中的每个页面brutus），较小的数字将以对数结束，而较大的数字将成为一个因素，因此评估所需的总时间将更长。

话虽如此，重要的是要意识到实际上事情比这更复杂，因为 (a) 列表不仅是排序的，而且是压缩的，这使得搜索更加困难，并且 (b) 部分列表可能存储在磁盘而不是内存，这意味着磁盘访问的总数比计算步骤的总数重要得多。因此，上述算法可能不适用于其最纯粹的形式，但原理如所述。

于 2012-03-06T11:41:32.163 回答