Patent application number | Description | Published |
20090210414 | Bit string searching apparatus, searching method, and program - Bit string searching apparatus using a coupled node tree with a root node and a node pair stored in adjacent areas that is formed by a branch node and a leaf node, branch nodes, or leaf nodes; the branch node including a discrimination bit position in the search key and information indicating a position of a primary node that is one node of a node pair; the leaf node including an index key formed by a bit string; from the root node of an arbitrary subtree of the coupled node tree, linking is repeated based on the search key's bit value at the discrimination bit position and information indicating a position of a primary node until a leaf node is reached; an index key stored in the leaf node is obtained as a search result key of the subtree by means of the search key. | 08-20-2009 |
20090234802 | Coupled node tree splitting/conjoining method and program - 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. | 09-17-2009 |
20090240655 | Bit String Seacrching Apparatus, Searching Method, and Program - A bit string searching apparatus has a coupled node tree, having 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, the branch node including a search key discrimination bit position and information indicating a position of one node of a node pair of a link target, and the leaf node including an index key that is a bit string that is the target of a search, wherein a search for an index key from the root node to a branch node using a search key is executed by repeatedly and successively linking to one node of a node pair of a link target, according to a bit value of a search key at the discrimination bit position in the branch node, until reaching the leaf node. | 09-24-2009 |
20090287660 | Bit string searching apparatus, searching method, and program - To provide a method that minimizes efficiency reductions in processing coupled node trees even if the size of the coupled node tree grows large. In basic searching or maximum or minimum value searching, the search history, not only the address information of the storage area wherein a node is stored but also the discrimination bit position of branch nodes traversed in the search path, is stored in the search path stack. | 11-19-2009 |
20100042596 | Bit string search apparatus, search method, and program - A coupled node tree 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 arranged in adjacent storage areas. The branch node includes a discrimination bit position of the search key and the first position information of a primary node, one node of a node pair of a link target. The leaf node includes the second position information of the storage area holding an index key that is the target of a search. According to a bit value of the search key of a discrimination bit position in the branch node, repeated linking to a primary node of a node pair of the link target or a node at a position in a memory area adjacent thereto until a leaf node is reached. | 02-18-2010 |
20100042597 | Longest-match/shortest-match search apparatus, search method, and program - A coupled node tree 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. The branch node includes a discrimination bit position of the search key and a position information of a primary node, which is one node of a node pair of a link target. The leaf node includes an index key that is a bit string that is the target of a search. A coupled node tree is searched using a longest-match/shortest-match search key and the longest-match/shortest-match node is determined through a comparison of the difference bit position between the index key resulting from the search and the longest-match/shortest-match search key and the discrimination bit position of a branch node on the search path memorized when the search is performed. | 02-18-2010 |
20100042598 | Coupled node tree backup/restore apparatus, backup/restore method, and program - A coupled node tree has a root node and a node pair, the node pair being a branch node, which includes position information of a link target node pair, and a leaf node, which includes a search target index key, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas. The nodes of the coupled node tree are backed up in a depth precedence search sequence. The coupled node tree is restored by repeating the following process: reading out the nodes in the sequence they are backed up, storing in a stack the position information of the node to be restored, successively restoring child nodes as long as branch nodes are encountered, restoring a leaf node which is read out and then, tracing back up the stack, a decision being made as to which node is next to be restored. | 02-18-2010 |
20100174741 | Bit string search apparatus, search method, and program - Provided is a search method which is appropriate for handling a don't-care bit. A coupled node tree 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. The branch node includes a discrimination bit position of a search key for the bit string search, which key is encoded so as to distinguish between don't-care bits and significant bits, and position information indicating a position of a primary node, which is one node of a node pair of a link target. A leaf node includes an index key which is a bit string in the status of either being or not being encoded. A search that takes in account the don't-care bit is performed by repeatedly linking in sequence to one of the nodes of a node pair that is the link target in accordance with the bit value of the search key at the discrimination bit position of a branch node until a leaf node is reached, and by tracing back up the path to the leaf node as necessary. | 07-08-2010 |
20100174742 | Bit string search apparatus, search method, and program - To provide a method that lessens the reduction in efficiency of processing using a coupled node tree even if the scale of the coupled node tree grows large. Is stored a termination node, whose discrimination bit position has a value smaller than 0, in a search path stack that holds the search history while successively storing therein branch nodes that have been traversed in the search path. The coupled node indicator of the stored branch node is converted to a value wherein a 1 is added if the link target is node | 07-08-2010 |
20100250560 | Bit string merge sort device, method, and program - To realize a high speed merge sort method by applying a coupled node tree, which method extracts a smallest or largest key from a plurality of sorted key storage areas in each of which is stored keys comprised of bit strings that are sorted, and generates a coupled node tree for merge while adding a processing source identifier that identifies the sorted storage area wherefrom the key has been extracted, and repeats the actions of writing out into the merged key storage area a key being obtained by a minimum or maximum value search on the coupled node tree and deleting the key, and inserting into the coupled node tree a key by extracting the key from one of the plurality of sorted key storage areas. | 09-30-2010 |
20100262617 | Database index key update method and program - A method of database update processing for updating efficiently database index keys, when new database index keys are supplied to replace index keys already in the database, generates a delta data between the new and old data comprising insert and delete keys by delete processing from a coupled node tree holding the index keys in the old data using index keys of new data as delete keys, and generates new data by delete and insert processing from and into a coupled node tree holding index keys in old data as index keys using the delete keys and insert keys of the delta data. | 10-14-2010 |
20100287193 | Bit string search apparatus, search method, and program - An index key is a key string formed of three or more keys whose tail-end key is unique, and a search key string for a bit string search has a unique key as its tail-end key. A branch node includes a search key sequence number expressing the position information of a key in the search key string to be used in the bit string comparison during the bit string search and the discrimination bit position for that key. Search for index keys is performed by extracting from the search key string the key with the search key sequence number in the branch node and repeatedly linking to one of the nodes of a node pair of the link target in response to the bit value at the discrimination bit position of that key until the leaf node corresponding to that index key is reached. | 11-11-2010 |
20110066638 | Bit strings search apparatus, search method, and program - Using a tree configuration wherein node groups of four or more nodes composed of combinations of branch nodes, leaf nodes or empty nodes are linked into a tree form, a bit string search by a search key string is enabled by repeatedly linking to one of the nodes of a node group to which a primary node belongs in response to the bit values of keys of the search key string at the discrimination bit position included in the branch node. | 03-17-2011 |
20110145538 | Storage region management method, storage region allocation method and program - A storage area management method for a data storage apparatus partitions an acquired storage area into storage areas with differing power-of-2 sizes and manages each of them. Also, a storage area allocation method receives an allocation request for a storage area that includes a requested allocation size, and acquires an available storage area whose size is the smallest power-of-2 size encompassing the requested allocation size, and obtains a binary expression of the requested allocation size, and in response to the received allocation request, allocates a contiguous storage area comprised of storage areas each of whose size is a power of 2 of a value of a bit position wherein a 1 is set in the binary expression. | 06-16-2011 |
20110170536 | Network path finding apparatus, method, and program - To perform a path finding for a network by traversing mutually connected links by means of a link destination table that is a data configuration for representing the network. The link destination table contains, for link IDs of each of the links in the network, a node ID of a node on one side of the link, destination link IDs for the node on one side which are link IDs of other links to that node, a node ID of the node on the other side of the link, destination link IDs of the node on the other side which are link IDs of other links to that node, and interval costs. | 07-14-2011 |
20110191756 | Code string search apparatus, search method, and program - A code ID range table holding code ID ranges for each code and a next code ID table holding next code IDs, which are the code ID located next to each code ID, are created. Code ID ranges of codes configuring a search code string are read out from the code ID range table for the search target code string, and the stored next code ID corresponding to a code ID included in the code ID range of the head code in the search code string is read out from the next code ID table while the stored next code IDs corresponding to the next codes are successively read out from the next code ID table, and the next code ID read out from the next code ID table is verified whether it is included in the code ID range read out from the code ID range table. | 08-04-2011 |
20110258205 | Bit string data sorting apparatus, sorting method, and program - The sort processing of keys to be sorted, which keys are expressed as bit strings involves a classification processing. In the classification processing, a bit string comparison between a reference key and a key which is an object of the classification is performed, and a difference bit position is obtained that is the bit position of the first bit that differs in the bit string comparison and the keys to be sorted are classified by the difference bit position into key groups with the same difference bit position. | 10-20-2011 |
20120089806 | REGION MANAGEMENT APPARATUS, REGION MANAGEMENT METHOD, AND PROGRAM - To provide a technology that, regardless of the capacity of a storage device, enables its areas to be flexibly partitioned and managed, and, when a file is allocated to a region also, can also use its areas effectively by means of an efficient method. When a region size of a storage device is expressed as the sum of mutually differing power-of-2 values, and areas whose size is one of the power-of-2 sizes configuring that sum are taken to be master partitions, to partition the areas into partitions each of whose size is the size made by successively dividing each master partition in half and to generate an allocation table holding allocation information expressing the allocation status of each of the files that have partitions with each of the sizes included in the master partitions. To manage a region based on the allocation information stored in the allocation table. | 04-12-2012 |
20120209855 | BIT-STRING KEY CLASSIFICATION/DISTRIBUTION APPARATUS, CLASSIFICATION/DISTRIBUTION METHOD, AND PROGRAM - When keys are to be classified into a plurality of blocks, to provide a classification method wherein the range of key values does not overlap and a method for distributing the classified keys by applying the art of a coupled-node tree. Keys are successively selected as classification keys from a key storage means holding the keys to be classified, and a classification tree, which is an application of a coupled-node tree, is generated by means of the classification keys, and the classification is done by making a correspondence between its leaf nodes and the keys to be classified into each of N blocks. The number of levels in the classification tree is constrained as a function of the block number N. A leaf node is extracted from the classification tree and the corresponding key is extracted as a classified key and distributed. | 08-16-2012 |
20120239664 | BIT STRING SEARCH APPARATUS, SEARCH METHOD, AND PROGRAM - To increase space efficiency of a coupled node tree, a branch node does not have an area that holds an array element number of an array element wherein is stored the primary node of the node pair that is the link target, and the root node is disposed in an array element with a node location number | 09-20-2012 |
20120284279 | CODE STRING SEARCH APPARATUS, SEARCH METHOD, AND PROGRAM - An index data configuration adapted to a code-string search method for a structured code string having data codes, first separator codes that separate a data code or a data code string and second separator codes that divide a code string into partial code strings. The configuration has a code ID range table holding the code ID ranges for each code and a next code ID table holding next code IDs. Using the configuration, a partial code string is searched for in the search target code string by a first search code string consisting of the data code or the data code string and a first separator code. Next, using a second search code string consisting of first separator codes, the data code or the data code string separated by each of the first separator codes is searched from the found partial code string. | 11-08-2012 |