倒排索引压缩算法研究综述

不断增长的互联网网页信息和成千上万的用户查询请求给搜索引擎的索引更新和查询访问带来了前所未有的实时性挑战.高效的索引压缩算法能够降低索引数据的存储和传输开销,加快处理器对索引数据的处理速度,因此能直接影响搜索引擎系统的查询性能.首先,概述了倒排索引中倒排链表所包含的d-gap和freq整数序列的存储结构,并依据压缩码字的对齐方式对倒排索引压缩算法进行分类;其次,详细阐述了当前流行的字对齐压缩算法,并总结了Simple、Frame of Reference(FOR)、Optimized Chunk Splitting(OCS)等几类典型的倒排索引压缩算法;之后,综述了倒排索引压缩算法的SIM D并行化研究,即采用SIMD指令集中Shuffle数据置换和垂直布局存储来加速算法对d-gap整数序列的并行处理性能.然后,针对压缩倒排索引的随机访问问题,综述了通常采用的自索引技术和原始序列压缩算法两种策略.最后,对倒排索引压缩算法在搜索引擎系统中的应用进行了分析和总结并对未来倒排索引压缩算法可能的研究方向进行了探讨和展望.

面向大规模图数据的关键词覆盖最优路径规划方法

针对个性化自驾游路径规划中存在规划路径无法满足不同用户个性化需求的问题,提出了基于不同用户兴趣点的关键词覆盖最优路径规划方法。首先,建立路网信息预处理模型并通过路网信息预处理算法绘制路网信息查询图;其次,使用倒排索引算法根据用户设定的个性化需求对路网信息查询图进行剪枝,在减小大规模数据处理内存开销的同时提升了关键词覆盖最优路径规划方法的执行效率;最后,通过双向并行拓展方式的关键词覆盖最优路径拓展算法实现满足用户兴趣点的个性化旅游路径推荐。实验结果表明,关键词覆盖最优路径规划方法不仅实现了满足用户个性化需求的路径规划,而且通过剪枝和双向并行拓展的方式提高了方法的执行效率。