倒排索引评估顺序
|
我在某处读到，当您进行凯撒，布鲁托斯和卡尔普尼亚时，当您拥有倒排索引时（例如，您有一个布鲁特页面的排序列表，一个凯撒页面的排序列表和一个钙尿蛋白的页面排序列表）。 ，如果Calpunia和Brutus的页面数少于Caesar的页面数，那么您应该进行Caesar AND（Brutus和Calpurnia）的操作，这意味着您应首先评估后者的AND。通常，每当您有一系列AND时，总是首先评估页面数最少的那对。这背后的原因是什么？为什么这样有效？
没有找到相关结果
已邀请:
2 个回复
距相镭
请注意，的大小为，的大小为。因此，第一个将要求对的索引有访问，而第二个则需要对的索引具有访问。但是，使用基于哈希的索引或基于树的索引时，对索引的此类访问在成本上不会有很大差异，并且通常在单个I / O中完成。掸牛浓疗
，并假设存在针对的occcaesar页面和针对的occbrutus页面（即occX表示术语X的页面列表的长度）。为了便于说明，现在假设occcaesar> occbrutus，即内容中的“ 14”比“ 15”更频繁。 然后，您要做的是首先遍历所有页面以，然后在页面列表中搜索每个页面以获取。如果确实可以对数时间搜索列表，则意味着您需要 occbrutus *日志（occcaesar） 确定包含这两个词的所有页面的计算步骤。 如果反向进行（即遍历列表并在列表中搜索每个页面），则较小的数字将以对数结尾，较大的数字将成为一个因数，因此，总时间需要更长的时间。 话虽如此，但重要的是要认识到实际上，事情要比这复杂得多，因为（a）不仅对列表进行排序而且对其进行压缩，这使搜索更加困难，并且（b）列表的某些部分可能存储在磁盘而不是内存，这意味着磁盘访问的总数比计算步骤的总数绝对重要。因此，上述算法可能无法以其最纯粹的形式应用，但是原理已描述。