CSA-Tree:An Optimized High-Dimensional Index Tree for Main Memory Access
Jun Sheng Liang · Chinese Journal of Computers · 2007
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.