计算机应用研究

作者：王珏,包诗琦,宋省身,

单位：1.武警警官学院信息通信系,成都610213；2.四川龙桥黑熊救护中心,成都610500；3.国防科技大学前沿交叉学科学院,长沙410000；

关键词：信息检索,数据结构,算法优化,求交算法,

k-ary搜索树因其对高速缓存和SIMD并行指令集天然的适配性，正在受到越来越多的关注和研究。近年来，它被成功地应用于搜索引擎倒排索引结构中，用于实现高效的查询处理和索引压缩。但基于k-ary搜索树的查询处理算法目前仍处在一种相对简单基础的应用程度，效率提升有限；而且查询算法仅限于元素搜索，大大限制了其适用范围。基于上述观察，研究了基于k-ary搜索树的求交算法，并提出了两种优化技术用于压缩搜索范围以提升查询效率。实验证明，结合不同的遍历方式，优化后的求交算法可以极大地提高查询速度，尤其是针对存储海量数据的长倒排链，配合更大的SIMD寄存器，k-ary搜索树相比于传统求交算法的优势更为明显。

来源：2021年第9期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2021年第9期