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

作者：王珏; 包诗琦; 宋省身^*

来源：计算机应用研究, 2021, 38(09): 2732-2736.

DOI：10.19734/j.issn.1001-3695.2020.12.0548

• 信息检索
• 数据结构
• 算法优化
• 求交算法

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

• 单位
  国防科技大学