【IR系统的基本性能】
1、访问内存数据比访问磁盘数据快得多,只需要几个时钟周期(大概 5 × 10−9 s)便可以访问内存中的一个字节,与此形成鲜明对照的是,从磁盘传输一个字节所需要的时间则长 得多(大概 2 × 10−8 s)。因此,我们会尽可能地把数据放在内存中,特别是那些访问频繁的数据。这种将频繁访问的磁盘数据放入内存的技术称为缓存技术(caching)。
2、进行磁盘读写时,磁头移到数据所在的磁道需要一段时间,该时间称为寻道时间,对典型的磁盘来说平均在 5 ms 左右。寻道期间并不进行数据的传输。于是,为使数据传输率最大,连续读取的数据块也应该在磁盘上连续存放。举例来说,基于表 4-1 中的数据的 话,大概只需要 0.2 秒钟就可以将一个连续存放的 10MB 数据块从磁盘传输到内存,但 是如果上述数据存放在 100 个非连续的块中,那么,需要移动 100 次磁头,因此总时间 可能会需要 0.2 + 100 × (5 × 10−3) = 0.7 s。
3、操作系统往往以数据块为单位进行读写。因此,从磁盘读取一个字节和读取一个数据块 所耗费的时间可能一样多。数据块的大小通常为 8 KB、16 KB、32 KB 或 64 KB。我们 将内存中保存读写块的那块区域称为缓冲区(buffer)。
4、数据从磁盘传输到内存是由系统总线而不是处理器来实现的,这意味着在磁盘 I/0 时处 理器仍然可以处理数据。我们可以利用这一点来加速数据的传输过程,比如将数据进行压缩然后再存储在磁盘上。假定采用一种高效的解压缩算法的话,那么读磁盘压缩数据 再解压所花的时间往往会比直接读取未压缩数据的时间要少。
[基于块的排序索引方法]
为了建立索引我们扫描一遍文档集合得到所有的词项—文档 ID 对。然后,我们以词项为主键、文档 ID 为次键进行排序。最后,将每个词项的文档 ID 组织成倒排记录表,并计算诸如词项频率或者文档频率的统计量。对于小规模文档集来说,上述过程均可在内存中完成。本章我们主要讨论在大规模文档集条件下需要引入二级存储介质时的索引方法。
为使索引构建过程效率更高,我们将词项用其 ID 来代替。由于内存不足,我们必须使用基于磁盘的外部排序算法(external sorting algorithm)。为了达到可以接受的速度,对该算法的核心要求是:在排序时尽量减少磁盘随机寻道的次数。
BSBI(blocked sort-based indexingalgorithm,基于块的排序索引算法)是一种解决的办法:
第 1 步,将文档集分割成几个大小相等的部分;
第 2 步,将每个部分的词项 ID—文档 ID 对排序;
第 3 步,将中间产生的临时排序结果存放到磁盘中;
第 4 步,将所有的中间文件合并成最终的索引。
下面讨论 BSBI 算法的复杂度。由于该算法最主要的时间消耗在排序上,因此其时间复杂度为 Θ(T log T),其中 T 是所需要排序的项数目的上界(即词项 ID—文档 ID 对的个数)。然而实际的索引构建时间往往取决于文档分析(PARSENEXTBLOCK)和最后合并(MERGEBLOCKS)的时间。
【内存式单遍扫描索引构建方法】
基于块的排序索引算法具有很好的可扩展性,但是需要一种将词项映射成其 ID 的数据结构。对于大规模的文档集来说,该数据结构会很大以致在内存中难以存放。一种更具扩展性的算法称为 SPIMI(single-pass in-memory indexing,内存式单遍扫描索引算法)。SPIMI 使用词项而不是其 ID,它将每个块的词典写入磁盘,对于下一个块则重新采用新的词典。只要硬盘空间足够大,SPIMI 就能够索引任何大小的文档集。
SPIMI 算法的流程如图 4-4 所示,其中省略了文档分析以及将文档转换成词项—文档 ID 流(算 法中称为 token_stream)的过程。反复调用 SPIMI-INVERT 函数直到将全部的文档集处理完为止。
【BSBI 和 SPIMI 的区别】
1、BSBI对TokenHit排序，所以排序的时间基准是TokenHit的个数。SPIMI对词项排序，排序的基准是Token的个数，所以SPIMI对排序的时间大大减小。
2、BSBI需要使用一个数据结构将词项转变成词项ID。SPIMI不需要，省内存。
【分布式索引构建】
使用mapreduce即可。
【动态索引构建】
大部分文档集会随文档的增加、删除或更新而不断改变。这也意味着需要将新的词项加入词典,并对已有词项的倒排记录表进行更新。如果要求能够及时检索到新文档,那么一种解决方法是同时保持两个索引:一个是大的主索引,另一个是小的用于存储新文档信息的辅助索引(auxiliary index),后者保存在内存中。检索时可以同时遍历两个索引并将结果合并。
问题：
1、按目前架构，不更新索引，只更新属性，所以如果一个文档发生变化，则新的Token会被无视。不过一个条文档发布后，无法编辑，所以不存在此问题。
2、对于文档的删除，从TokenID找到DocID，那么Doc的属性中会记录此文档是否被删除再决定是否展现。另外，按照目前架构，如果有大量文档被删除，对于已新索引，则会存在大量空的情况。