System and method for construction of a data structure for indexing multidimensional objects
First Claim
1. A computerized method of constructing a tree data structure for indexing multidimensional data objects stored in a computer database, said method comprising the steps of:
- constructing a binary tree data structure indexing the multidimensional data objects wherein leaf nodes contain no more than a predetermined maximum number of the multidimensional data objects;
traversing the binary tree from top to bottom and iteratively compressing parent and non-leaf child node pairs into collapsed nodes, each collapsed node having no more than a predetermined maximum fanout for improving page utilization, responsive to said step of constructing; and
storing a compressed data structure in a computer readable memory, responsive to said steps of traversing and compressing.
1 Assignment
0 Petitions
Accused Products
Abstract
An apparatus and a method for constructing a multidimensional index tree which minimizes the time to access data objects and is resilient to the skewness of the data. This is achieved through successive partitioning of all given data objects by considering one level at a time starting with one partition and using a top-down approach until each final partition can fit within a leaf node. Subdividing the data objects is via a global optimization approach to minimize the area overlap and perimeter of the minimum bounding rectangles covered by each node. The current invention divides the index construction problem into two subproblems: the first one addresses the tightness of the packing (in terms of area, overlap and perimeter) using a small fan out at each index node and the other one handles the fan out issue to improve index page utilization. These two stages are referred to as binarization and compression. The binarization stage constructs a binary tree such that the entries in the leaf nodes correspond to the spatial data objects. The compression stage converts the binary tree into a tree for which all but the leaf nodes and the parent nodes of all leaf nodes have branch factors of M. In the binarization stage, a weighting or skew factor is used to achieve flexibility in determining the number of data objects to be included in each of the partitions to obtain a tree structure with desirable query performance. Thus the index tree constructed is not required to be height balanced. This provides a means to trade-off imbalance in the index tree in order to reduce the number of pages which need to be accessed in a query.
-
Citations
37 Claims
-
1. A computerized method of constructing a tree data structure for indexing multidimensional data objects stored in a computer database, said method comprising the steps of:
-
constructing a binary tree data structure indexing the multidimensional data objects wherein leaf nodes contain no more than a predetermined maximum number of the multidimensional data objects; traversing the binary tree from top to bottom and iteratively compressing parent and non-leaf child node pairs into collapsed nodes, each collapsed node having no more than a predetermined maximum fanout for improving page utilization, responsive to said step of constructing; and storing a compressed data structure in a computer readable memory, responsive to said steps of traversing and compressing. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A computer processing system for constructing a tree data structure which indexes multidimensional data objects stored in a computer database, said system comprising:
-
binarization means for constructing a binary tree data structure indexing the multidimensional data objects wherein leaf nodes contain no more than a predetermined maximum number of the multidimensional data objects; compression means, coupled said binarization means, for traversing the binary tree from top to bottom and iteratively compressing parent and non-leaf child node pairs into collapsed nodes, each collapsed node having no more than a predetermined maximum fanout for improving page utilization; and a memory, coupled said binarization means and said compression means, for storing a data structure including the collapsed nodes. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the machine to perform method steps for constructing a tree data structure for indexing multidimensional data objects stored in a computer database, said method steps comprising:
-
constructing a binary tree data structure indexing the multidimensional data objects wherein leaf nodes contain no more than a predetermined maximum number of the multidimensional data objects; traversing the binary tree from top to bottom and iteratively compressing parent and non-leaf child node pairs into collapsed nodes, each collapsed node having no more than a predetermined maximum fanout for improving page utilization, responsive to said step of constructing; and storing a compressed data structure in a computer readable memory, responsive to said steps of traversing and compressing. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
Specification