Parallel processing of data organized in a tree structure

• US 8,370,394 B2
• Filed: 07/14/2010
• Issued: 02/05/2013
• Est. Priority Date: 07/17/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Atta, Islam, El-Shishiny, Hisham
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US12/835,916
• Publication Number:
  US 20110016153A1
• Time in Patent Office: 937 Days
• Field of Search: 707/797
• US Class Current: 707/797
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

A method for parallel processing of data organized in the form of a tree including: converting the tree into a linear array structure including a data array for storing the data of said tree and three reference arrays; determining partial workloads from the linear array structure obtained at step a; and performing parallel processing of said partial workloads. Each entry in the data array corresponding to a given node in the tree and includes three pointers. The pointers each point to a respective one of the reference arrays: a first pointer identifies the parent node of the given node, a second pointer identifies the first child node of the given node, and a third pointer identifies the sibling node of the given node.

Claims

1. A method for parallel processing of data organized in the form of a tree, the method comprising:

converting the tree into a linear array structure including a data array for storing the data of the tree and three reference arrays, wherein each entry in the data array corresponds to a given node in the tree and includes three pointers, with each of the three pointers pointing to a respective one of the three reference arrays, wherein a first one of the pointers identifies a parent node of the given node, a second one of the pointers identifies a first child node of the given node, and a third one of the pointers identifies a sibling node of the given node;

determining partial workloads from the linear array structure; and

performing parallel processing of the partial workloads.

2. The method of claim 1, wherein the data from the tree is stored in the data array using a Polish representation.

3. The method of any preceding claims, wherein the converting of the tree into a linear array structure comprises:

parsing the tree to obtain one or more parsed nodes;

initially setting a current index to zero; and

for each parsed node and for a current index in the data array;

copying the data associated with the parsed node into the data array at the current index;

setting a first reference array at the current index to point to the data array entry corresponding to the parent node of the parsed node in the tree;

if the parsed node has at least one child in the input tree, setting a second reference array at the current index to point to data array value at index (current index+1);

if the parsed node is a sibling to another node in the input tree and if the another node has an index k in the data array, setting a third reference array at index k to point to the data array value at index i; and

incrementing the current index by one.

4. The method of claim 1, wherein:

the determining partial workloads includes dividing the linear data array into equally sized data chunks; and

the performing parallel processing of the partial workload includes processing the data chunks in parallel.

5. The method of claim 1, wherein the determining partial workloads comprises determining lists of sub-trees from the linear array structure, each sub-tree representing a partial workload.

6. The method of claim 5, wherein the determining lists of sub-trees comprises:

defining a root structure representing a candidate sub-tree, the root structure being composed of four pointers pointing respectively to a data node into the data array and to three entries into the three reference arrays;

computing the size of the candidate sub-tree using a third reference array;

determining if the size of the sub-tree matches a predefined condition;

if the size of the sub-tree matches the predefined condition, adding the candidate sub-tree into the list of sub-trees;

setting root to point to its sibling using the third reference array; and

for each new value of root, performing the computing, determining and adding steps.

7. The method of claim 6, further comprising setting root to point to its first child using a second reference array if it is determined that the sub-tree does not match the predefined condition.

8. The method of claim 6, the computing of the size of the candidate sub-tree further comprising setting root to point to its parent sibling using a first reference array if it is determined that root does not have any siblings.

9. The method of claim 6, wherein the determining if the size of the sub-tree matches the predefined condition further comprises comparing the size of the candidate sub-tree added to a number of nodes in the list of sub-trees with available space for partial workload.

10. The method of claim 6, wherein determining partial workload further includes queuing the list of sub-trees for processing.

11. A computer program product comprising a computer readable device having encoded thereon computer program code that when executed of a data processing device performs the method of:

converting data organized in the form of a tree into a linear array structure including a data array for storing the data of the tree and three reference arrays, wherein each entry in the data array corresponds to a given node in the tree and includes three pointers, with each of the three pointers pointing to a respective one of the three reference arrays, wherein a first one of the pointers identifies a parent node of the given node, a second one of the pointers identifies a first child node of the given node, and a third one of the pointers identifies a sibling node of the given node;

determining partial workloads from the linear array structure; and

performing parallel processing of the partial workloads.

12. The computer program product of claim 11, wherein the program code for performing the converting of the tree into a linear array structure further comprises program code for:

parsing the tree to obtain one or more parsed nodes;

initially setting a current index to zero; and

for each parsed node and for a current index in the data array;

copying the data associated with the parsed node into the data array at the current index;

setting a first reference array at the current index to point to the data array entry corresponding to the parent node of the parsed node in the tree;

