METHOD FOR COMPRESSING MULTI-DIMENSIONAL INDEX OF MAIN MEMORY DATABASE

摘要

PURPOSE: A method for compressing the multi-dimensional index of a main memory database is provided to enhance the index cache operation by reducing a size of the MBR(Minimum Bounding Rectangle) through the quantization of the MBR. CONSTITUTION: In order to put in more entry into a node, a CR-tree(Cache-Conscious R-tree) compresses an MBR key taking 80 percents of the index in case of a two-dimensional index. In order to remove the zero in a front part of the MBR coordinates number, the MBR key is converted into the relative coordinates on the basis of the left lower coordinates of the parent MBR. In order to remove the unimportant bits of the rear part of the relative coordinate number, the quantization is carried out by the fixed bits. Thus, the CR-tree becomes narrower and smaller than an R-tree. The two-dimensional CR-tree represents the similar update performance and the 2.5 times faster search performance than the R-tree while using 60 percents smaller spaces.