CSA-Tree:一种改进的高维主存索引树  

CSA-Tree:An Optimized High-Dimensional Index Tree for Main Memory Access

作　　者：梁俊杰[1] 冯玉才[1] 

机构地区：[1]华中科技大学计算机学院

出　　处：《计算机学报》2007年第3期415-423,共9页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金([2005]555)资助

摘　　要：主存技术的不断进步,使得主存多媒体数据库的实现成为可能.研究表明,主存多媒体数据库系统性能深受处理器缓存未命中的影响,缓存感知型主存索引是提高数据检索效率的有效手段.针对SA-Tree不适用于主存存取的缺点,提出它的变体CSA-Tree.CSA-Tree利用PCA降维技术,将树的各层节点采用不同的维度表示,这样不仅提高了缓存空间的利用率,还降低了CPU负载,从而提高了索引查询效率.大量实验证明,CSA-Tree在主存环境中具有良好的高维数据检索性能.In main-memory databases, the number of processor cache misses has a critical impact on the performance of the system. Cache-conscious indices are designed to improve performance by reducing the number of processor cache misses that are incurred during a search operation. Considering the disadvantage of SA-Tree inefficient for main memory access, the authors present its variant called CSA-Tree, which is a multi-level structure where each level of the tree represents the data space at different dimensionalities by using Principal Component Analysis. Each level of the tree serves to prune the search space more efficiently as the reduced dimensions can better exploit the small cache line size. Moreover, the distance computation on lower dimensionality is less expensive. Extensive experiments show that the CSA-Tree is superior in most cases compared with other methods.

关 键 词：高维主存索引 L2-cache未命中 距离计算 KNN查询 主成分分析 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]