System and method for construction of a data structure for indexing multidimensional objects

• US 5,781,906 A
• Filed: 06/06/1996
• Issued: 07/14/1998
• Est. Priority Date: 06/06/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip Shi-lung, Wolf, Joel Leonard, Aggarwal, Charu Chandra
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/660,047
• Time in Patent Office: 768 Days
• Field of Search: 707/102, 707/100, 707/1, 707/3, 707/2, 364/282.1, 364/282.3, 341/51
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

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.

2. A computerized method as claimed in claim 1, wherein said step of constructing a binary tree comprises the step of:

partitioning the data objects contained in a parent node into a child node pair according to a skew factor which represents a maximum imbalance between a number of data objects contained in a bounding rectangle associated with each child node of the child node pair; and

selecting the child node pair associated with bounding rectangles having a smallest total area subject to an overlap factor limiting an amount of overlap of the bounding rectangles, responsive to said step of partitioning.

3. A computerized method as claimed in claim 2, wherein said step of selecting the child node pair further comprises the step of adjudicating ties by selecting the child node pair associated with the bounding rectangles having a relative minimum total perimeter.

4. A computerized method as claimed in claim 1, wherein said step of constructing the binary tree further comprises the steps of:

creating and maintaining an ordered list of all nodes containing more than the predetermined maximum number of the data objects;

initializing the ordered list to a single node containing all of the data objects; and

iterating the following steps while the ordered list is non-empty;

selecting a parent node from the list; and

partitioning the data objects contained in the parent node into a first child node and a second child node according to a skew factor which represents a maximum imbalance in a number of data objects associated with the first child node and the second child node; and

removing the parent node from the ordered list and adding thereto at least one of the child nodes according to whether they contain more than the predetermined maximum number of the data objects.

5. A computerized method as claimed in claim 4, wherein said step of partitioning comprises the steps of:

ordering centers of the data objects according to a longest dimension in a bounding rectangle corresponding to said parent node;

evaluating all partitions according to the skew factor and for which the number of the centers of the data objects associated with the first child node is a multiple of a predetermined incremental value; and

choosing among said all partitions, one partition associated with bounding rectangles having a smallest total area subject to an overlap factor which constrains an amount of overlap of the bounding rectangles.

6. A computerized method as claimed in claim 5, wherein the predetermined incremental value is one.

7. A computerized method as claimed in claim 5, wherein the predetermined incremental value is equal to the predetermined maximum number of the data objects contained in the leaf node.

8. A computerized method as claimed in claim 5, comprises the steps of:

ordering centers of the data objects according to each dimension in the bounding rectangle corresponding to said parent node; and

said step of choosing among all said partitions is done in said each dimension.

9. A computerized method as claimed in claim 8, wherein said predetermined incremental value is one.

10. A computerized method as claimed in claim 8, wherein said predetermined incremental value is equal to the predetermined maximum number of the data objects in the leaf node.

11. A computerized method as claimed in claim 1, wherein said step of compressing the binary tree further comprises the steps of:

creating and maintaining a list with entries corresponding to non-leaf nodes, in breadth-first order;

iterating the following steps while said ordered list is non-empty;

selecting a parent node from the list;

choosing a child node, associated with the parent node from the list, containing the largest number of data objects and collapsing the child node into the parent node from the list;

removing the parent node from the list and replacing the parent with a revised parent node provided the number of data objects is less than said predetermined maximum number of data objects.

12. A computerized method as claimed in claim 1, comprising the steps of:

finding for each leaf node an ancestor node such that a number of data objects corresponding to said ancestor node is not greater than said predetermined maximum number of data objects but the number of data objects corresponding to a parent of said ancestor node is greater than said predetermined maximum; and

collapsing all non-leaf descendants of said ancestor node into said ancestor node, responsive to said step of constructing a binary tree.

13. A tree data structure tangibly fixed in a computer readable memory for indexing multidimensional data objects, said data structure constructed according to a method comprising the steps of claim 1.

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.

15. A computer processing system as claimed in claim 14, wherein said binarization means comprises:

sweep logic means for partitioning the data objects contained in a parent node into a child node pair according to a skew factor which represents a maximum imbalance between a number of data objects contained in a bounding rectangle associated with each child node of the child node pair, and for selecting the child node pair associated with bounding rectangles having a smallest total area subject to an overlap factor limiting an amount of overlap of the bounding rectangles.

16. A computer processing system as claimed in claim 15, wherein said sweep logic means further comprises means for adjudicating ties by selecting the child node pair associated with the bounding rectangles having a relative minimum total perimeter.

17. A computer processing system as claimed in claim 14, wherein said binarization means further comprises:

means for creating and maintaining an ordered list of all nodes containing more than the predetermined maximum number of the data objects;

means for initializing the ordered list to correspond to a single node containing all of the data objects; and

means for iterating the following steps while the ordered list containing said all of the data objects is non-empty;

means for selecting a parent node from the list, and partitioning the data objects contained in the parent node into a first child node and a second child node according to a skew factor which represents a maximum imbalance in a number of data objects associated with the first child node and the second child node; and

means for removing the parent node from the ordered list and adding thereto at least one of the child nodes according to whether they contain more than the predetermined maximum number of the data objects.

18. A computer processing system as claimed in claim 17, wherein said sweep logic means comprises:

