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

作　　者：Xingshen SONG Jinsheng DENG Fengcai QIAO Kun JIANG 

机构地区：[1]College of Advanced Interdisciplinary Studies,National University of Defense Technology,Changsha 410000,China [2]Faculty of Computer Science and Engineering,Xi’an University of Technology,Xi’an 710000,China

出　　处：《Frontiers of Computer Science》2022年第3期215-217,共3页中国计算机科学前沿（英文版）

摘　　要：1 Introduction Recently,k-ary search tree is gaining popularity as one infrastructure in search engines.Due 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.

关 键 词：CACHE TREE INTERSECTION 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]