信息检索导论---第四章读书笔记

第四章 构建索引

一、硬件相关概念

1. 扇区是磁盘中最小的物理存储单元
2. 操作系统将相邻的扇区组合在一起，形成一个数据块，对块进行管理，每个块包含2，4，8，16，32或64个扇区
3. 数据块是逻辑概念，而非物理概念。
4. 一个数据块只能放一个文件，因此文件的实际大小是小于等于所占的存储空间大小的。
5. 操作系统往往以数据块为单位进行读写，因此，读取一个字节可能和读取一个数据块耗费的时间一样
6. 进行磁盘读写时，需要将磁头移到数据所在的磁道，该过程耗费的时间称为寻道时间。
7. 寻道时间一般在5ms左右，该过程不进行数据传输。
8. 为了使数据传输效率最大，通常连续读取的数据块也应该在磁盘上连续存放。
9. 数据从磁盘传输到内存是系统总栈而不是处理器实现的，在磁盘IO时仍然可以处理数据。
10. 把频繁访问的磁盘数据放入内存中的技术称为高速缓存（caching）。
11. 把内存中保存读写块的那块区域称为缓冲区（buffer）。
12. 访问内存数据比磁盘数据快很多，内存传输数据是磁盘传输数据速度的10倍

二、基于块的排序索引方法–BSBI

1. 将文档切分为几个大小相等的部分
2. 将每个部分的词项ID–文档ID对排序–在内存中排序，尽量减少磁盘随机寻道的次数，磁盘顺序读取会比随机寻道速度块很多。
3. 直到累积放满一个数据块空间，将中间产生的临时文件写入磁盘
4. 合并磁盘文件成为最终的索引—利用最小堆结构或者类似的数据结构
5. BSBI算法的时间复杂度，该算法主要在排序上耗费时间，时间复杂度为（THETA(TlogT))
6. 该算法一般需要两次扫描，一次扫描得到词汇表，一次扫描构建倒排索引

三、内存式单遍扫描索引构建方法–SPIMI

1. BSBI方法需要将词项映射成ID，对于大规模文档集来说，在内存中难以存放。
2. SPIMI使用词项而不是ID，将每个块的词典写入磁盘，对下一个块重新采用新的词典

• BSBI和SPIMI的区别：
  1. SPIMI直接在倒排记录表中增加一项，倒排记录是动态增长的；而BSBI是在一开始进行排序
  2. SPIMMI的优点：1）不需要排序，处理的速度更快；2）保留了词项的归属关系，节省内存
  3. SPIMI的时间复杂度是theta(T),因为不需要排序操作

四、分布式索引构建方法

1. 基于词项分割的分布式索引
2. 基于文档分割的分布式索引–实际中主要采用
3. 从词项到ID的映射，分布式构建，一种常用的方法是对高频词维护一张词项到ID的映射表，复制到所有的节点上，对低频词直接利用词项而不是ID。

五、动态索引构建方法

1. 最简单的方法是周期性的从头重新构建

2. 如果要求及时检索到新文档，需要维护两套索引，一个是大的主索引，一个是存储新文档的辅助索引，辅助索引保存在内存中，查询时可以将二者的结构进行合并。

   当辅助索引变得很大时，就将辅助索引合并到主索引上。

3. 存在的问题：多个索引保存和合并开销较大，在合并期间搜素效率较低，同时维护的复杂性也较高，因此，

   在实际中，大多数搜索引擎选择重新构建。

六、其它索引构建方法

1. 带位置信息的索引结构
2. 用户授权往往通过ACL（访问控制表）来实现，在查询时，用户的访问资格往往通过直接从文件系统返回的访问信息来验证–即使这样会降低查询效率。