if the parsed node has at least one child in the input tree, setting a second reference array at the current index to point to data array value at index (current index+1);

if the parsed node is a sibling to another node in the input tree and if the another node has an index k in the data array, setting a third reference array at index k to point to the data array value at index i; and

incrementing the current index by one.

13. The computer program product of claim 11, wherein:

the program code that performs the determining partial workloads includes program code for dividing the linear data array into equally sized data chunks; and

the program code that performs the parallel processing of the partial workload includes program code for processing the data chunks in parallel.

14. The computer program product of claim 11, wherein the program code that performs the determining partial workloads further comprises program code for determining lists of sub-trees from the linear array structure, each sub-tree representing a partial workload, wherein the determining lists of sub-trees comprises:

defining a root structure representing a candidate sub-tree, the root structure being composed of four pointers pointing respectively to a data node into the data array and to three entries into the three reference arrays;

computing the size of the candidate sub-tree using a third reference array;

determining if the size of the sub-tree matches a predefined condition;

if the size of the sub-tree matches the predefined condition, adding the candidate sub-tree into the list of sub-trees;

setting root to point to its sibling using the third reference array; and

for each new value of root, performing the computing, determining and adding steps.

15. The computer program product of claim 14, wherein:

the program code for determining lists of sub-trees from the linear array structure further comprises program code for performing the following functions;

setting root to point to its first child using a second reference array if it is determined that the sub-tree does not match the predefined condition; and

setting root to point to its parent sibling using a first reference array if it is determined that root does not have any siblings;

the program code for determining if the size of the sub-tree matches the predefined condition further comprises program code for comparing the size of the candidate sub-tree added to a number of nodes in the list of sub-trees with available space for partial workload; and

the program code for determining partial workload further includes program code for queuing the list of sub-trees for processing.

16. A data processing system comprising:

a processor;

a storage coupled to the processor; and

program code that executes on the processor that enables the data processing system to;

convert data organized in the form of a tree into a linear array structure including a data array for storing the data of the tree and three reference arrays, wherein each entry in the data array corresponds to a given node in the tree and includes three pointers, with each of the three pointers pointing to a respective one of the three reference arrays, wherein a first one of the pointers identifies a parent node of the given node, a second one of the pointers identifies a first child node of the given node, and a third one of the pointers identifies a sibling node of the given node;

determine partial workloads from the linear array structure; and

perform parallel processing of the partial workloads.

17. The data processing system of claim 16, wherein the program code for performing the converting of the tree into a linear array structure further comprises program code that enables the data processing system to:

parse the tree to obtain one or more parsed nodes;

initially set a current index to zero; and

for each parsed node and for a current index in the data array;

copy the data associated with the parsed node into the data array at the current index;

set a first reference array at the current index to point to the data array entry corresponding to the parent node of the parsed node in the tree;

if the parsed node has at least one child in the input tree, set a second reference array at the current index to point to data array value at index (current index+1);

if the parsed node is a sibling to another node in the input tree and if the another node has an index k in the data array, set a third reference array at index k to point to the data array value at index i; and

increment the current index by one.

18. The data processing of claim 16, wherein:

the program code that performs the determining partial workloads includes program code to divide the linear data array into equally sized data chunks; and

the program code that performs the parallel processing of the partial workload includes program code to process the data chunks in parallel.

19. The data processing system of claim 16, wherein the program code to determine partial workloads further comprises program code to determine lists of sub-trees from the linear array structure, each sub-tree representing a partial workload, wherein the program code to determine lists of sub-trees further comprises program code that enables the data processing system to:

define a root structure representing a candidate sub-tree, the root structure being composed of four pointers pointing respectively to a data node into the data array and to three entries into the three reference arrays;

compute the size of the candidate sub-tree using a third reference array;

determine if the size of the sub-tree matches a predefined condition;

if the size of the sub-tree matches the predefined condition, add the candidate sub-tree into the list of sub-trees;

set root to point to its sibling using the third reference array; and

for each new value of root, perform the compute, determine and add steps.

20. The data processing system of claim 19, wherein:

the program code to determine lists of sub-trees from the linear array structure further comprising program code that enables the data processing system to;

setting root to point to its first child using a second reference array if it is determined that the sub-tree does not match the predefined condition; and

setting root to point to its parent sibling using a first reference array if it is determined that root does not have any siblings;

the program code to determine if the size of the sub-tree matches the predefined condition further comprises program code that enables the data processing system to compare the size of the candidate sub-tree added to a number of nodes in the list of sub-trees with available space for partial workload; and

the program code to determine partial workload further comprises program code that enables the data processing system to queue the list of sub-trees for processing.