Coupled node tree splitting/conjoining method and program

• US 20090234802A1
• Filed: 05/27/2009
• Published: 09/17/2009
• Est. Priority Date: 11/28/2006
• Status: Active Grant

• Current Assignee: Kousokuya, Inc.
• Original Assignee: S Grants Company Limited
• Inventors: Shinjo, Toshio, Kokubun, Mitsuhiro
• Granted Patent: US 8,224,861 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

The minimum value or the maximum value of the index keys of a coupled node tree of a processing source is determined, and the index keys are successively deleted until the index key that is to be the splitting point is reached, the deleted index keys being inserted into the coupled node tree of the processing target, thereby splitting the coupled node tree. Deletion processing is done of one coupled node tree, taking as the processing source in the above-noted splitting method, and insertion processing is done of the other, taken as the processing target, thereby conjoining the coupled node trees.

Claims

1. A coupled node tree splitting method comprising:

preparing step that prepares a coupled node tree used which is in a bit string search and comprises a root node and a node pair, the node pair being a branch node and a leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein

the root node is a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree,

the branch node includes a discrimination bit position of a search key with which a bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes an index key that is a bit string that is the target of a search, and wherein

repeating linkage, at the branch node, to a primary node or a node at a position in a memory area adjacent thereto of a node pair of the link target from an arbitrary node of the tree as a searching start node in accordance with a bit value of a search key of a discrimination bit position included in the branch node, until the leaf node is reached, an index key stored in the leaf node is made a search result key, which is a search result using the search key of an arbitrary subtree having the searching start node as its root node;

a step of obtaining a split key that establishes an index key that splits a processing source coupled node tree that is to be split;

a processing source minimum value or maximum value obtaining step that determines a minimum value or a maximum value of the index keys of the processing source coupled node tree;

a comparing step of comparing the split key with either the minimum value or the maximum value and, if the minimum value is larger than the split key or if the maximum value is smaller than the split key, ending processing;

a generating step of, if the result of the comparison is that the minimum value is not larger than the split key or the maximum value is not smaller than the split key, inserting the minimum value or the maximum value index key, so as to generate a new processing target coupled node tree;

a deleting step of deleting the minimum value or maximum value index key from the processing source coupled node tree; and

wherein

by making the processing source coupled node tree from which has been deleted the minimum value or maximum value index key into a new processing source coupled node tree,

the processing source minimum value or maximum value obtaining step,

the comparing step,

the generating step,

and the deleting step

are repeated until the minimum value or maximum value obtained by the processing source minimum value or maximum value obtaining step becomes larger than or smaller than the split key respectively.

2. A coupled node tree splitting method according to claim 1, wherein the minimum value or maximum value obtaining step is a step that determines the minimum value or the maximum value of the index keys of the processing source coupled node tree by linking to only the primary node of the two nodes forming the node pair or to only the node located in a memory area adjacent thereto of the node pair respectively, with the root node of the processing source coupled node tree as the searching start node, until a leaf node is reached.

3. A coupled node tree splitting method according to claim 2, wherein the coupled node tree is stored in an array, and the position information is an array element number of an array element of the array in which a node corresponding to the position information is stored,

the array element number of the array element in which the searching start node is stored and the array element numbers of the array elements in which is stored the link target from the searching start node up until the leaf node are successively held in a stack, wherein

the generating step includes a step that

sets the minimum value or maximum value determined by the processing source minimum value or maximum value obtaining step as the insertion key of the processing target coupled node tree,

executes a processing target maximum value or minimum value obtaining step that obtains the maximum value or the minimum value of the index key of the processing target coupled node tree,

performs a bit string comparison between the insertion key and the maximum value or the minimum value of the index key to determine a highest order bit position at which a bit value differs,

establishes, from the relative position relationship between the highest order bit position and a discrimination bit position of the branch node of the array element number stored in the stack, a processing target parent node that is the insertion position of a node pair that includes the leaf node that holds the insertion key, and

