Method and system for performing proximity joins on high-dimensional data points in parallel

• US 5,884,320 A
• Filed: 08/20/1997
• Issued: 03/16/1999
• Est. Priority Date: 08/20/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Shafer, John Christopher
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/920,331
• Time in Patent Office: 573 Days
• Field of Search: 707/1, 707/5, 707/10, 707/100-105, 707/200-206, 364/282.1, 706/934
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method and system for performing spatial proximity joins on high-dimensional points representing data objects of a database in parallel in a multiprocessor system. The method comprises the steps of: partitioning the data points among the processors; creating index structures for the data points of the processors in parallel; assigning the join operations to the processors using the index structures; and simultaneously redistributing and joining the data points in the processors in parallel based on a predetermined joining condition. An efficient data structure, ε-K-D-B tree, is used to provide fast access to the high-dimensional points and to minimize system storage requirements. The invention achieves fast response time and requires minimum storage space by having structurally identical indices among the processors, assigning workload based on the join costs, and redistributing the data points among the processors while joining the data whenever possible.

Claims

1. A method for performing proximity join operations on high-dimensional data points in parallel in a multiprocessor system, the join operations being based on a similarity distance between any two data points, the method comprising the steps of:

partitioning the data points among the processors;

creating an index structure for the data points of each processor, the index structure having a plurality of leaf nodes each corresponding to a subset of the data points;

assigning the join operations to the processors using the index structures; and

simultaneously redistributing and joining the data points in the processors in parallel based on a predetermined joining condition.

2. The method as recited in claim 1, wherein the step of assigning the joint operations includes the steps of:

determining a cost for each join operation; and

assigning the join operations to the processors based on the determined costs of the join operations.

3. The method as recited in claim 2, wherein the step of determining a cost for each join operation includes the steps of:

traversing the index structures to determine a global size for each leaf node; and

estimating the cost from the global sizes of the leaf nodes involved in the join operation.

4. The method as recited in claim 1, wherein:

the index structure is a multi-dimensional ε

-K-D-B tree having a root node branching into a plurality of interior nodes, the tree terminating with the leaf nodes; and

the joining condition is such that the similarity distance between any two data points to be joined is at most ε

.

5. The method as recited in claim 4, wherein the step of creating an index structure includes the step of splitting each leaf node, in at least one dimension of the tree, into .left brkt-bot.1/ε

.right brkt-bot. child nodes whenever the number of points in the leaf node exceeds a predetermined value, each child node having a width greater than ε

in the dimension used for splitting.

6. The method as recited in claim 5, wherein:

each leaf node of the ε

-K-D-B tree has a depth equal to one plus the number of interior nodes between the root node and leaf node; and

the step of splitting a leaf node is based on the depth of the leaf node.

7. The method as recited in claim 5, wherein the step of splitting a leaf node includes determining an order of the dimensions used for splitting based on any correlation among the dimensions such that a dimension selected for splitting next has the least correlation with previously selected dimensions.

8. The method as recited in claim 7, wherein:

the multi-dimensional ε

-K-D-B trees for all the processors are structurally identical; and

the processors have the same order of the dimensions used for splitting the leaf nodes.

9. The method as recited in claim 5, further comprising the steps of:

sorting the data points of each leaf node using a dimension not used for splitting the leaf nodes as a common sort dimension; and

for each pair of leaf nodes from which data points are to be joined, sort-merging the data points associated with the pair based on the common sort dimension.

10. The method as recited in claim 1, further comprising the step of communicating the index structure by each processor to the other processors.

11. The method as recited in claim 1, further comprising the step of broadcasting asynchronously, by each processor to the other processors, as to which leaf nodes in the index structure of the processor have recently been split.

12. The method as recited in claim 1, further comprising the step of distributing the data points asynchronously among the processors so that each processor has all the data points for the joint operations assigned to the processor.

13. The method as recited in claim 12, wherein the step of distributing includes the step of sending the data points, by each processor to the other processors, in a depth-first order using the index structure of the processor.

14. The method as recited in claim 12, further comprising the step of deleting a leaf node in each processor if the leaf node is no longer needed for the join operations assigned to the processor.

15. The method as recited in claim 1, wherein the step of joining the data points includes the steps of:

each processor first joining the leaf nodes for which the processor has received the data points needed for the joint operations assigned to the processor; and

deleting those leaf nodes and data points from which the join operations have been performed by the processor.

16. The method as recited in claim 1, wherein the step of assigning the join operations includes the step of traversing the respective index structure for each processor to determine the join operations that will be performed by the processor.

17. The method as recited in claim 16, wherein:

the index structure is a tree structure having a root node branching into a plurality of child nodes and terminating with the leaf nodes; and

the method further includes the step of joining a first node and a second node, the step of joining a first node and a second node including the steps of;

