一种k-ary搜索树的快速求交算法  

Efficient intersection algorithm based on k-ary search tree

作　　者：王珏 包诗琦 宋省身 Wang Jue;Bao Shiqi;Song Xingshen(Dept.of Information&Communication,Officers College of PAP,Chengdu 610213,China;Chengdu Bear Rescue Centre,Chengdu 610500,China;Academy for Advanced Interdisciplinary Studies,National University of Defense Technology,Changsha 410000,China)

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

出　　处：《计算机应用研究》2021年第9期2732-2736,共5页Application Research of Computers

摘　　要：k-ary搜索树因其对高速缓存和SIMD并行指令集天然的适配性,正在受到越来越多的关注和研究。近年来,它被成功地应用于搜索引擎倒排索引结构中,用于实现高效的查询处理和索引压缩。但基于k-ary搜索树的查询处理算法目前仍处在一种相对简单基础的应用程度,效率提升有限;而且查询算法仅限于元素搜索,大大限制了其适用范围。基于上述观察,研究了基于k-ary搜索树的求交算法,并提出了两种优化技术用于压缩搜索范围以提升查询效率。实验证明,结合不同的遍历方式,优化后的求交算法可以极大地提高查询速度,尤其是针对存储海量数据的长倒排链,配合更大的SIMD寄存器,k-ary搜索树相比于传统求交算法的优势更为明显。K-ary search tree is a promising structure due to its friendliness to cache awareness and SIMD acceleration.Recent years have witnessed its successful application to inverted index for efficient query processing and index compression.However,its query processing methods are either complicated or rudimentary,and its adoption is limited in membership test,which both impair its application in real life.This paper studied the intersection algorithm for k-ary search tree,and introduced two early termination techniques collaborating with particular traversal methods to improve its intersection efficiency.The experimental analyses validated the proposed optimizations could greatly improve the query speed,and the optimized k-ary search tree suits better for long inverted lists,and when equipped with larger SIMD registers,it is able to beat the state-of-the-art sorted-array based intersection algorithms.

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

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]