Patent ID: 7283987

Claim:
A method of accessing a multi-dimensional index structure resident in main memory for facilitating reference to data objects stored in a database, wherein the index structure consists of internal nodes having pointers to child nodes and leaf nodes having to database objects, the method comprising: associating with each node a minimum bounding rectangle (“MBR”), wherein each MBR is a minimal hyper-rectangle enclosing a corresponding data object in the case of a leaf node and all hyper-rectangles in the child node in the case of an internal node; representing each of one or more said MBRs by a relative representation of an MBR (“RMBR”), wherein the relative representation of an MBR (“RMBR”) is coordinates of the MBR represented relative to coordinates of a reference MBR; compressing each RMBR into a quantized RMBR (“QRMBR”) by quantizing each RMBR using a given finite level of quantization, wherein the compressing includes cutting off trailing insignificant bits of the RMBR after quantization; and accessing the data objects stored in the database as a function of the QRMBR.