means for ordering centers of the data objects according to a longest dimension in a bounding rectangle corresponding to said parent node;

means for evaluating all partitions according to the skew factor and for which the number of the centers of the data objects associated with the first child node is a multiple of a predetermined incremental value; and

means for choosing among said all partitions, one partition associated with bounding rectangles having a smallest total area subject to an overlap factor which constrains an amount of overlap of the bounding rectangles.

19. A computer processing system as claimed in claim 18, wherein the predetermined incremental value is one.

20. A computer processing system as claimed in claim 18, wherein the predetermined incremental value is equal to the predetermined maximum number of the data objects contained in the leaf node.

21. A computer processing system as claimed in claim 18, wherein said sweep logic comprises:

means for ordering centers of the data objects according to each dimension in the bounding rectangle corresponding to said parent node; and

means for choosing among all said partitions in said each dimension.

22. A computer processing system as claimed in claim 21, wherein said predetermined incremental value is one.

23. A computer processing system as claimed in claim 21, wherein said predetermined incremental value is equal to the predetermined maximum number of the data objects in the leaf node.

24. A computer processing system as claimed in claim 14, wherein said compression means further comprises:

means for creating and maintaining a list with entries corresponding to non-leaf nodes, in breadth-first order;

means for iterating the following steps while said ordered list is non-empty;

means for selecting a parent node from the list;

means for choosing a child node, associated with the parent node from the list, containing the largest number of data objects and collapsing the child node into the parent node from the list;

means for removing the parent node from the list and replacing the parent with a revised parent node provided the number of data objects is less than said predetermined maximum number of data objects.

25. A computer processing system as claimed in claim 14, comprising:

precompression means for finding for each leaf node an ancestor node such that a number of data objects corresponding to said ancestor node is not greater than said predetermined maximum number of data objects but the number of data objects corresponding to a parent of said ancestor node is greater than said predetermined maximum; and

for collapsing all non-leaf descendants of said ancestor node into said ancestor node, responsive to said step of constructing a binary tree.

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.

27. A program storage device as claimed in claim 26, wherein said step of constructing a binary tree comprises the step of:

partitioning the data objects contained in a parent node into a child node pair according to a skew factor which represents a maximum imbalance between a number of data objects contained in a bounding rectangle associated with each child node of the child node pair; and

selecting the child node pair associated with bounding rectangles having a smallest total area subject to an overlap factor limiting an amount of overlap of the bounding rectangles, responsive to said step of partitioning.

28. A program storage device as claimed in claim 27, wherein said step of selecting the child node pair further comprises the step of adjudicating ties by selecting the child node pair associated with the bounding rectangles having a relative minimum total perimeter.

29. A program storage device as claimed in claim 26, wherein said step of constructing the binary tree further comprises the steps of:

creating and maintaining an ordered list of all nodes containing more than the predetermined maximum number of the data objects;

initializing the ordered list to a single node containing all of the data objects; and

iterating the following steps while the ordered list is non-empty;

selecting a parent node from the list; and

partitioning the data objects contained in the parent node into a first child node and a second child node according to a skew factor which represents a maximum imbalance in a number of data objects associated with the first child node and the second child node; and

removing the parent node from the ordered list and adding thereto at least one of the child nodes according to whether they contain more than the predetermined maximum number of the data objects.

30. A program storage device as claimed in claim 29, wherein said step of partitioning comprises the steps of:

ordering centers of the data objects according to a longest dimension in a bounding rectangle corresponding to said parent node;

evaluating all partitions according to the skew factor and for which the number of the centers of the data objects associated with the first child node is a multiple of a predetermined incremental value; and

choosing among said all partitions, one partition associated with bounding rectangles having a smallest total area subject to an overlap factor which constrains an amount of overlap of the bounding rectangles.

31. A program storage device as claimed in claim 30, wherein the predetermined incremental value is one.

32. A program storage device as claimed in claim 30, wherein the predetermined incremental value is equal to the predetermined maximum number of the data objects contained in the leaf node.

33. A program storage device as claimed in claim 30, comprises the steps of:

ordering centers of the data objects according to each dimension in the bounding rectangle corresponding to said parent node; and

said step of choosing among all said partitions is done in said each dimension.

34. A program storage device as claimed in claim 33, wherein said predetermined incremental value is one.

35. A program storage device as claimed in claim 33, wherein said predetermined incremental value is equal to the predetermined maximum number of the data objects in the leaf node.

36. A program storage device as claimed in claim 26, wherein said step of compressing the binary tree further comprises the steps of:

creating and maintaining a list with entries corresponding to non-leaf nodes, in breadth-first order;

iterating the following steps while said ordered list is non-empty;

selecting a parent node from the list;

choosing a child node, associated with the parent node from the list, containing the largest number of data objects and collapsing the child node into the parent node from the list;

removing the parent node from the list and replacing the parent with a revised parent node provided the number of data objects is less than said predetermined maximum number of data objects.

37. A program storage device as claimed in claim 26, comprising the steps of:

finding for each leaf node an ancestor node such that a number of data objects corresponding to said ancestor node is not greater than said predetermined maximum number of data objects but the number of data objects corresponding to a parent of said ancestor node is greater than said predetermined maximum; and

collapsing all non-leaf descendants of said ancestor node into said ancestor node, responsive to said step of constructing a binary tree.