stores the array element number of the array element into which is stored the primary node of a node pair that includes the leaf node holding the insertion key into the position information of the processing target parent node.

4. A coupled node tree splitting method according to claim 3, wherein

the generating step includes a further step for setting the processing target parent node as an inserted node into which the leaf node including the insertion key is inserted,

and wherein the processing target maximum value or minimum value obtaining step obtains the maximum value or the minimum value of the index keys of the processing target coupled node tree with the inserted node as the searching start node.

5. A coupled node tree splitting method according to claim 4, wherein

the deleting step includes a step that

sets as a deletion node of the processing source coupled node tree the leaf node that includes the minimum value or the maximum value determined by the processing source minimum value or maximum value obtaining step as the index key,

stores the contents of the node forming the same node pair with the deletion node into the branch node of the link source of that node pair, and

deletes the node pair.

6. A program that a computer is caused to execute, for performing the coupled node tree splitting method according to claim 1.

7. A computer-readable storage medium storing the program according to claim 6.

8. A coupled node tree conjoining method comprising:

preparing step that prepares two coupled node trees each of which is used in a bit string search and comprises a root node and a node pair, the node pair being a branch node and leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein

the root node is a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree,

the branch node includes a discrimination bit position of a search key with which a bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes an index key that is a bit string that is the target of a search, and wherein

repeating linkage, at the branch node, to a primary node or a node at a position in a memory area adjacent thereto of a node pair of the link target from an arbitrary node of the tree as a searching start node in accordance with a bit value of a search key of a discrimination bit position included in the branch node, until the leaf node is reached, an index key stored in the leaf node is made a search result key, which is a search result using the search key of an arbitrary subtree having the searching start node as its root node;

a processing source minimum value or maximum value obtaining step that determines a minimum value or a maximum value of the index keys of a processing source coupled node tree, that is, one of the two coupled node trees;

an inserting step that inserts the minimum value or the maximum value into a processing target coupled node tree, that is, other coupled node tree of the two coupled node trees;

a deleting step that deletes the minimum value or the maximum value from the processing source coupled node tree; and

wherein

by making the processing source coupled node tree from which has been deleted the minimum value or maximum value index key into a new processing source coupled node tree,

the processing source minimum value or maximum value obtaining step,

the inserting step, and the deleting step

are repeated until the processing source coupled node tree is completely deleted.

9. A coupled node tree conjoining method according to claim 8, wherein

the coupled node tree is stored in an array, and the position information is an array element number of an array element of the array in which a node corresponding to the position information is stored,

the array element number of an array element in which the searching start node is stored and the array element numbers of the array elements in which is stored the link target from the searching start node up until the leaf node are successively stored in a stack, wherein

the inserting step includes a step that

sets the minimum value or the maximum value as the insertion key of the processing target coupled node tree,

executes a processing target maximum value or minimum value obtaining step that obtains a maximum value or a minimum value of the index keys of the processing target coupled node tree,

performs a bit string comparison between the insertion key and the maximum value or the minimum value of the index keys of the processing target coupled node tree and determines a highest order bit position at which a bit value differs,

establishes a parent node, which is an insertion point of a node that includes a leaf node holding the insertion key, from the relative positional relationship between the highest order bit position and the discrimination bit position of the branch node of the array element number stored in the stack, and

stores the array element number of the array element into which is stored the primary node of a node pair that includes the leaf node holding the insertion key into the position information of the parent node.

10. A coupled node tree conjoining method according to claim 9, wherein the deleting step includes a step that

sets the leaf node that includes the minimum value or the maximum value obtained by the processing source minimum value or maximum value obtaining step as a deletion node of the processing source coupled node tree and

stores the contents of the node forming the same pair with the deletion node into the branch node of a link source of that node pair, and

deletes the node pair.

11. A program that a computer is caused to execute, for performing the coupled node tree conjoining method according to claim 8.

12. A computer-readable storage medium storing the program according to claim 11.

