Compression scheme for improving cache behavior in database systems

Abstract

A scheme for accessing a multi-dimensional index structure resident in main memory to refer to data objects stored in a database is disclosed. To reduce the amount of accessed index data, the scheme compresses a minimum bounding rectangle ('MBR'). The first step to compress the MBR is to represent the MBR relatively to a reference MBR. The relative representation of an MBR ('RMBR') is coordinates of the MBR represented relative to coordinates of the reference MBR. In addition, quantization may be performed as an additional step for further compression. In this step, the RMBR is quantized using a finite level of quantization chosen from a given set of quantization levels. Alternatively, a proper node size can be chosen to reduce the index search time. The present invention also includes several alternative embodiments of the accessing scheme including whether to eliminate pointer in internal node's entries except the first entry, whether to store a reference MBR in non-root nodes, whether to apply the proposed compression technique by quantization to leaf nodes or not, and whether to place the database in main memory or in disk. Also, the present invention includes an apparatus, a system and a computer readable medium for accomplishing the same scheme as described above.