论文部分内容阅读
随着关键字检索在Web搜索领域取得巨大成功,XML数据上的关键字检索技术也得到了广泛的关注。为了提高检索结果的有效性和性能,检索系统需要综合考虑以下问题:理解查询语义、定义查询结果、设计高效的查询算法、合理的打分排序。SLCA作为XML数据检索的返回结果已经得到了认可,IMS算法以锚结点为基础,设计了高效的多路SLCA求解算法。这些工作有效解决了XML数据关键字检索的重要问题,但作为检索前提的理解查询关键字的真实语义问题却几乎无相关工作涉及;另外,已有的XML检索系统基本都以Dewey编码为基础,编码比较和计算LCA的效率低下,而IMS算法也仍然存在相当的冗余计算。 本文分析了关键字语义扩展问题,提出了基于WikiKeywords语义网络和XML文档统计信息的复合关键字扩展技术。WikiKeywords语义网络是分析Wikipedia数据集得出的反映关键字相互关联的语义网络,我们以此为基础对用户查询关键字进行扩展,并给出了扩展关键字可信度的计算方法。为了克服WikiKeywords网络的冗余扩展问题,本文还利用XML,文档集的统计特征,建立了XMLKeywords语义网络,并综合WikiKeywords,提出了复合关键字扩展技术。 针对Dewey编码在计算SLCA时的低效问题和IMS算法存在的冗余计算问题,本文提出了基于区间编码的SLCA求解算法MMPS。MMPS以迭代的方式寻找那些在候选列表里不存在后代结点且离匹配中最右边结点最近的那些匹配(Smatch),计算其LCA,并根据Smatch的下一匹配(Nmatch),判断当前LCA是否为SLCA。MMPS有效的过滤掉那些对最终结果无用的匹配,减少了LCA的计算,同时以迭代的方式寻找Smatch,减少了候选结果集很大时的I/O开销,更适合基于语义扩展的SLCA计算;另外,算法以区间编码为基础,将编码比较和LCA计算的开销降到了O(1)。 由于MMPS算法是一种阻塞式算法,存在用户体验问题,文章进一步对其进行了改进,给出了基于可信度的PipelineMMPS算法。PipelineMMPS是一种非阻塞式的算法,算法根据扩展关键字的可信度制定计算计划,优先计算可信度高的SLCA,并直接输出,提高了用户体验。