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

主存技术的不断进步,使得主存多媒体数据库的实现成为可能.研究表明,主存多媒体数据库系统性能深受处理器缓存未命中的影响,缓存感知型主存索引是提高数据检索效率的有效手段.针对SA-Tree不适用于主存存取的缺点,提出它的变体CSA-Tree.CSA-Tree利用PCA降维技术,将树的各层节点采用不同的维度表示,这样不仅提高了缓存空间的利用率,还降低了CPU负载,从而提高了索引查询效率.大量实验证明,CSA-Tree在主存环境中具有良好的高维数据检索性能.

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

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.