论文部分内容阅读
随着网络技术的迅速发展和互联网应用的不断普及,可以从互联网上获得的信息呈爆炸式增长,互联网已经成为全球规模最大、使用最广泛的信息库。为了有效地从这些海量数据中检索到需要的信息,互联网搜索引擎是一种必不可少的技术手段。互联网搜索技术已经成为信息检索领域的重要研究课题。由于海量的网页数据和巨大的查询需求,搜索引擎的效率是影响信息获取的关键问题。因此,本文主要研究提高互联网搜索效率的方法,并重点研究适用于大规模互联网搜索的TopK处理策略。TopK处理指使用各种优化手段、以最小的代价从海量文本信息中获得正确的前K个结果。能否实现高效的TopK算法,对互联网搜索的性能至关重要。本文的主要贡献包括以下几个方面:1.本文提出了一种利用网页结构化数据特征的倒排索引结构,并且提出了利用这种索引结构的高效TopK处理策略。在通用网页搜索中,当相关排序函数考虑Term Proximity等多种因素的情况下,所提方法能明显提高TopK处理的性能。本文还探讨了如何利用Term Proximity探测算法来进一步避免不必要的Term Proximity分数计算。在TREC数据集上的实验结果表明,本文中提出的算法不仅适用于线性组合的排序函数,对非线性的排序函数也取得了明显的效果,而且对于近似TopK处理问题也获得了预期效果。和传统的索引方法相比,创建基于网页结构化数据特征的倒排索只增加很小的额外复杂度,而且没有增加存储空间消耗。因此,这种索引结构完全符合大规模搜索引擎的需要。大量的实验结果证明本文提出的索引结构和算法是有效的。2.本文提出了一种通过对词组建立辅助索引来提高TopK处理性能的策略。考虑到传统信息检索能利用词组索引来实现高效的词组查询处理,本文总结了Term Proximity函数和词组的密切关系,提出对词组建立辅助索引来降低对Term Proximity分数上限的估计。这样在对倒排索引进行TopK处理时能够提前满足停止条件,或者节约不必要的Term Proximity分数计算,从而提高了通用网页搜索中TopK处理的性能。同时本文还研究了词组和词频分布的特点,提出只对最有必要的一部分词组建立辅助索引,尽可能地减少词组索引所占空间的开销。本文提出三种不同格式的精简词组索引,并且比较它们的性能和空间效率,同时还研究了利用精简词组索引帮助基于网页结构的倒排索引获得更高的TopK处理性能的可能性。3.针对面向对象的搜索系统,本文研究了对象聚合映射的TopK处理问题,提出了一个高效的TopK处理框架。对象聚合映射指的是利用一种对象的倒排索引有效地检索出另一种对象。传统的做法是将对象聚合映射的TopK处理分成检索和聚合两部分,而且主要优化其中的聚合部分。和传统方法不同,本文把检索和聚合两部分当作一个整体来考虑,提出了三种TopK处理的优化准则,并且利用多种类型对象的特征,建立了一种混合的倒排索引结构,获得了实质意义上的TopK性能提升。综上,本文提出了一系列针对互联网信息检索系统的TopK算法,通过在实际的大规模互联网数据集上进行的各种实验,证明了这些方法的合理性和有效性,本文研究的成果已经在实际的互联网搜索原型系统中获得了成功的应用。