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

Claim 3

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.

Claim 4

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.

Claim 5

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 ε.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.

Claim 21

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.

Claim 22

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.

Claim 23

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 ε.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.

Claim 35

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.

Claim 36

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.

Claim 37

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.

Claim 38

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.

Claim 39

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.

Claim 40

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.

Claim 41

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 ε.

Claim 42

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.

Claim 43

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.

Claim 44

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.

Claim 45

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.

Claim 46

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.

Claim 47

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.

Claim 48

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.

Claim 49

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.

Claim 50

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.

Claim 51

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.

Claim 52

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.