Patent ID: 8166043
Filing Date: 2012-04-24
Classification: G06F

Abstract:
1. A bit string search apparatus, comprising: a tangible non-transitory computer readable data storage apparatus having a coupled node tree stored therein, the coupled node tree being used in a bit string search and comprises a root node and in layers below that root node, node groups formed from four or more nodes in adjacent storage areas, the nodes being a collection of branch nodes, leaf nodes, or empty nodes, 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 group of a link target, and the leaf node includes an index key composed of a bit string that is the target of a search or a second position information indicating a storage area holding the index key, and the empty node includes information expressing that that node is in an empty status, the index key being a key string formed of two or more keys, and the branch node also including a discrimination bit position for a key of a search key string for performing a bit string search; a data processing apparatus configured to repeat a linkage, at the branch node, to one node located in one node position of a link target node group to which the primary node belongs from an arbitrary node other than an empty node of the coupled node tree as a search start node, in accordance with bit values of keys of the search key string at the discrimination bit position included in the branch node; and wherein, if a leaf node is reached, the index key stored in a storage area indicated by the second position information included in the leaf node or the index key stored in the leaf node is made the search result key string of a search, using the search key string, of an arbitrary subtree of the coupled node tree that has the search start node as its root node or if an empty node is reached, the empty node is made the search result empty node of a search, using the search key string, of an arbitrary subtree of the coupled node tree that has the search start node as its root node.