PROCESSING A HIERARCHICAL STRUCTURE TO RESPOND TO A QUERY

• US 20130226966A1
• Filed: 02/27/2013
• Published: 08/29/2013
• Est. Priority Date: 02/27/2012
• Status: Abandoned Application

• Current Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD. (Technion-Israel Institute Of Technology)
• Original Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD. (Technion-Israel Institute Of Technology)
• Inventors: SHMUELI, Oded, Shnaiderman, Lila
• Application Number:
  US13/778,349
• Publication Number:
  US 20130226966A1
• Time in Patent Office: Days
• US Class Current: 707/770
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/8373 Query execution
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A method of processing of processing a hierarchical structure to respond to a query, comprising:

• • a) Providing a hierarchical structure having a plurality of nodes of a plurality of node types.
  • b) Receiving a query that defines a hierarchical query pattern defining hierarchical relationship between at least two query nodes.
  • c) Simultaneously exploring the hierarchical structure in a bottom up manner by a plurality of threads to update a mapping data structure for each hierarchical structure node that has the same node type as a corresponding query node. Each thread updates the mapping data structure for each ancestor node of each node according to a match between each ancestor node and a corresponding parent node of the corresponding query node.
  • d) Simultaneously analyzing the mapping data structure by the plurality of threads to identify at least one portion of the hierarchical structure that matches the hierarchical query pattern.

Claims

1. A method of processing a hierarchical structure to respond to a query, comprising:

providing a hierarchical structure having a plurality of nodes of a plurality of node types;

receiving a query that defines a hierarchical query pattern defining hierarchical relationship between at least two query nodes;

simultaneously exploring said hierarchical structure in a bottom up manner by a plurality of threads to update a mapping data structure for each hierarchical structure node of said plurality of nodes that has the same node type as a corresponding query node of said at least two query nodes; and

simultaneously analyzing said mapping data structure by said plurality of threads to identify at least one portion of said hierarchical structure that matches said hierarchical query pattern;

wherein each said thread updates said mapping data structure for each ancestor node of said each hierarchical structure node according to a match between said each ancestor node and a corresponding parent node of said corresponding query node.

2. The method of claim 1, wherein said plurality of threads are executed simultaneously by a plurality of slave processors.

3. The method of claim 1, wherein said exploring is performed in a plurality of iterations, during each said iteration another subset of said plurality of nodes is explored to update said mapping data structure with respect to another one of said at least two query nodes.

4. The method of claim 1, wherein said analyzing is performed in a plurality of iterations, during each said iteration said mapping data structure is analyzed for a subset of said plurality of nodes with respect to another said query node.

5. The method of claim 1, wherein said plurality of nodes are enumerated prior to said exploration in order to provide positioning information for the plurality of nodes, said positioning information is used by said plurality of threads to navigate through said hierarchical structure.

6. The method of claim 5, wherein said enumeration employs depth first search (DFS) order starting at a root node of said hierarchical structure, during said enumeration said plurality of nodes is assigned with a tree level indication, an opening index and a closing index to identify the exact hierarchical position of each of said plurality of nodes within said hierarchical structure.

7. The method of claim 1, wherein said ancestor include parent nodes.

8. The method of claim 1, further comprising collecting results of said analyzing and outputting a match indication.

9. The method of claim 8, wherein said match indication includes a reference to at least one portion of said hierarchical structure that matches said hierarchical pattern, said portion includes at least one node.

10. The method of claim 1, wherein said hierarchical structure is an extensible markup language (XML) dataset.

11. A system of processing a hierarchical structure to respond to a query using a plurality of slave processors, comprising:

a storage which hosts a hierarchical structure having a plurality of nodes;

a plurality of slave processors executing a plurality of threads; and

a control processor which processes said hierarchical structure to respond to a query by instructing said plurality of threads to explore simultaneously said hierarchical structure and to update a mapping data structure to indicate which of said plurality of nodes has a node type and a set of ancestor nodes that are common with a respective node of said query and analyzing said updated mapping data structure to identify at least one portion of said hierarchical structure that matches with respect to at least one corresponding node of said query;

wherein each of said plurality of threads is exploring and analyzing one of said plurality of nodes at a time.

12. The system of claim 11, wherein said plurality of slave processors is embedded within at least one single instruction multiple data (SIMD) hardware unit.

13. The system of claim 12, wherein said SIMD hardware unit is a graphic processing unit (GPU).

14. The system of claim 11, wherein said plurality of slave processors and said control processor are integrated within the same hardware platform, said platform is sufficient for processing said hierarchical structure.

15. The system of claim 11, wherein said plurality of slave processors includes one or more general purpose processors having at least one processing core.

16. The system of claim 11, wherein said plurality of slave processors includes at least one remote clusters that includes at least one slave processor, said at least one remote clusters communicates with said control processor to synchronize processing said hierarchical structure.

17. A method of creating additional structural hierarchical information of a hierarchical structure with respect to a query, comprising:

constructing a plurality of node type arrays, each said node type array includes a plurality of node entries, each node entry is associated with a one of a plurality of nodes within a hierarchical structure having a common node type; and

updating said node entries with node link information, said link information describes links of each of said plurality of nodes to ancestor nodes.

18. The method of claim 17, wherein said ancestor nodes include parent nodes.

19. The method of claim 17, wherein a single said node type array is assigned to a plurality of leaf nodes in order to reduce memory consumption, said plurality of leaf nodes are sorted within said single node type array in ascending order according to said node type.

20. The method of claim 17, wherein said hierarchical structure is an extensible markup language (XML) dataset.