MULTIDIMENSIONAL SPACE DATA STRUCTURE, METHOD FOR UPDATING AND SEARCHING MULTIDIMENSIONAL SPACE DATA, RECORDING MEDIUM RECORDING THE STRUCTURE AND RECORDING MEDIUM RECORDING PROGRAM FOR EXECUTING THE METHOD

摘要

PROBLEM TO BE SOLVED: To provide a multidimensional space data structure and a method for updating and searching multidimensional space data with which the number of disk accesses in search processing can be reduced and improvement in a search performance can be attained by compressing rectangle position information in a multidimensional space with a partial space code. SOLUTION: A geometrical object in the multidimensional space is packed into minimum range rectangle and hierarchized with rectangles as leaves, the most significant rectangle is defined as a non-leaf node, a tree structure is constituted by successively linking leaf nodes to the low-order non-leaf nodes, a real part is provided by expressing the minimum range rectangle with an absolute position, a virtual range rectangle is constituted while being expressed with the partial space code based on a position relative to the minimum range rectangle of the non-leaf node, a virtual part is provided by hierarchizing the virtual range rectangle into tree structure, and in the virtual part, each node is constituted of the number of entries, multidimensional partial space codes expressing the start and end points of each slave node and slave node pointers expressing the storage position of each slave node.