13. A coupled node tree splitting method comprising:

preparing step that prepares a coupled node tree which is used in a bit string search and comprises a root node and a node pair, the node pair being a branch node and a leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein

the root node is a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree,

the branch node includes a discrimination bit position of a search key with which a bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes an index key that is a bit string that is the target of a search, and wherein

repeating linkage, at the branch node, to a primary node or a node at a position in a memory area adjacent thereto of a node pair of the link target from an arbitrary node of the tree as a searching start node in accordance with a bit value of a search key of a discrimination bit position included in the branch node, until the leaf node is reached, an index key stored in the leaf node is made a search result key, which is a search result using the search key of an arbitrary subtree having the searching start node as its root node;

a step of obtaining a split key that splits a processing source coupled node tree that is to be split;

a split node obtaining step that determines a split node, which is the root node of a largest subtree of processing source subtrees having the split key as a maximum value or a minimum value;

a generating step that generates a new processing target coupled node tree by inserting a split node tree that is a subtree having the split node as the root node; and

a deleting step that deletes the split node tree from the processing source coupled node tree.

14. A coupled node tree splitting method according to claim 13, wherein

the split node obtaining step performs a search with the root node of the processing source coupled node tree as the searching start node using the split key as the search key, and obtains as the split node a branch node on a linking path from the root node up until the split key, with no leaf node that includes an index key that is larger than the split key existing among all of the link target nodes from the branch node or with no leaf node that includes an index key that is smaller than the split key existing among all of the link target nodes from the branch node, and that is also highest order on the coupled node tree among such branch nodes.

15. A coupled node tree splitting method according to claim 14, further comprising:

a next split node obtaining step of obtaining as a next split node a node that forms a node pair with a branch node on a linking path from the root node to the split node, with no leaf node that includes an index key that is larger than the split key existing among all of nodes that is lower order on the coupled node tree from that node or with no leaf node that includes an index key that is smaller than the split key existing among all of nodes that is lower order on the coupled node tree from that node, and that is also highest order on the coupled node tree among such nodes,

wherein

the generating step and deleting step are executed using the next split node as the split node.

16. A coupled node tree splitting method according to claim 15, wherein the coupled node tree is stored in an array and the position information is an array element number of an array element of the area in which the node corresponding to the position information is stored, and

the array element number of the array element in which the searching start node is stored and the array element numbers of the array elements in which the link target from the searching start node up until the leaf node is stored are successively stored in a stack.

17. A coupled node tree splitting method according to claim 16, wherein

the split node obtaining step successively reads out the array element numbers stored in the stack up until the array element number of an array element in which the coupled node indicator is stored or up until the array element number of the array element in which a node forming a pair with the coupled node indicator is stored, the node stored in the array element having the read-out array element number of the array element in which the coupled node indicator is stored or the array element number of the array element in which the node forming a pair with the coupled node indicator is stored being obtained as the split node

18. A coupled node tree splitting method according to claim 17, wherein

the next split node obtaining step successively reads out array element numbers stored before the array element number of the array element in which the split node is stored until reaching the array element number of the array element in which a node forming a pair with the coupled node indicator is stored or until reaching the array element number of the array element in which the coupled node indicator is stored, the read-out array element number of the array element in which the node forming a pair with the coupled node indicator is stored or the array element number of the array element in which the coupled node indicator is stored being obtained as the next split node.

19. A program that a computer is caused to execute, for performing the coupled node tree splitting method according to claim 13.

20. A computer-readable storage medium storing the program according to claim 19.

21. A coupled node tree conjoining method comprising:

preparing step that prepares two coupled node trees each of which is used in a bit string search and comprises a root node and a node pair, the node pair being a branch node and leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein

the root node is a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree,

the branch node includes a discrimination bit position of a search key with which a bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes an index key that is a bit string that is the target of a search, and wherein

