Patent ID: 8195667
Filing Date: 2012-06-05
Classification: G06F

Abstract:
1. A bit string search method using 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 leaf node, or a pair of branch nodes, or a pair of leaf nodes 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, and the branch node includes a first 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 a second position information indicating a position of a storage area in which is stored an index key composed of a bit string that is the target of a search, the index key being a key string formed of three or more keys of which a tail end key is an unduplicated unique key, and the branch node further including a search key sequence number distinguishing a position of a key within a search key string for the bit string search and a discrimination bit position of the key, comprising: 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 coupled node tree as a search start node in accordance with a bit value of a key at a discrimination bit position included in the branch node, which key is distinguished within a search key string by a search key number included in the branch node, until the leaf node is reached; and reading out an index key stored in the storage area indicated by the second position information included in the leaf node and the index key being made a search result key string, which is a search result using the search key string of an arbitrary subtree having the search start node as its root node.