05第五章基于索引的相关排序解析.ppt

* * 文档分布式 每台索引服务器的行为类似于整个文档集一小部分数据的有哪些信誉好的足球投注网站引擎 目录机发送查询的拷贝给每台索引服务器，每台机器返回前k个结果以及每个结果的分数 这些结果由目录机合并为一个相关排序表，然后返回给用户 5.7.5 分布式的评价(Cont.) * 词项分布式 索引中的每个倒排表被分给一个索引服务器，大部分情况，所要处理的查询数据不会存储在一台机器 被选中处理查询的服务器通常是倒排表最长的那台索引服务器 如果其他索引服务器上有相关的数据，则通过网络传送给他们来处理查询 查询处理完成后，结果发生给目录机 5.7.5 分布式的评价(Cont.) * 文档中的词项分布 Zipfian分布：在给定的语料中，对于任意一个term，其频度(freq)的排名（rank）和freq的乘积大致是一个常数。 服从Zipfian分布：一些词经常出现，但是大量词出现的频率很低。即第i个常见词项的频率cfi和1/i成正比， cfi表示词项ti在所有文档中出现的次数。 查询的分布也类似。一些查询，例如关于名人或者当前的事件，在公众有哪些信誉好的足球投注网站引擎中非常流行。 一个有哪些信誉好的足球投注网站引擎每天收到的大约一半的查询是唯一的。 缓存能够改善效率 缓存以后可能用到的数据，如存储对于查询的相关排序结果，或缓存来自磁盘的倒排表。 5.7.6 缓存 * 缓存对于有哪些信誉好的足球投注网站引擎非常适合。查询和相关排序表很小，也就是在缓存中存储它们不需要占用太多的空间。 相反，在大规模语料库上处理查询是密集计算，这意味着一旦相关排序被计算出来，保存它通常是很有意义的。 缓存能够改善效率，当内存空间吃紧时，缓存应该专注于最常见的查询，给缓存倒排表留下足够的空间。 缓存中的数据要新，避免陈旧数据。 5.7.6 缓存(Cont.) * 总结 抽象的相关排序模型 倒排索引 索引的构建 简单构建 索引融合 分布式索引 查询处理 Document-at-a-time Term-at-a-time 优化技术 * * * * 5.6.2 融合(Cont.) 图 索引融合实例 索引A和索引B合并产生新的索引 * 内存中不能有2个部分索引，所以输入文件必须精细的设计以便能被融合 一个途径是按字母顺序对部分索引排序，以便用非常小的内存融合部分索引 索引融合策略也显示了可行的并行索引策略 使用多台机器构建各自的部分索引，一台机器用于合并所有的索引，形成最后的索引。 5.6.2 融合(Cont.) * 传统的有哪些信誉好的足球投注网站引擎使用一台快速机器生成索引和处理查询，但对于大数据不适用 数据量爆炸式增长、服务器廉价，促进分布式索引的出现 使用众多廉价服务器和分布式软件来实现协同。 5.6.3 分布式索引 * 迄今为止，一直假设索引是批量处理 文档集合作为索引器的输入，索引器构建索引，然后系统允许用户进行查询。 实际上，文档集合是变化的，2种技术解决更新问题 索引合并 结果合并 5.6.4 更新 * 索引合并 构建一个新的较小的索引I2，然后与旧的索引I1合并，形成一个新的包含全部数据的索引I -当有大量文档同时更新时，索引合并是可行的策略。 -对于单一文档的更新，索引合并不是一个好的策略，因为将整个索引写入硬盘相当耗时。 结果合并 对新数据构建一个小的索引，但不合并到大的索引中。查询分别在这个小的索引和大的索引中处理，结果被融合在一起，返回给用户前k个文档。 5.6.4 更新(Cont.) * 如何从索引中删除文档？ 使用被删除文档列表。 在查询处理时，系统检查被删除文档列表，确定没有被删除文档进入到给用户显示的结果列表中。 如果文档内容更改，可以使用删除文档列表删除旧的版本，然后在新的文档列表中加入新的版本 5.6.4 更新(Cont.) * 太多的索引会使查询处理变慢，太少的索引会由于过度的磁盘访问导致索引构建过程变慢 几何分割：必威体育精装版的索引I0包含内存中能存到的数据，索引I1包含大约是I0的r倍的数据。 如果m是机器内存的字节数，则索引In包含 和 之间的字节数据。如果索引In包含超过 的数据，将被合并到索引In+1中 5.6.4 更新(Cont.) * 假设文档集合包含五个文档，每个文档内容如图所示，在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。 例：索引构建实例 * 中文和英文等语言不同，单词之间没有明确分隔符号，所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流。 为了系统后续处理方便，需要对每个不同的单词赋予唯一的单词编号，同时记录下哪些文档包含这个单词，在如此处理结束后，我们可以得到最简单的倒排索引。 最简单的倒排索引 * 包含计