repeating linkage, at the branch node, to a primary node or a node at a position in a memory area adjacent thereto of a node pair of the link target from an arbitrary node of the tree as a searching start node in accordance with a bit value of a search key of a discrimination bit position included in the branch node, until the leaf node is reached, an index key stored in the leaf node is made a search result key, which is a search result using the search key of an arbitrary subtree having the searching start node as its root node;

a processing source maximum value or minimum value obtaining step that determines a maximum value or a minimum value of the index keys of a processing source coupled node tree, that is, one of two coupled node trees;

a processing target minimum value or maximum value obtaining step that determines a minimum value or a maximum value of the index keys of a processing target coupled node tree, that is, another of two coupled node trees;

a difference bit position obtaining step that determines a difference bit position between the maximum value of the index keys of the processing source coupled node tree determined by the processing source maximum value or minimum value obtaining step and the minimum value of the index keys of the processing target coupled node tree determined by the processing target minimum value or maximum value obtaining step or between the minimum value of the index keys of the processing source coupled node tree determined by the processing source maximum value or minimum value obtaining step and the maximum value of the index keys of the processing target coupled node tree determined by the processing target minimum value or maximum value obtaining step;

a split/conjoin node obtaining step that determines a split/conjoin node, which is the root node of a subtree that is to be split from the processing source coupled node tree and conjoined to the processing target coupled node tree, based on the difference bit position obtained by the difference bit position obtaining step;

a conjoining position obtaining step that determines a processing target conjoining position for conjoining the split/conjoin node determined by the split/conjoin node obtaining step, based on the difference bit position determined by the difference bit position obtaining step;

an inserting step that inserts the split/conjoin node determined by the split/conjoin node obtaining step at the processing target conjoining position determined by the conjoining position obtaining step; and

a deleting step that deletes the split/conjoin node determined by the split/conjoin node obtaining step from the processing source coupled node tree.

22. A coupled node tree conjoining method according to claim 21, wherein

the processing source maximum value or minimum value obtaining step is a step that, with the root node of the processing source coupled node tree as the searching start node, determines the maximum value or the minimum value of the index keys of the processing source coupled node tree by linking, of the node pairs, to only a primary node of the two nodes that form a node pair or to only the node located in a memory area adjacent to the coupled node indicator respectively until a leaf node is reached,

and the processing target minimum value or maximum value obtaining step is a step that, with the root node of the processing target coupled node tree as the searching start node, determines the minimum value or the maximum value of the index keys of the processing target coupled node tree by linking, of the node pairs, to only a coupled node of the two nodes that form a node pair or to only the node located in a memory area adjacent to the coupled node indicator respectively until a leaf node is reached,

23. A coupled node tree conjoining method according to claim 22, wherein

the processing source and the processing target coupled node tree are stored in an array, and the position information is an array element number of an array element in which a node corresponding to the position information is stored, and

the array element number of the array element in which the searching start node at the processing source maximum value or minimum value obtaining step and the processing target minimum value or maximum value obtaining step are stored and the array element numbers of the array elements in which the link target from the searching start node up until the leaf node at the processing source maximum value or minimum value obtaining step and the processing target minimum value or maximum value obtaining step are stored are successively stored respectively in a processing source stack and a processing target stack.

24. A coupled node tree conjoining method according to claim 23, wherein

the split/conjoin node obtaining step reads out from the array element number stored one position before the array element number of the array element stored in the processing source stack until the discrimination bit position of the branch node stored in the array element of the array element number is higher position than the difference bit position, and obtains a node stored in the array element having the array element number stored in the processing source stack next to the read-out array element number as the split/conjoin node, and

the conjoining position obtaining step reads out from the array element number stored one position before the array element number of the array element stored in the processing target stack until the discrimination bit position of the branch node stored in the array element of the array element number is higher position than the difference bit position, and obtains a node stored in the array element having the array element number stored in the processing target stack next to the read-out array element number as the conjoining position.

25. A program that a computer is caused to execute, for performing the coupled node tree conjoining method according to claim 21.

26. A computer-readable storage medium storing the program according to claim 25.