智能信息处理复习4——索引构建

硬件基础

• 在内存中访问数据会比从硬盘访问数据快很多(大概10倍左右的差距)
• 硬盘寻道时间（seek time）是闲置时间：磁头在定位时不发生数据传输
• 为优化从磁盘到内存的传送时间，一个大(连续)块的传输会比多个小块(非连续)的传输速度快
• 硬盘 I/O是基于块的: 读写时是整块进行的。块大小：8KB到256 KB不等
• IR系统的服务器的典型配置是几个GB的内存，有时内存可能达到几十GB，数百G或者上T的硬盘。
• 容错处理的代价非常昂贵：采用多台普通机器会比一台提供容错的机器的价格更便宜

基于块的排序索引方法

基于块的排序索引构建算法BSBI（Blocked Sort-Based Indexing）

1. 将文档分割成几个大小相等的部分；
2. 将每个部分的词项ID-文档ID对进行排序，创建倒排记录表；
3. 将基于块的倒排索引（即将中间产生的临时文件）。写到磁盘上
4. 将所有的中间文件合并成最终的索引
   
   

内存式单遍扫描索引构建方法

• 关键思想 1: 对每个块都产生一个独立的词典 – 　不需要在块之间进行term-termID的映射
• 关键思想2: 对倒排记录表不排序，按照他们出现的先后顺序排列
• 基础上述思想可以对每个块生成一个完整的倒排索引
• 这些独立的索引最后合并一个大索引
  

分布式索引构建方法

• 维持一台主机(Master)来指挥索引构建任务-这台主机被认为是安全的
• 将索引划分成多组并行任务
• 主机将把每个任务分配给某个缓冲池中的空闲机器来执行