a) if the first and second nodes are both leaf nodes, then selecting the first and second nodes for joining;

b) if the first node is a leaf node and the second node is not a leaf node, then joining the first node with each child node of the second node; and

c) if neither the first nor the second node is a leaf node, then;

i) joining each n-th child node of the first node with a corresponding n-th child node of the second node, n being from 1 to F, where F is the number of child nodes from each node of the tree except the leaf nodes;

ii) joining each n-th child node of the first node with an (n+1)-th child is node of the second node, n being from 1 to F-1; and

iii) joining each n-th child node of the second node with an (n+1)-th child node of the first node, n being from 1 to F-1.

18. A computer program product for use with a multiprocessor system for directing the system to perform proximity joins on high-dimensional data points in parallel in the processors, the computer program product comprising:

a computer readable medium;

means, provided on the computer-readable medium, for directing the system to partition the data points among the processors;

means, provided on the computer-readable medium, for directing the system to create an index structure for the data points in each processor, the index structure having a plurality of leaf nodes each corresponding to a subset of the data points;

means, provided on the computer-readable medium, for directing the system to assign the join operations to the processors using the index structures; and

means, provided on the computer-readable medium, for directing the system to simultaneously redistribute and join the data points in the processors in parallel, based on a predetermined joining condition.

19. The computer program product as recited in claim 18, wherein the means for directing to assign the joint operations includes:

means, provided on the computer-readable medium, for directing the system to determine a cost for each join operation; and

means, provided on the computer-readable medium, for directing the system to assign the join operations to the processors based on the determined costs of the join operations.

20. The computer program product as recited in claim 19, wherein the means for directing to determine a cost for each join operation includes:

means, provided on the computer-readable medium, for directing each processor to traverse the respective index structure to determine a global size for each leaf node; and

means, provided on the computer-readable medium, for directing the processor to estimate the cost from the global sizes of the leaf nodes involved in the join operation.

21. The computer program product as recited in claim 18, wherein:

the index structure is a multi-dimensional ε

-K-D-B tree having a root node branching into a plurality of interior nodes, the tree terminating with the leaf nodes; and

the joining condition is such that the similarity distance between any two data points to be joined is at most ε

.

22. The computer program product as recited in claim 21, wherein the means for directing to create an index structure includes means, provided on the computer-readable medium, for directing each processor to split each leaf node of the respective structure, in at least one dimension of the tree, into .left brkt-bot.1/ε

.right brkt-bot. child nodes whenever the number of points in the leaf node exceeds a predetermined value, each child node having a width greater than ε

in the dimension used for splitting.

23. The computer program product as recited in claim 22, wherein:

each leaf node of the ε

-K-D-B tree has a depth equal to one plus the number of interior nodes between the root node and leaf node; and

the splitting of a leaf node is based on the depth of the leaf node.

24. The computer program product as recited in claim 22, wherein the means for directing to split a leaf node includes means, provided on the computer-readable medium, for directing the processor to determine an order of the dimensions used for splitting based on any correlation among the dimensions, such that a dimension selected for splitting next has the least correlation with previously selected dimensions.

25. The computer program product as recited in claim 24, wherein:

the multi-dimensional ε

-K-D-B trees for all the processors are structurally identical; and

the processors have the same order of the dimensions used for splitting the leaf nodes.

26. The computer program product as recited in claim 22, further comprising:

means, provided on the computer-readable medium, for directing each processor to sort the data points of each respective leaf node using a dimension not used for splitting the leaf nodes as a common sort dimension; and

for each pair of leaf nodes from which data points are to be joined, means, provided on the computer-readable medium, for directing the processor to sort-merge the data points associated with the pair based on the common sort dimension.

27. The computer program product as recited in claim 18, further comprising means, provided on the computer-readable medium, for directing each processor to communicate the index structure created by the processor to the other processors.

28. The computer program product as recited in claim 18, further comprising means, provided on the computer-readable medium, for directing each processor to broadcast asynchronously to the other processors as to which leaf nodes of the processor have recently been split.

29. The computer program product as recited in claim 18, further comprising means, provided on the computer-readable medium, for directing the system to distribute the data points asynchronously among the processors so that each processor has all the data points for the joint operations assigned to the processor.

30. The computer program product as recited in claim 29, wherein the means for directing to distribute includes means, provided on the computer-readable medium, for directing each processor to send the data points to the other processors in a depth-first order using the index structure of the processor.

31. The computer program product as recited in claim 29, further comprising means, provided on the computer-readable medium, for directing each processor to delete a leaf node in the processor if the leaf node is no longer needed for the join operations assigned to the processor.

32. The computer program product as recited in claim 18, wherein the means for directing to join the data points includes:

means, provided on the computer-readable medium, for directing each processor to first join the leaf nodes for which the processor has received the data points needed for the joint operations assigned to the processor; and

