论文部分内容阅读
索引技术是现代信息检索、搜索引擎和数据挖掘的关键技术之一。对于大规模文本检索系统，倒排索引是目前为止最高效的数据索引方法。倒排索引包含了词(Term)对应文档的关系信息，可以用来快速解析用户的关键字查询。在过去的几十年中，离线倒排索引构建算法(Off-line Index Construction Algorithms)得到了广泛而深入的研究，目前的倒排索引构建算法都具有较低的时间复杂度和空间复杂度，理论上可以使用有限的内存空间构建无限数量文档的倒排索引。但是，这种倒排索引构建算法假设文档集在索引构建过程中是不变化的，而且在索引构建过程中也不能接受文档查询操作。
然而，随着Web2.0的出现和电子商务的发展，Web数据的变化越来越频繁。同一个关键词的前一秒搜索和后一秒搜索的结果都会因为Web数据的增加、删除和修改而不一样。本文研究这种大规模动态文本的在线索引构建技术(On-line Index Maintenance)，构建的倒排索引可以实时反应文档集的动态变化情况，支持高效的文档添加、删除和修改操作；同时在索引构建过程中，仍然可以接受查询操作，将文档集的变化情况实时反应在查询结果中。我们详细分析和归纳了各种离线倒排索引构建算法和已有的几种增量文本倒排索引在线更新算法。在数据变化非常频繁的搜索应用中，这些方法的索引更新和查询处理性能将急剧下降。因此，本文提出了一种新的动态平衡树(Dynamic BalanceTree)在线索引更新模型。我们把基于合并的索引更新过程表示成树的构建过程，提出了动态平衡树的概念，用来统一描述索引更新过程和控制索引数据的更新。这种模型不仅适合增量文本的在线索引更新，也适合文档添加、删除和修改同时存在的动态文本的在线索引更新，可以很好地处理索引构建和查询处理之间的性能均衡问题，是基于合并的索引更新方法的一个统一框架。在大规模Web数据集上的实验测试表明，基于动态平衡树模型的在线索引更新方法是高效的，具有很好的适应性和规模可扩展性。
倒排索引构建算法对文档删除的支持是动态文本在线索引的另一个重要方面。我们深入探讨了文档删除对倒排索引构建和查询处理的性能影响，对已有的删除文档垃圾回收算法进行了分析。在基于门限值的在线索引垃圾回收方法基础上，提出了一种面向粒度的垃圾回收方法，减少了在垃圾回收中代价颇高的倒排链(Posting list)重构操作。此外，我们将跳表(Skip List)引入到倒排索引结构中，进一步提出了一种基于跳表的自适应粒度(Adaptive Granularity，AG)垃圾回收方法。跳表在逻辑上将倒排链分成删除区块和无删除区块，而区块作为垃圾回收的粒度，可根据删除文档的分布情况自适应调节。该方法不仅可以避免对无删除区块进行重构，而且也可以避免对删除区块进行处理，显著提高了垃圾回收效率。实验表明，面向粒度的垃圾回收方法将垃圾回收的性能提高将近20％，而基于跳表的自适应粒度垃圾回收方法则提高30％以上。
此外，我们研究了目前一些主流的信息检索系统，对这些系统所采用的技术和算法进行了分析。由于目前已有的信息检索平台绝大部分都是面向静态文本的离线检索平台，因此，我们设计并实现了一套既支持传统信息检索实验，又面向动态文本在线索引的实验平台FirteX。该平台有良好的架构、并具有高性能、高可伸缩性、易扩展和易维护等特点。FirteX曾获得第二届东北亚OSS竞赛杰出贡献奖、第二届(2006)中国开源软件竞赛学生组银奖和中国科学院第二届开源软件设计大赛一等奖等奖项。
动态文本在线索引技术的研究最近几年得到了广泛的关注。本文的研究工作对于推动这一研究方向的发展具有较为重要的启发意义。本文的检索系统是一个新的尝试，也是传统信息检索平台的重要突破，对于推动新型在线索引和检索系统的发展具有较为重要的带头作用。当然，在线索引技术还有很多工作要做，需要相关领域的研究者们不懈努力。