K-ary search tree revisited:improving construction and intersection efficiency

作     者：Xingshen SONG Jinsheng DENG Fengcai QIAO Kun JIANG Xingshen SONG;Jinsheng DENG;Fengcai QIAO;Kun JIANG

作者机构：College of Advanced Interdisciplinary StudiesNational University of Defense TechnologyChangsha 410000China Faculty of Computer Science and EngineeringXi’an University of TechnologyXi’an 710000China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2022年第16卷第3期

页      面：215-217页

核心收录：

学科分类：08[工学] 0903[农学-农业资源与环境] 0901[农学-作物学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：cache tree intersection 

摘      要：1 Introduction Recently,k-ary search tree is gaining popularity as one infrastructure in search *** to its intrinsic cache-and SIMD-friendly capabilities,k-ary search tree is efficient in compression and query processing when combined with inverted index[1-3].In a k-ary tree,each node is composed of k-1 entries,which evenly partitions its range into k subranges(subnodes).By aligning the node size with buffer size of faster cache,the data is expected to be better utilized before evicted out,and fewer cache misses are triggered as well.