Source: http://www.google.com/patents/US7627604?dq=7800613
Timestamp: 2017-04-29 02:24:42
Document Index: 474143941

Matched Legal Cases: ['art 1', 'art 2', 'art 3', 'art 4', 'art 5', 'art 6', 'art 7', 'art 8', 'art 1', 'art 2']

Patent US7627604 - Method for handling tree-type data structure, information processing device ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsIt is possible to express a tree-type data structure so as to effectively trace the relationship between data in the tree-type data structure (for example, parent-child, ancestor, descendant, brothers, generations). In the tree-type data structure, for each of non root nodes which are the nodes excluding...http://www.google.com/patents/US7627604?utm_source=gb-gplus-sharePatent US7627604 - Method for handling tree-type data structure, information processing device, and programAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7627604 B2Publication typeGrantApplication numberUS 10/599,043PCT numberPCT/JP2005/004190Publication dateDec 1, 2009Filing dateMar 10, 2005Priority dateMar 16, 2004Fee statusPaidAlso published asUS20080270435, WO2005088479A1Publication number10599043, 599043, PCT/2005/4190, PCT/JP/2005/004190, PCT/JP/2005/04190, PCT/JP/5/004190, PCT/JP/5/04190, PCT/JP2005/004190, PCT/JP2005/04190, PCT/JP2005004190, PCT/JP200504190, PCT/JP5/004190, PCT/JP5/04190, PCT/JP5004190, PCT/JP504190, US 7627604 B2, US 7627604B2, US-B2-7627604, US7627604 B2, US7627604B2InventorsShinji FurushoOriginal AssigneeTurbo Data Laboratories, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (18), Non-Patent Citations (4), Referenced by (10), Classifications (15), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethod for handling tree-type data structure, information processing device, and program
US 7627604 B2Abstract
It is possible to express a tree-type data structure so as to effectively trace the relationship between data in the tree-type data structure (for example, parent-child, ancestor, descendant, brothers, generations). In the tree-type data structure, for each of non root nodes which are the nodes excluding the root node, their parent nodes are correlated so that the parent-child relationship between the nodes is expressed by using “child->parent” relationship. Accordingly, by specifying a child node, it is possible to promptly specify the only one parent node corresponding to the child node.
The present invention relates to a method of treating a tree type data structure, and particularly to a method of expressing a tree type data structure, building the tree type data structure on a storage device or changing the tree type data structure. Furthermore, the invention relates to an information processing device for carrying out the method. Still furthermore, the invention relates to a program for executing the method and a recording medium having the program recorded therein.
A database is used in various kinds of applications, and a relational database (RDB) from which logical inconsistency can be excluded has been mainly used in a medium-scale or large-scale system. For example, RDB is used in systems for airplane seat reservation, etc. In this case, by indicating a key item, a target (one target in many cases) can be quickly searched for, or a reservation can be settled, canceled or changed. Furthermore, each airplane has several hundreds seats at most, and thus the number of empty seats of a specific airplane can be determined.
However, treatment of the tree type data structure, for example, search of tree type data generally has a very low efficiency. A first reason for the low efficiency resides in the fact that data exist in distributed nodes at various locations, and thus it is difficult to quickly specify the location at which data exists. In RDB, for example, data of “age” are stored in only an item of “age” of some tables. However, in the tree type data structure, nodes for holding data of “age” are scattered at various locations, and thus it is general that the corresponding data cannot be searched for unless the overall tree type data structure is checked.
As an approach to the method of constructing XML data in the form of a database while keeping its form, a copy of data written in a tree structure is taken out, and for example in the case of an item “age”, index data for searching for “age” are separately held (for example, see patent document 2). Accordingly, the merit of XML data that an attribute can be added to the data itself can be sufficiently actively used, and the relational structure of the respective items expressed by using tags can be directly stored.
[Non-patent Document 1] SEC Co., Ltd., “Karearea White Paper”, [online], [searched on Feb. 19, 2004], Internet <URL:http://wwww.sec.co.jp/products/karearea/>
[Non-patent Document 2] W3C, “Extensible Markup Language (XML)) 1.0 (Third Edition)”, [online], Feb. 4, 2004, [searched on Feb. 19, 2004], Internet <URL:http://www.w3.org/TR/2004/REC-xml-20040204/>
Actually, even when a search is actually carried out to specify a node, it takes much time to express the node. Furthermore, this mechanism is unusable for a search in terms of a relationship between nodes (for example, extraction of a tree containing “age” of “sixty years old” for an ancestor node and containing “age” of “one year old” for a descendent node).
In order to attain the above object, the principle of the invention resides in that the parent-child relationship between nodes building a tree type data structure is expressed not by a “parent→child” relationship which associates a parent node with a child node, but by a “child→parent” relationship which associates the child node with the parent node.
When the parent-child relationship is expressed by the “parent→child” relationship, the parent-child relationship cannot be defined unless two elements of the parent node and the child node are specified because there is a case where a plurality of child nodes is associated with one parent node. That is, even when the parent node is specified, the child nodes having the parent-child relationship with the parent node cannot be specified.
On the other hand, when the parent-child relationship is expressed by the “child→parent” relationship, one child node has necessarily a unique parent node, and thus by specifying the child node, the unique parent node corresponding to the child node can be quickly specified.
Therefore, according to the invention, a method of expressing a parent-child relationship between nodes constituting a tree type data structure on a storage device, the parent-child relationship between the nodes is expressed by associating non-root nodes corresponding to the nodes other than a root node with the parent node of each non-root node. Accordingly, topology of a tree can be expressed by tracking a list including the child nodes and the parent nodes expressed by the “child→parent” relationship.
a parent-child relationship defining step of associating the node identifiers assigned to non-root nodes corresponding to the nodes other than the root node with the node identifier assigned to parent nodes of the non-root nodes. As described above, the node identifier is first provided to the node by any identification information such as a character string, a floating point number, an integer or the like, and then the parent-child relationship is defined on the basis of the “child→parent” expression, whereby the node identifier of the parent node is drawn (looked up) from the node identifier of the child node, whereby topology of a tree can be expressed.
Accordingly, the sequential integers are assigned to the nodes in the depth-first, and the parent-child relationship among the nodes is expressed by the array of the “child→parent” relationship. Therefore, there is achieved an excellent property that when the parent-child relationship among the nodes to which the sequential numbers are assigned in the depth-first is expressed by the array on the basis of the “child→parent” relationship, descendant nodes of a given node appear in a continuous region.
a parent-child relationship definition step of storing into the storage device an array formed by arranging, in the order of integers assigned to non-root node corresponding to nodes other than the root node, integers assigned to parent nodes of the respective non-root nodes. Accordingly, the sequential integers are assigned to the nodes in the width-first mode, and the parent-child relationship of the nodes is expressed by the array of the “child→parent” relationship. There is achieved an excellent property that when the parent-child relationship of nodes to which sequential numbers are assigned in the width-first mode is represented by the array based on the “child→parent” relationship, the numbers assigned to the parent nodes appear in a given order (ascending order or descending order) in the array.
a step of storing in the storage device an array of numbers assigned to child nodes corresponding to parent nodes in the order of numbers assigned to the parent nodes concerned when the parent-child expression mode is selected. Accordingly, the parent-child relationship among nodes expressed by the “child→parent” can be expressed by the “parent→child” relationship. The expression based on the “parent→child” relationship is advantageous when information is exchanged with the external.
As described above, the “child→parent” expression and the “parent→child” expression to express the parent-child relationship and the depth-first mode and the width-first mode to assign numbers to nodes can be selectively used as the expression form of the tree type data structure. Therefore, the invention provides a method for the mutual conversion between different expression forms.
a step of converting the parent-child relationship of each node to the parent-child relationship expressed by the numbers assigned in the width-first mode by using the conversion array. Accordingly, the “child→parent” expression form based on the depth-first mode can be converted to the “child→parent” expression form based on the width-first mode.
a step of converting the parent-child relationship of each node to the parent-child relationship expressed by the numbers assigned in the depth-first mode by using the conversion array. Accordingly, the high-speed conversion from the “child→parent” expression form based on the width-first mode to the “child→parent” expression form based on the depth-first mode can be performed.
a step of converting the parent-child relationship of the respective nodes to parent-child relationship expressed by numbers assigned in the depth-first mode by using the conversion array. Accordingly, the search-based conversion from the “child→parent” expression form based on the width-first mode to the “child→parent” expression form based on the depth-first mode can be performed. The “depth-first” search is implemented by creating a number conversion array by using stack.
a step of successively reading out the elements of the first array, and successively storing the numbers of the child nodes for the elements of the first array as the elements of the second array secured for the nodes to which numbers having the values coincident with the elements concerned are assigned. Accordingly, the parent-child relationship is converted form the “child→parent” expression form to the “parent→child” expression form. That is, the parent-child relationship after the conversion is defined by storing in the storage device the numbers assigned to the child nodes corresponding to parent nodes as the elements of the second array in the order of assigning the numbers to the parent nodes.
a step of successively reading out the elements of the first array and successively storing the numbers of the parent nodes for the elements of the first array as elements of second array secured for nodes to which numbers having values coincident with the elements are assigned. Accordingly, the parent-child relationship is converted from the “parent→child” expression form to the “child→parent” expression form. That is, the parent-child relationship after the conversion is defined by storing the numbers assigned to the parent nodes corresponding to child nodes in the order of numbers assigned to the child nodes concerned as elements of the second array in the storage device.
According to the invention, the parent-child relationship among the nodes of the tree type data structure is described on the basis of the “child→parent” expression, and thus the parent-child relationship can be defined by providing one storage place to one node. Accordingly, the amount of the memory accessed when the tree type data structure is operated is reduced, and thus the operation can be performed at high speed.
Still furthermore, according to the “child→parent” expression of the invention, by assigning numbers to nodes in the width-first mode, child nodes derived from some node can be easily searched for.
Furthermore, according to the “child→parent” expression of the invention, by assigning numbers to nodes in the depth-first mode, the blocks of the descendant nodes of some node can be easily specified.
Embodiments according to the invention will be hereunder described with reference to the accompanying drawings.
FIGS. 2A, B are diagrams showing POS data which is an example of the tree type data. FIG. 2A shows an example in which the data structure of the tree type data (that is, topology) and data values are visually expressed, and FIG. 2B shows an example in which the same tree type data are expressed in the form of XML. As shown in FIGS. 2A and 2B, the tree data structure is expressed by a combination of nodes and arcs which start from a root node (POS data in this embodiment), branch at each node and reach leaf nodes (terminal points). A storage place for a substantial value of each node, for example, the value of a shop name node=“France shop” is indicated by a pointer relating to the shop name node.
[Expression Based on “Child→Parent” Relationship]
In the example of FIGS. 3A to C, the arc list is described on the basis of the “parent→child” relationship for associating the child node with the parent node. Therefore, since one parent node, for example, a root node 0, has three child nodes 10, 60 and 80, the same node ID of 0 appears three times at From-ID of the arc list. That is, the child node cannot be specified even when the parent node is specified, and thus the arc list is constructed by the array of elements From-Id and the array of elements To-ID. When the arc list is used, some nodes appear in both the array of From-ID and the array of To-ID.
On the other hand, the parent-child relationship can be expressed on the basis of the “child→parent” relationship. In this case, the parent-child relationship between nodes is expressed by an array of pairs of respective non-root nodes other than the root node and associated parent nodes. When the parent-child relationship is expressed on the basis of the “child→parent” relationship, there is an important property which is not achieved in the case of the “parent→child” relationship. That is, a unique parent node necessarily corresponds to one child node, and thus by specifying a child node, the unique parent node corresponding to the child node concerned can be immediately specified. That is, it is actually sufficient only to prepare the array of elements To-ID for the ark list. As a result, the storage capacity for storing the arc list can be reduced. The reduction of the storage capacity brings an effect of reducing the frequency of access to the memory, so that the processing speed can be increased.
FIGS. 4A to C are diagrams showing a method of expressing a tree data structure on the basis of the “child→parent” relationship according to an embodiment of the invention. FIG. 4A is a diagram showing the overall tree, and FIG. 4B shows an arc list based on the “child→parent” relationship. The arc list shown in FIG. 4B contains a storage area of the parent node corresponding to a root node, and thus “-” is conveniently set as the parent node of the root node. However, the parent corresponding to the root node does not exist, and thus the storage area of the parent node corresponding to the root node may be excluded from the arc list based on the “child→parent” relationship as shown in FIG. 4C. As described above, according to the embodiment of the invention, with respect to each of non-root nodes which correspond to nodes other than the root node, the parent node of each non-root node is associated with each of the non-root nodes to express the parent-child relationship between the nodes. A list of parent nodes is tracked from the child nodes expressed by “child→parent”, whereby the topology of the tree can be expressed.
According to the embodiment of the invention, as shown in FIG. 5, the tree data structure based on the “child→parent” relationship as described above is built on RAM 14 by causing the computer system 10 shown in FIG. 1 to execute a node definition step 501 for assigning unique node identifiers to nodes including a root node, and a parent-child relationship definition step 502 for associating node identifiers assigned to the non-root node corresponding to nodes other than the root node with the node identifier assigned to parent nodes of the respective non-root nodes. As described above, a node identifier is first assigned to a node by any identification information such as a character string, a floating point number, an integer or the like, and then the parent-child relationship is defined on the basis of the “child→parent” expression, whereby the topology of the tree can be expressed by drawing (looking up) the node identifier of the parent node from the node identifier of the child node.
As described above, when the numbers are used as the node identifiers as described above, an address at which a storage value relating to a node is stored can be immediately looked up from the node number of the node concerned, that is, in the order of O(1). Furthermore, by expressing the parent-child relationship on the basis of the “child→parent”, the parent node can be looked up from the child node immediately, that is, in the order of O(1).
Accordingly, the sequential numbers are assigned to the nodes in the depth-first mode, and the parent-child relationship between nodes is expressed by the array of the “child→parent” relationship.
FIG. 9 is a diagram showing the array of the parent-child relationship based on the “child→parent” expression created from the tree data structure based on the depth-first shown in FIGS. 6A to C according to the embodiment of the invention. As shown as a sub tree 1 or sub tree 2 in FIG. 9, there is achieved an excellent property that when the parent-child relationship of nodes to which the sequential numbers are assigned in the depth-first mode is expressed by the array on the basis of the “child→parent” relationship, descendants nodes of some node appear in sequential areas.
As described above, the parent-child relationship between nodes can be also expressed by the array of the “parent child” relationship in place of the array of the “child→parent” relationship. FIG. 10 is a diagram showing the array of the parent-child relationship based on the “parent→child” expression crated from the depth-first tree data structure shown in FIGS. 6A to C. Since one parent node can have plural child nodes, and thus the array of the parent-child relationship comprises two arrays consisting of an array Aggr for indicating areas in which the numbers of child nodes corresponding to each node are stored, and an array P→C in which the numbers of the child nodes are stored. For example, the value of a second element Aggr[1] from the head of the array Aggr is equal to “3”, and this represents that the numbers of child nodes corresponding to the node [1] are stored in the element P→C [3] and subsequent elements of the array P→C. Accordingly, it is found that the child nodes corresponding to the node [0], that is, the root node are three elements from the head of the array P→C, that is, 1 of P→C[0], 6 of P→C[1] and 8 of P→C[2].
A method of determining the array of the parent-child relationship based on the “parent→child” expression will be described.
Or, the parent-child relationship based on the expression “parent→child” can be expressed by two arrays, that is, the array of the parent node numbers and the array of the corresponding child node numbers. However, in order to find out the parent-child relationship by using this array, the number of the parent node must be searched, that is, the access time of log(n) is required, and thus the efficiency is low.
Accordingly, sequential integers are assigned to the nodes in the width-first mode, and the parent-child relationship between nodes is expressed by the array of the “child→parent” relationship.
FIG. 12 is a diagram showing the array of the parent-child relationship based on the “child→parent” expression created from the width-first tree data structure shown in FIGS. 7A to C according to the embodiment of the invention. As shown in FIG. 12, when the parent-child relationship of nodes to which sequential numbers are assigned in the width-first mode is expressed in the array on the basis of the “child→parent” relationship, there is achieved an excellent property that the child nodes of some node appear in sequential areas. This is because when the parent-child relationship of nodes to which sequential numbers are assigned in the width-first mode is expressed in the array on the basis of the “child→parent” relationship, the number assigned to the parent node appears in an order style (ascending order or descending order) in the array.
As described above, the parent-child relationship between nodes can be expressed not only by the array of the “child→parent” relationship, but also by the array of the “parent→child” relationship. FIG. 13 is a diagram showing the array of the parent-child relationship based on the “parent→child” expression created from the width-first tree data structure shown in FIGS. 7A to C. Since one parent node may have plural child nodes, the array of the parent-child relationship comprises two arrays consisting of an array Aggr indicating areas in which the numbers of child nodes for each node are stored, and an array P→C in which the numbers of the child nodes are stored. For example, the value of the second element Aggr [1] from the head of the array Aggr is equal to “3”, and this represents that the numbers of child nodes for the node [1] are stored in the element P→C[3] and the subsequent elements of the array P→C. Accordingly, it is found that the child nodes for the node [0], that is, the root node are three elements from the head of the array P→C, 1 of P→C[0], 2 of P→C[1] and 3 of P→C[2].
As described above, each of the depth-first mode and the width-first mode has an inherent excellent property. Therefore, the computer system of the embodiment of the invention converts the mutual expression form among the “child→parent” expression form based on the depth-first, the “child→parent” expression form based on the width-first and the “parent→child” expression form. FIG. 14 is a diagram showing the relationship of the mutual conversion of the three expression form according to the embodiment of the invention.
Accordingly, the parent-child relationship among the nodes expressed by the “child→parent” relationship can be expressed by the “parent→child” relationship in accordance with the condition. The expression based on the “parent→child” relationship is advantageous to information exchange with the external, for example.
As described above, according to the embodiment of the invention, the “child→parent” expression and the “parent→child” expression for expressing the parent-child relationship, and the depth-first mode and the width-first mode for assigning numbers to nodes can be selectively used. A mutual conversion method of different expression forms will be described hereunder.
[Conversion from the Depth-First “Child→Parent” Expression to the Width-First “Child→Parent” Expression]
FIGS. 16A, B are diagrams showing the conversion from the depth-first “child→parent” expression (FIG. 16A) to the width-first “child→parent” expression (FIG. 16) according to the embodiment of the invention. FIG. 17 is a flowchart showing the conversion method from the depth-first “child→parent” expression to the width-first “child→parent” expression according to the embodiment of the invention. The parent-child relationship is defined by storing the numbers assigned to the parent nodes corresponding to child nodes in the order of numbers assigned to the child nodes concerned into a storage device of the computer system 10, for example, RAM 14.
a step of 1704 of converting the parent-child relationship of the respective nodes to a parent-child relationship expressed by the numbers assigned in the width-first mode by using the conversion array. Accordingly, it is possible to convert the “child→parent” expression form based on the depth-first mode to the “child→parent” expression form based on the width-first mode.
In the step 1701, the number of nodes of each generation is counted. FIGS. 18A to 22 are diagrams showing the processing of counting the number of nodes belonging to each generation of the tree data structure based on the depth-first according to the embodiment of the invention. First, as shown in the procedure 0 of FIG. 18A, two conversion arrays are prepared. An array “depth” for storing the generation of each node has the same size as the array “C→P”. An array “depth-count” for storing the number of nodes of each generation has a proper size which is equal to or more than the number of stages of the tree structure, and it is initialized to zero. In the procedure 1 of FIG. 18B, starting the head element (specifically, the root node), the generation (depth) of the nodes is determined and the number of elements belonging to the generation of the element concerned, that is, the head element of the array “depth-count” is incremented by only 1. With respect to the node 0, the generation thereof is equal to 0, so that 0 is set to “depth” [0] and “depth-count” [0] is incremented from 0 to 1. In the figure, the number of a target node is indicted by a bold type. In the procedure 2 of FIG. 18C, the number of the parent node corresponding to the node 1 is achieved from the array “C→P” to investigate the generation of the parent node. The element of the array “C→P”[1] is equal to zero, and when “depth” [0] is referred to, the element thereof is equal to zero (indicated by an italic type in the figure), so that it is found that the generation of the parent node is equal to zero. The value of the generation of the node 1 is achieved by adding the value of the generation of the parent node with 1, and thus it is equal to the value of the generation of the parent node +1=1. Therefore, the value 1 of the generation is set to the array “depth” [1], and the element of the array “depth-count” [1] is incremented by only 1.
Procedure 3: Since the next C→P element is equal to 1, “depth” [1] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to 1, “depth” of the node concerned is equal to 1+1=>2. Therefore, “depth” (=2) of the node concerned is stored in “depth” [2]. Finally, “depth-count” [“depth” of the node concerned] is incremented.
Procedure 4: Since the next C→P element is equal to 2, “depth” [2] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to 2, the “depth” of the node concerned is equal to 2+1=>3. Therefore, “depth” (=3) of the node concerned is stored in “depth” [3]. Finally, “depth-count” [the “depth” of the node concerned] is incremented.
Procedure 5: Since the next C→P element is equal to 2, “depth” [2] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to 2, the “depth” of the node concerned is equal to 2+1=>3. Therefore, the “depth” (=3) of the node concerned is stored in “depth” [4]. Finally, “depth-count” [the “depth” of the node concerned] is incremented.
Procedure 6: Since the next C→P element is equal to 1, “depth” [1] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to 1, the “depth” of the node concerned is equal to 1+1=>2. Therefore, the “depth” (=2) of the node concerned is stored in “depth” [5]. Finally, “depth-count” (the “depth” of the node concerned) is incremented.
Procedure 7: Since the next C→P element is equal to zero, “depth” [0] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to zero, the “depth” of the node concerned is equal to 0+1=>1. Therefore, the “depth” (=1) of the node concerned is stored in “depth” [6]. Finally, “depth-count” [the “depth” of the node concerned] is incremented.
Procedure 8: Since the next C→P element is equal to 6, “depth” [6] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to 1, the “depth” of the node concerned is equal to 1+1=>2. Therefore, the “depth” (=2) of the node concerned is stored in “depth” [7]. Finally, “depth-count” [the “depth” of the node concerned] is incremented.
Procedure 9: Since the next C→P element is equal to zero, “depth” [0] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to zero, the “depth” of the node concerned is equal to 0+1=>1. Therefore, the “depth” (=1) of the node concerned is stored in “depth” [8]. Finally, “depth-count” [the “depth” of the node concerned] is incremented.
Procedure 10: Since the next C→P element is equal to 8, “depth” [8] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to zero, the “depth” of the node concerned is equal to 1+1=>2. Therefore, the “depth” (=2) of the node concerned is stored in “depth” [9]. Finally, “depth-count” (the “depth” of the node concerned) is incremented.
Procedure 11: Since the next C→P element is equal to 9, “depth” [9] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to 2, the “depth” of the node concerned is equal to 2+1=>3. Therefore, the “depth” (=3) of the node concerned is stored in “depth” [10]. Finally, “depth-count” {the “depth” of the node concerned} is incremented.
Procedure 12: Since the next C→P element is equal to 9, “depth” [9] (corresponding to the “depth” of the parent) is referred to. Since the “depth” of the parent is equal to 2, the “depth” of the node concerned is equal to 2+1=>3. Therefore, the “depth” (=3) of the node concerned is stored in “depth” [11]. Finally, “depth-count” [the “depth” of the node concerned] is incremented.
Accordingly, the array “depth” and the array “depth-counter” as shown in FIG. 23 are achieved.
Next, in the step 1702, the elements of the array “depth-count” in which the number of nodes of each generation is stored are accumulated (that is, the number of the nodes is counted). For example when the values of elements of the array (1, 3, 4, 4, 0) are accumulated,
Accordingly, the array becomes (1, 4, 8, 12, 12). As is apparent from this accumulation, the number of nodes till the generation 0 is equal to 1, the number of nodes till the generation 1 is equal to 4, the number of nodes till the generation 2 is equal to 8, the number of nodes till the generation 3 is equal to 12, and the number of nodes till the generation 4 is equal to 12. When the nodes are arranged in the generation order from this state, it is found that the head node of the generation 0 is 0th as a whole, the head node of the generation 1 is a first node, the head node of the generation is a fourth node as a whole, the head node of the generation 3 is an eighth node as a whole, and the head node of the generation 4 is a twelfth node as a whole. As described above, by accumulating the elements of the array “depth-count” of the number of the nodes of each generation, an array “depth-aggr” indicating what number node the head node of each generation is as a whole when the nodes are arranged in the generation order is achieved. In a preferable embodiment, the array “depth-aggr” is not directly equal to (1, 4, 8, 12, 12), but it is equal to an array (0, 1, 4, 8, 12) achieved by filling 0 to the head and displacing the elements backward one by one. The array “depth-aggr” represents numbers assigned in each generation when the numbers are assigned in the width-first mode.
In the step 1703, the conversion array is created. FIGS. 24A to 28 are diagrams showing the processing of creating the conversion array for converting the numbers of nodes to numbers assigned in the width-first mode according to the embodiment of the invention. First, as shown in the procedure 0 of FIG. 24A, an area for a number conversion definition array [Conversion definition of “No.”], that is, an integer array having the same size as the array C→P is reserved. Subsequently, in the procedure 1 of FIG. 24B, the generation of node 0, that is, the “depth” [0] is taken out, and the element 0 of the element “depth-aggr” [0] of the array “depth-aggr” indicated by the value 0 of the “depth” [0] is taken out. This value 0 represents the number assigned in the generation 0. By setting this value 0 to the element of the array [Conversion definition of “No.”] corresponding to the node 0, it is found that the node 0 to which the number is assigned in the depth-first mode is converted to the node 0 when the numbers are assigned in the width-first mode.
In the procedure 2 of FIG. 24C, the number conversion definition of the node 1 is carried out. Therefore, the “depth” [1] representing the generation of the node 1 is taken out, and the value 1 of the “depth-aggr”[1] indicated by the value 1 of the “depth” [1] is taken out. This value 1 is set to the array [Conversion definition of “No.”] [1], and the value of the “depth-aggr”[1] is incremented by only 1. The element of the “depth-aggr”[1] from which the element is taken out is incremented by only 1, whereby when the node of the generation 1 is selected, the number of the node concerned after the conversion is equal to a number larger than the number 1 after the conversion by only 1, that is, equal to 2.
For example, in the procedure 3, the “depth” [2] is taken out, and the element of the “depth-aggr” indicated by the value is taken out. The element corresponding to the taken-out “depth-aggr” is stored in the [Conversion definition of “No.”] and also it is incremented by only 1 and stored in “depth-aggr”. In the procedures 4 to 12, “depth” [3] to “depth” [11] are taken out, and the element of “depth-aggr” indicated by the value concerned is taken out. The corresponding element of the taken-out “depth-aggr” is stored in [Conversion definition of “No.”] and also it is incremented by only 1 and stored in “depth-aggr”.
Accordingly, the final array [Conversion definition of “No.”] as shown in FIG. 28 is achieved.
IN step 1704, the parent-child relationship of respective nodes is converted to the parent-child relationship expressed by numbers assigned in the width-first mode by using the conversion array. FIG. 29 is a diagram showing the processing of converting the parent-child relationship of the “child→parent” expression form based on the depth-first mode to the “child→parent” expression form based on the width-first mode according to the embodiment of the invention. For example, when the child node C and the parent node P are associated with each other in the “child→parent” expression form based on the depth-first mode, if the node number C is converted to the node number C′ and the node number P is converted to the node number P′ by the final number conversion definition array [Conversion definition of “No.”], the child node C′ and the parent node P′ are associated with each other in the “child→parent” expression form based on the width-first mode. If the number C′ of the child node after the conversion and the number P′ of the parent node after the conversion are achieved for all the child nodes C before the conversion, the array C′→P′ of the parent-child relationship in which the storage position is represented by C′ and the storage value is represented by P′ is completed.
In the example of FIG. 29, the storage positions (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) are converted to (0, 1, 4, 8, 9, 5, 2, 6, 3, 7, 10, 11) by using the array of [Conversion definition of “No.”]. Accordingly, as shown in FIG. 29, the array C→P after the conversion of the storage position is as follows:
the value −1 of the array C→P [0] based on the depth-first is set to the array C→P [0] after the conversion of the storage position; the value 0 of the array C→P [1] based on the depth-first is set to the array CUP [1] after the conversion of the storage position; the value 0 of the array C→P [6] based on the depth-first is set to the array C→P [2] after the conversion of the storage position; the value 0 of the array C→P [8] based on the depth-first is set to the array C→P [3] after the conversion of the storage position; the value 1 of the array C→P [2] based on the depth-first is set to the array C→P [4] after the conversion of the storage position; the value 1 of the array C→P [5] based on the depth-first is set to the array C→P [5] after the conversion of the storage position; the value 6 of the array C→P [7] based on the depth-first is set to the array C→P [6] after the conversion of the storage position; the value 8 of the array C→P [9] based on the depth-first is set to the array C→P [7] after the conversion of the storage position; the value 2 of the array C→P [3] based on the depth-first is set to the array C→P [8] after the conversion of the storage position; the value 2 of the array C→P [4] based on the depth-first is set to the array C→P [9] after the conversion of the storage position; the value 9 of the array C→P [10] based on the depth-first is set to the array C→P [10] after the conversion of the storage position; and the value 9 of the array C→P [11] based on the depth-first is set to the array C→P [11] after the conversion of the storage position. Subsequently, the value of each element of the array C→P after the conversion of the storage position is converted by using the array of [Conversion definition of “No.”], thereby achieving the C→P array after the conversion of the storage value.
In the example of FIG. 29, the conversion of the storage position, that is, the conversion of the child node number is first carried out, and then the conversion of the storage value, that is, the conversion of the parent node number is carried out. However, the conversion of the storage position may be carried out after the conversion of the storage value is first carried out. Alternatively, both the conversion of the storage position and the conversion of the storage value may be carried out at the same time. The node number “−1” representing the parent node of the root node is not required to be converted.
Through the above processing, the conversion from the depth-first “child→parent” expression to the width-first “child→parent” expression as show in FIGS. 16A, B is carried out.
[High-Speed Conversion from the Width-First “Child→Parent” Expression to the Depth-First “Child→Parent” Expression]
FIGS. 30A, B are diagrams showing the conversion from the width-first “child→parent” expression (FIG. 30A) to the depth-first “child→parent” expression (FIG. 30B) according to the embodiment of the invention. FIG. 31 is a flowchart showing the method for the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression according to the embodiment of the invention. The parent-child relationship is defined by storing, in the order of the numbers assigned to the child nodes, the numbers assigned to the parent nodes corresponding to the child nodes in the storage device of the computer system 10, for example, RAM 14. As shown in FIG. 13, the computer system 10 executes:
a step 3103 of converting the parent-child relationship of each node to the parent-child relationship expressed by the numbers assigned in the depth-first mode. Accordingly, the high-speed conversion from the “child→parent” expression form based on the width-first mode to the “child→parent” expression form based on the depth-first mode can be performed.
In step 3103, the parent-child relationship of the respective nodes is converted to the parent-child relationship expressed by the numbers assigned in the depth-first mode by using the conversion array. FIG. 35 is a diagram showing the processing of converting the parent-child relationship of the “child→parent” expression form based on the width-first mode to the parent-child relationship of the “child→parent” expression form based on the depth-first mode. This processing is the same processing as described with reference to FIG. 29. For example, when the child node C and the parent node P are associated with each other in the “child→parent” expression form based on the width-first mode, the node number C is converted to the node number C′ by the above conversion array (Conversion definition of “No.”), and if the node number P is converted to the node number P′, the child node C′ and the parent node P′ are associated with each other in the “child→parent” expression form based on the depth-first mode. If the number C′ of the child node after the conversion and the number P′ of the parent node after the conversion are achieved for all the child nodes C before the conversion, the array C′→P′ of the parent-child relationship in which the storage position is represented by C′ and the storage value is represented is completed.
In the example of FIG. 35, the conversion of the storage position, the conversion of the child node number is first carried out, and then the conversion of the storage value, that is, the conversion of the parent node number is carried out. However, the storage position may be converted after the storage value is first converted, or both the conversion of the storage position and the conversion of the storage value may be performed simultaneously. It is unnecessary to convert the node number “−1” representing the route node.
Through the above processing, the high-speed conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression as shown in FIGS. 30A and B can be performed.
[Conversion from Width-First “Child→Parent” Expression to the Depth-First “Child→Parent” Expression]
According to the embodiment of the invention, the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression may be implemented by a conversion method using searching in addition to the high-speed conversion method described with reference to FIGS. 30A to 35. In the following description, this conversion method using the search will be described by using an example shown in FIGS. 30A and B.
The parent-child relationship based on the width-first “child→parent” expression is defined by storing, in the order of the numbers assigned to the child nodes, the numbers assigned to the parent nodes corresponding to the child nodes in the storage device of the computer system 10, that is, RAM 14. The computer 10 executes:
FIGS. 36 and 43B are diagrams showing a conversion method from the width-first “child→parent” expression to the depth-first “child→parent” expression. In the conversion based on the search from the “child→parent” expression form based on the width-first mode to the “child→parent” expression form based on the depth-first mode, the “depth-first” search is implemented by creating a number conversion array by using stack, for example.
Subsequently, the expression of the parent-child expression is converted by the completely same processing as the processing of converting the parent-child relationship of the “child→parent” expression form based on the width-first mode to the parent-child relationship of the “child→parent” expression form based on the depth-first mode according to the embodiment of the invention described with reference to FIG. 35.
[Conversion from “Child→Parent” Expression to “Parent <Child” Expression]
Next, the conversion method from the “child→parent” relationship for associating the parent node with the child node to the “parent→child” relationship for associating the child node with the parent node will be described.
FIG. 44 is a flowchart showing the conversion method from the “child→parent” expression to the “parent→child” expression according to the embodiment of the invention. The parent-child relationship is defined by storing, in the order of the numbers assigned to the child node, the numbers of the parent nodes corresponding to the child nodes in the storage device of the computer system 10, that is, RAM 14. The computer system 10 executes:
a step 4403 of successively reading out the elements of the first array and successively storing the numbers of the child nodes for the elements of the first array as elements of the second array secured for the nodes to which the numbers coincident with the values of the elements are assigned. Accordingly, the parent-child relationship is converted from the “child-parent” expression form to the “parent-child” expression form. That is, the parent-child relationship after the conversion is defined by storing the numbers assigned to the child nodes corresponding to a parent node as the elements of the second array in the storage device in the order of the numbers assigned to the parent node concerned.
According to this conversion method, the depth-first or width-first property is directly preserved. Therefore, the “child→parent” expression based on the depth-first mode is converted to the “parent→child” expression based on the depth-first mode, and the “child →parent” expression based on the width-first mode is converted to the “parent→child” expression based on the width-first mode. FIG. 45A to C are diagrams showing an example of the tree data structure based on the depth-first mode. FIG. 45A shows the overall tree data structure, FIG. 45B shows the parent-child relationship based on the “child→parent” expression form, and FIG. 45C shows the parent-child relationship based on the “parent→child” expression form. In this embodiment, the expression form as shown in FIG. 45B is converted to the expression form as shown in FIG. 45C.
FIGS. 46A to 47C are diagrams showing a method for the conversion from the “child→parent” expression based on the depth-first mode to the “parent→child” expression based on the depth-first mode according to the embodiment of the invention.
In the procedure 1 of FIG. 46A, areas for storing the parent-child relationship of the “parent→child” expression form after the conversion are first secured, and initialized. As described above, in the case of the “parent→child” expression form, the array Aggr and array P→C are prepared. The array Aggr is an array for indicating areas in which the numbers of child nodes corresponding to each node are stored, and the array P→C is an array for storing the numbers of the child nodes. The size of the array Aggr is equal to the size of the arrangement C→P (of the “child→parent” expression form), and the arrangement Aggr is initialized to zero. The size of the arrangement P→C may be set to be smaller than the arrangement Aggr by the amount corresponding to one element. It is unnecessary to initialize the array P→C, however, in FIG. 46A, it is initialized to −1 in order to make the understanding easy.
FIG. 47C shows the array Aggr and the array P→C achieved through the conversion. These arrays is the same as the array of the parent-child relationship based on the depth-first “parent→child” relationship shown in FIG. 10, and thus the further description is not added.
In the conversion method, as described above, the depth-first or width-first property is directly preserved. Accordingly, the conversion method according to the embodiment of the invention is suitable for the conversion from the “child→parent” expression based on the width-first mode to the “parent→child” expression based on the width-first mode.
[Conversion from “Parent→Child” Expression to “Child→Parent” Expression]
Next, a method of the conversion from “parent→child” relationship for associating the child node with the parent node to the “child→parent” relationship for associating the parent node with the child node according to the embodiment of the invention will be described.
FIG. 48 is a flowchart showing the method for the conversion from the width-first “child→parent” expression from the depth-first “child→parent” expression according to the embodiment of the invention. The parent-child relationship is defined by storing, in the order of the numbers assigned to the parent nodes, the numbers assigned to the child nodes to the parent node as elements of a first array in the storage device of the computer system 10, for example, RAM 14. The computer 10 executes:
a step 4802 of successively reading out the elements of the first array, and successively storing the numbers of the parent nodes to the elements of the first array as the elements of the second array secured for the nodes to which the numbers having values coincident with the elements concerned are assigned. Accordingly, the parent relationship is converted from the “parent→child” expression form to the “child→parent” expression form. That is, the parent-child relationship after the conversion is defined by storing the numbers assigned to the parent nodes corresponding to child nodes in the order of the numbers assigned to the child nodes concerned as the elements of the second array into the storage device.
According to this method, the depth-first or width-first property can be directly preserved. Therefore, the “parent→child” expression based on the depth-first mode is converted to the “child→parent” expression based on the depth-first mode, and the “parent→child” expression based on the width-first mode is converted to the “child→parent” based on the width-first mode. In the following description, an example of the conversion from the parent→child” expression based on the depth-first mode to the “child→parent” expression based on the depth-first will be described. In this example, with respect to the tree data structure based on the depth-first mode shown in FIGS. 45A to C, the parent-child relationship based on the “parent→child” expression form shown in FIG. 45C is converted to the parent-child relationship based on the “child→parent” expression form shown in FIG. 45B.
FIGS. 49A to C are diagrams showing a method for the conversion from the “parent→child” expression based on the depth-first mode to the “child→parent” expression based on the depth-first mode according to the embodiment of the invention.
Subsequently, as shown in the procedure 2-1 of FIG. 49B and the procedure 2-2 of FIG. 49C, “parent→child” relationship is read out from the array Aggr and the array P→C, and the child node numbers of the corresponding C→P are filled. For example, the element (=0) of the subscript 0 of the array represents the head of the area in the array P→C in which the child nodes of the parent node 0 are stored, and the element (=3) of the subscript 1 of the array Aggr represents the head of the area in the array P→C where the child nodes of the parent node 1 are stored. Therefore, it is found that the node numbers of the child nodes of the parent node 0 are stored in the area from the subscript 0 to the subscript 2 of the array P→C. Since 1, 6 and 8 are stored in this order as child node numbers in this area, the node number 0 of the parent node 0 is set as the elements of the subscripts 1, 6 and 8 of the array C→P. Accordingly, the area of the child nodes for which the node of the node number 0 corresponds to the parent node is embedded in the array C→P. This process is successively executed in the order of subscripts of the array Aggr, thereby achieving a final result shown in FIG. 49D.
According to the conversion method, as described above, the depth-first or width-first property is directly preserved. Accordingly, the conversion method according to the embodiment of the invention is suitable for the conversion from the “parent→child” expression based on the width-first mode to the “child→parent” expression based on the width-first mode.
FIG. 1 is a block diagram showing a computer system for treating a tree data structure according to an embodiment of the invention.
FIGS. 4A to C are diagrams showing an expression method for the tree data structure based on “child→parent” relationship according to the embodiment of the invention.
FIG. 9 is a diagram showing the array of parent-child relationship based on the “child→parent” expression created according to the embodiment of the invention.
FIG. 10 is a diagram showing the array of the parent-child relationship based on the “parent-child” expression created from the tree data structure based on the depth-first shown in FIGS. 6A to C.
FIG. 12 is a diagram showing the array of the parent-child relationship based on the “child→parent” expression created according to the embodiment of the invention.
FIG. 13 is a diagram showing the array of the parent-child relationship based on the “parent→child” expression created from the tree data structure based on depth-first shown in FIGS. 7A to C.
FIGS. 16A, B are diagrams showing the conversion from the depth-first “child→parent” expression to the width-first “child→parent” expression according to the embodiment of the invention.
FIG. 17 is a flowchart showing the method of the conversion from the depth-first “child→parent” expression to the width-first “child→parent” expression according to the embodiment of the invention.
FIGS. 30A, B are diagrams of the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression according to the embodiment of the invention.
FIG. 31 is a flowchart showing the method of the conversion from the width-first “child→parent” expression to the depth-first “child→parent” according to the embodiment of the invention.
FIG. 36 is a diagram (part 1) of the method of conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression according to the embodiment of the invention.
FIGS. 37A to C are diagrams (part 2) of the method of the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression according to another embodiment of the invention.
FIGS. 38A to C are diagrams (part 3) showing the method of the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression according to another embodiment of the invention.
FIGS. 39A to C are diagrams (part 4) showing the method of the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression according to another embodiment of the invention.
FIGS. 40A to C are diagrams (part 5) of the method of the conversion from the width-first “child→parent” expression to the depth “child→parent” expression according to another embodiment of the invention.
FIGS. 41A to C are diagrams (part 6) of the method for the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression according to another embodiment of the invention.
FIGS. 42A to C are diagrams (part 7) of the method for the conversion from the width-first “child→parent” expression to the depth-first “child→parent” expression.
FIGS. 43A, B are diagrams (part 8) of the method for the conversion from the width-first “child→parent” expression to the depth-first “child→parent” according to another embodiment of the invention.
FIG. 44 is a flowchart showing the method for the conversion from the “child→parent” expression to the “parent→child” expression according to the embodiment of the invention.
FIGS. 46A to C are diagrams (part 1) showing the method of the conversion from the “child→parent” expression based on the depth-first mode to the “parent→child” expression based on the depth-first mode according to the embodiment of the invention.
FIGS. 47A to C are diagrams (part 2) of the method for the conversion from the “child→parent” expression based on the depth-first mode to the “parent→child” expression based on the depth-first mode.
FIG. 48 is a flowchart showing the method for the conversion from the “parent→child” expression to the “child→parent” expression according to the embodiment of the invention.
FIGS. 49A to D are diagrams showing the method for the conversion from the “parent→child” expression based on the depth-first to the “child→parent” expression based on the depth-first mode according to the embodiment of the invention.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4868743 *Nov 23, 1987Sep 19, 1989Hitachi, Ltd.Traversal method of processing tree structure information and apparatus using the sameUS5727195 *Apr 14, 1995Mar 10, 1998Fuji Xerox Co., Ltd.Document retrieving object instructing apparatusUS5995952 *Oct 10, 1996Nov 30, 1999Fujitsu LimitedNeural network for providing hints to problem solving apparatus using tree search methodUS6006027 *Aug 20, 1997Dec 21, 1999Synopsys, Inc.Method and apparatus for event simulationUS6029170 *Nov 25, 1997Feb 22, 2000International Business Machines CorporationHybrid tree array data structure and methodUS6081624 *Jun 1, 1998Jun 27, 2000Autodesk, Inc.Spatial index compression through spatial subdivision encodingUS6219833 *Dec 11, 1998Apr 17, 2001Hewlett-Packard CompanyMethod of using primary and secondary processorsUS6279007 *Nov 30, 1998Aug 21, 2001Microsoft CorporationArchitecture for managing query friendly hierarchical valuesUS6389416 *Feb 19, 1999May 14, 2002International Business Machines CorporationDepth first method for generating itemsetsUS6509898 *Apr 17, 1998Jan 21, 2003Xerox CorporationUsage based methods of traversing and displaying generalized graph structuresUS6567815 *Aug 1, 2000May 20, 2003International Business Machines CorporationTechnique of clustering and compaction of binary treesUS6904423 *Feb 18, 2000Jun 7, 2005Bioreason, Inc.Method and system for artificial intelligence directed lead discovery through multi-domain clusteringUS6931418 *Mar 26, 2002Aug 16, 2005Steven M. BarnesMethod and system for partial-order analysis of multi-dimensional dataJP2000099226A Title not availableJP2001195406A Title not availableJP2003248615A Title not availableJPH10240741A Title not availableJPH11327993A Title not available* Cited by examinerNon-Patent CitationsReference1International Search Report issued in corresponding application No. PCT/JP2005/004190, completed Apr. 8, 2005 and mailed Apr. 26, 2005.2SEC Co., Ltd., "Karearea White Paper", [online], [searched on Feb. 19, 2004], Internet , printed Sep. 12, 2006.3Sedgwich, R., Algorithm vol. 1=Kiso Seiretsu, first edition, Kindai Kagaku Sha, 1990, pp. 39-55.4W3C, "Extensible Markup Language (XML)) 1.0 (Third Edition)", [online], Feb. 4, 2004, [searched on Feb. 19, 2004], Internet , printed Sep. 12, 2006.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8726034 *Aug 28, 2009May 13, 2014Brown UniversityCryptographic accumulators for authenticated hash tablesUS8943045 *Jan 28, 2009Jan 27, 2015Oracle International CorporationMechanisms for efficient autocompletion in XML search applicationsUS9081755 *Apr 7, 2006Jul 14, 2015France TelecomMethod for processing a data tree structureUS9098725 *Feb 26, 2014Aug 4, 2015Brown UniversityCryptographic accumulators for authenticated hash tablesUS20090063519 *Apr 7, 2006Mar 5, 2009Cotarmanac H AlexandreMethod for Processing a Data Tree StructureUS20090259616 *Apr 14, 2008Oct 15, 2009Sandeep ChowdhuryStructure-position mapping of xml with variable-length dataUS20100191721 *Jan 28, 2009Jul 29, 2010Oracle International CorporationMechanisms For Efficient Autocompletion In XML Search ApplicationsUS20110225429 *Aug 28, 2009Sep 15, 2011Charalampos PapamanthouCryptographic accumulators for authenticated hash tablesUS20140245006 *Feb 26, 2014Aug 28, 2014Brown UniversityCryptographic accumulators for authenticated hash tablesWO2012034477A1 *Aug 29, 2011Mar 22, 2012Tencent Technology (Shenzhen) Company LimitedMethod and device for data storage* Cited by examinerClassifications U.S. Classification1/1, 707/999.107, 707/999.104, 707/999.003, 707/999.103, 707/999.01International ClassificationG06F17/30, G06F7/00, G06F17/00Cooperative ClassificationY10S707/99944, Y10S707/99948, Y10S707/99945, G06F17/30961, Y10S707/99933European ClassificationG06F17/30Z1TLegal EventsDateCodeEventDescriptionJun 20, 2008ASAssignmentOwner name: TURBO DATA LABORATORIES, INC., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:FURUSHO, SHINJI;REEL/FRAME:021128/0242Effective date: 20060927Mar 12, 2013FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services