means, provided on the computer-readable medium, for directing the processor to delete those leaf nodes and data points from which the join operations have been performed by the processor.

33. The computer program product as recited in claim 18, wherein the means for directing to assign the join operations includes means, provided on the computer-readable medium, for directing each processor to traverse the respective index structure to determine the join operations that will be performed by the processor.

34. The computer program product as recited in claim 33, wherein:

the index structure is a tree structure having a root node branching into a plurality of child nodes and terminating with the leaf nodes; and

the computer program product further comprises means, provided on the computer-readable medium, for directing each processor to join a first node and a second node, the means for directing to join a first node and a second node including;

a) means, provided on the computer-readable medium, for directing the processor to select the first and second nodes for joining if the first and second nodes are both leaf nodes;

b) means, provided on the computer-readable medium, for directing the processor to join the first node with each child node of the second node if the first node is a leaf node and the second node is not a leaf node; and

c) if neither the first nor the second node is a leaf node, then;

i) means, provided on the computer-readable medium, for directing the processor to join each n-th child node of the first node with a corresponding n-th child node of the second node, n being from 1 to F, where F is the number of child nodes from each node of the tree except the leaf nodes;

ii) means, provided on the computer-readable medium, for directing the processor to join each n-th child node of the first node with an (n+1)-th child node of the second node, n being from 1 to F-1; and

iii) means, provided on the computer-readable medium, for directing the processor to join each n-th child node of the second node with an (n+1)-th child node of the first node, n being from 1 to F-1.

35. A database system for performing proximity joins on high-dimensional points in parallel in a multiprocessor computer, comprising:

means for partitioning the data points among the processors;

means, in each processor, for creating an index structure for the data points of the processor, the index structure having a plurality of leaf nodes each corresponding to a subset of the data points;

means for assigning the join operations to the processors using the index structures; and

means, in each processor, for simultaneously redistributing and joining the data points in the processors in parallel based on a predetermined joining condition.

36. The system as recited in claim 35, wherein the means for assigning the joint operations includes:

means for determining a cost for each join operation; and

means for assigning the join operations to the processors based on the determined cost of the join operations.

37. The system as recited in claim 36, wherein the means for determining a cost for each join operation includes:

means for traversing the index structures in each processor to determine a global size for each leaf node; and

means for estimating the cost from the global sizes of the leaf nodes involved in the join operation.

38. The system as recited in claim 35, wherein:

the index structure is a multi-dimensional ε

-K-D-B tree having a root node branching into a plurality of interior nodes, the tree terminating with the leaf nodes; and

the joining condition is such that the similarity distance between any two data points to be joined is at most ε

.

39. The system as recited in claim 38, wherein the means for creating an index structure includes means for splitting each leaf node, in at least one dimension of the tree, into .left brkt-bot.1/ε

.right brkt-bot. child nodes whenever the number of points in the leaf node exceeds a predetermined value, each child node having a width greater than ε

in the dimension used for splitting.

40. The system as recited in claim 39, wherein:

each leaf node of the ε

-K-D-B tree has a depth equal to one plus the number of interior nodes between the root node and leaf node; and

the splitting a leaf node is based on the depth of the leaf node.

41. The system as recited in claim 39, wherein the means for splitting a leaf node includes means for determining an order of the dimensions used for splitting based on any correlation among the dimensions such that a dimension selected for splitting next has the least correlation with previously selected dimensions.

42. The system as recited in claim 41, wherein:

the multi-dimensional ε

-K-D-B trees for all the processors are structurally identical; and

the processors have the same order of the dimensions used for splitting the leaf nodes.

43. The system as recited in claim 39, further comprising:

means, in each processor, for sorting the data points of each leaf node using a dimension not used for splitting the leaf nodes as a common sort dimension; and

for each pair of leaf nodes from which data points are to be joined, means in each processor for sort-merging the data points associated with the pair based on the common sort dimension.

44. The system as recited in claim 35, further comprising means for communicating, by each processor to the other processors, the index structure created by the processor.

45. The system as recited in claim 35, further comprising means for broadcasting asynchronously, by each processor to the other processors, as to which leaf nodes of the processor have recently been split.

46. The system as recited in claim 35, further comprising means for distributing the data points asynchronously among the processors so that each processor has all the data points for the joint operations assigned to the processor.

47. The system as recited in claim 46, wherein the means for distributing includes means for sending the data points, by each processor to the other processors, in a depth-first order using the index structure of the processor.

48. The system as recited in claim 46, further comprising means for deleting a leaf node in each processor if the leaf node is no longer needed for the join operations assigned to the processor.

49. The system as recited in claim 35, wherein the means for joining the data points includes:

means for first joining the leaf nodes for which the processor has received the data points needed for the joint operations assigned to the processor; and

means for deleting those leaf nodes and data points from which the join operations have been performed by the processor.