Search apparatus and search management method for fixed-length data

• US 20070194957A1
• Filed: 03/31/2004
• Published: 08/23/2007
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: IPT Corp.
• Original Assignee: IPT Corp.
• Inventors: Watanabe, Shinpei
• Granted Patent: US 7,565,343 B2
• Time in Patent Office: Days
• US Class Current: 341/106
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Fixed-length data (560) contained in a database (560) are segmented into a number of pieces of data that are searchable at a time and searching is performed at high speed. As means for it, a pointer table (500), a secondary pointer table, a local table, and a fixed-length-data table are provided, and when more segmentation is required, a table having a numeric-value comparing function is further provided. As means for performing efficient configuration/management of the tables and for performing management that does not interfere with a search operation, an empty-house table (700), an empty-room table (720), a room-management table (740), and a structure-management table (760) may be provided.

Claims

1. A fixed-length-data searching apparatus comprising:

input-fixed-length-data processing means for performing specified processing on fixed-length data that has been input and that is to be searched for, and performing output;

a pointer table memory for storing a pointer table in which an output value from the input-fixed-length-data processing means or pointer processing means is held as an index;

the pointer processing means for performing specified processing by using a pointer value output from the pointer table memory, an output of the input-fixed-length-data processing means, and an output value of a fixed-length-data table memory;

the fixed-length-data table memory for storing the fixed-length-data table in which at least one of data corresponding to fixed-length data required for searching and data required for searching, and a large number of pieces of fixed-length data addressed by an output of the pointer processing means are held;

comparing means for comparing, using a specified method, multiple fixed-length data stored in the fixed-length-data table and the input fixed-length data to be searched for and outputting a comparison result obtained by the comparison;

a data-table memory for storing a data table in which various data corresponding to the fixed-length data stored in the fixed-length-data table are held;

modifying means for reading data stored in the data table, the data corresponding to fixed-length data matched in the comparison result, and modifying the read data; and

outputting means for outputting a search result, a fixed-length data name, and other data output from the comparing means and the modifying means.

2. The fixed-length-data searching apparatus according to claim 1, wherein in order to perform search processing of the input fixed-length data to be searched for, the input-fixed-length-data processing means comprises means for outputting, as a search processing slot, a name or search number attached to the input;

and the search number output from the input-fixed-length-data processing means is used to process a large number of search processing operations in parallel in the individual memories and the individual means of the fixed-length-data searching apparatus.

3. The fixed-length-data searching apparatus according to claim 1, wherein the input-fixed-length-data processing means for processing the input fixed-length data to be searched comprises at least one of:

means for calculating, using all or part of the input fixed-length data, a hash value using a specified hash function and outputting the hash value; and

means for outputting all or part of the input fixed-length data.

4. The fixed-length-data searching apparatus according to claim 1, wherein the pointer table comprises at least one of:

data required for address generating means in means for using an input from the pointer table;

multiple bits indicating a processing procedure in means for using the input from the pointer table;

multiple bits indicating a procedure for reading only a relevant array of multiple memory arrays included in the fixed-length-data table memory that stores the fixed-length-data table; and

multiple bits indicating an address with respect to fixed-length data in the fixed-length-data table, the fixed-length data being searchable without being compared with the input fixed-length data by the comparing means.

5. The fixed-length-data searching apparatus according to claim 1, wherein the pointer processing means comprises means for generating, based on at least one of an output of the pointer table and an output of the fixed-length-data table, at least one of:

an address of the fixed-length-data table;

an address of a numeric-value comparison table created in a database including the fixed-length-data table and the data table;

an address of a secondary pointer table; and

an address of a local table created in the database.

6. The fixed-length-data searching apparatus according to claim 1, wherein the fixed-length-data table comprises means for reading entry control data and multiple elements with respect to one memory address output by the pointer processing means, and multiple elements are fixed-length data and data corresponding to fixed-length data.

7. The fixed-length-data searching apparatus according to claim 6, wherein the elements comprise:

fixed-length data;

a fixed-length data name unique to the fixed-length data; and

element control data.

8. The fixed-length-data searching apparatus according to claim 7, wherein the elements further comprise either a prefix mask used for prefix mask means or a local mask used for local mask means,

wherein the prefix mask means is means, included in the comparing means, for comparing, using a comparator, bits of multiple pieces of fixed-length data stored in the fixed-length-data table and bits of the input fixed-length data to be searched for, and using, with respect to an output of the comparator, only a unique bit length from the highest bit of the fixed-length data to obtain the comparison result;

and the local mask means is means for comparing, using the comparator, bits of multiple pieces of fixed-length data stored in the fixed-length-data table and bits of the input fixed-length data to be searched for, and masking, with mask data unique to the fixed-length data, an output of the comparator to obtain the comparison result.

9. The fixed-length-data searching apparatus according to claim 7, wherein the element control data comprises multiple bits for controlling means for automatically deleting an element in the fixed-length-data table.

10. The fixed-length-data searching apparatus according to claim 6, wherein the entry control data comprises multiple bits indicating a processing content for an output read from the fixed-length-data table.

11. The fixed-length-data searching apparatus according to claim 1, wherein the fixed-length-data table comprises, as entry control data, at least one of:

an address for reading the fixed-length-data table;

an address for reading a secondary pointer table;

an address for reading a local table therein; and

an address for reading a numeric-value comparison table therein.

12. The fixed-length-data searching apparatus according to claim 1, wherein the fixed-length-data table comprises a configuration in which a local table and a numeric-value comparison table are configurable therein.

13. The fixed-length-data searching apparatus according to claim 1, wherein the pointer table memory, the fixed-length-data table memory, and the data-table memory have Q, N, and U memory arrays (Q, N, and U are integers of 1 or greater), respectively, each memory array having corresponding P, M, and V memory banks (P, M, and V are integers of 1 or greater),

wherein the memory arrays and the memory banks in at least one of the pointer table memory, the fixed-length-data table memory, and the data-table memory are operable independently and operate in parallel, each memory bank comprising at least one of means capable of reading or writing multiple bits at a time and reading means for efficiently performing the parallel operation of the memory banks in the memory arrays.

14. The fixed-length-data searching apparatus according to claim 1, wherein the data table comprises means for holding static data that corresponds to the fixed-length data stored in the fixed-length-data table and that is irrelevant to a search operation and dynamic data that is modified by a result of the search operation.

15. The fixed-length-data searching apparatus according to claim 1, wherein the modifying means comprises means for reading data from the data table based on the result output by the comparing means and means for modifying the read data and writing the modified data to the data table.

16. The fixed-length-data searching apparatus according to claim 1, wherein the comparing means comprises:

N*R bit maskable bit comparators and value comparators (* is an operation sign indicating multiplication) for simultaneously comparing, based on a specified method, multiple pieces of fixed-length data stored in the fixed-length-data table with the input fixed-length data to be searched for and for outputting the comparison result,

wherein the N*R maskable bit comparators and the value comparators comprise means that is reconfigurable with a variable bit length to perform comparison with the fixed-length data or part thereof, N being an integer of 1 or greater indicating the number of memory arrays and R being the number of bits that are simultaneously readable from or writable to the memory banks in the memory arrays.

17. The fixed-length-data searching apparatus according to claim 1, wherein the comparing means compares, using a comparator, bits of multiple pieces of fixed-length data stored in the fixed-length-data table and bits of the input fixed-length data to be searched for and comprises at least one of:

global mask means for masking an output of the comparator bit by bit to obtain the comparison result;

local mask means for masking an output of the comparator with mask data unique to the fixed-length data to obtain the comparison result; and

prefix mask means for using, with respect to an output of the comparator, only a unique bit length from the highest bit of the fixed-length data to obtain the comparison result.

18. The fixed-length-data searching apparatus according to claim 1, wherein the comparing means comprises means for outputting the comparison result together with a name or search number assigned to the input.

19. The fixed-length-data searching apparatus according to claim 1, wherein the outputting means comprises at least one of:

means for outputting the comparison result received from the comparing means and user data received from the modifying means in synchronization with each other; and

means for outputting, as a command slot of the fixed-length-data searching apparatus, a name or search number attached to the input of fixed-length data to be searched for, to prevent overflow of the input.

54. A program causing a computer to function as the apparatus according to claim 1.

55. A computer-readable storage medium on which the program according to claim 54 is recorded.

20. A fixed-length-data searching method having:

an input-fixed-length-data processing step of performing specified processing on fixed-length data that has been input with a name or search number attached to each input and that is to be searched for, and of performing output;

a step of reading a pointer value from a pointer table by using an output value of the input-fixed-length-data processing step as an index;

a pointer processing step of performing specified processing by using the pointer value output from the pointer table memory and an output value of the input-fixed-length-data processing step;

a step of reading a fixed-length-data table in which at least one of data corresponding to fixed-length data required for searching and data required for searching, and a large number of pieces of fixed-length data addressed by an output of the pointer processing step are held;

a comparing step of simultaneously comparing, using a specified method, multiple pieces of fixed-length data stored in the fixed-length-data table with the input fixed-length data to be searched for, and of outputting a comparison result;

a step of reading, based on the comparison result, a data table in which various data corresponding to the fixed-length data stored in the fixed-length-data table are held.

a modifying step of modifying data read in accordance with the comparison result; and

an outputting step of outputting a search result, a fixed-length-data name, and other data output in the comparing step and the modifying step.

21. A fixed-length-data searching method having:

an input-fixed-length-data processing step of performing specified processing on fixed-length data that has been input with a name or search number attached to each input and that is to be searched for, and of performing output;

a step of reading a first pointer value from a pointer table by using an output value of the input-fixed-length-data processing step as an index;

a pointer processing step of performing specified processing by using the first pointer value and the output of the input-fixed-length-data processing step;

a step of reading a second pointer value from the pointer table by using, as an index, an output value of the pointer processing step that uses the first pointer;

a pointer processing step of performing specified processing by using the second pointer value and the input fixed-length data;

a step of reading a fixed-length-data table in which at least one of data corresponding to fixed-length data required for searching and data required for searching, and a large number of pieces of fixed-length data addressed by an output of the pointer processing step that uses the second pointer are held;

a comparing step of comparing, using a specified method, multiple pieces of fixed-length data stored in the fixed-length-data table with the input fixed-length data to be searched for, and of outputting a comparison result;

a step of reading, based on the comparison result, a data table in which various data corresponding to the fixed-length data stored in the fixed-length-data table are held;

a modifying step of modifying data read based on the comparison result; and

an outputting step of outputting a search result, a fixed-length-data name, and other data output in the comparing step and the modifying step.

22. A fixed-length-data searching method having:

an input-fixed-length-data processing step of performing specified processing on fixed-length data that has been input with a name or search number attached to each input and that is to be searched for, and of performing output;

a step of reading a pointer value from a pointer table as a pointer table index of the input-fixed-length-data processing;

a pointer processing step of performing specified processing by using the pointer value output from the pointer table memory and an output value of the input-fixed-length-data processing step;

a step of reading a fixed-length-data table in which at least one of data corresponding to fixed-length data required for searching and data required for searching, and a large number of pieces of fixed-length data addressed by an output of the pointer processing step are held;

a pointer processing step of performing specified processing by using an output from the fixed-length-data table;

a step of reading the fixed-length-data table;

a comparing step of simultaneously comparing, using a specified method, multiple pieces of fixed-length data stored in the fixed-length-data table with the input fixed-length data to be searched for, and of outputting a comparison result;

a step of reading, based on the comparison result, a data table in which various data corresponding to the fixed-length data stored in the fixed-length-data table are held;

a modifying step of modifying data read in accordance with the comparison result; and

an outputting step of outputting a search result, a fixed-length-data name, and other data output in the comparing step and the modifying step.

23. A fixed-length-data searching method having:

an input-fixed-length-data processing step of performing specified processing on fixed-length data that has been input with a name or search number attached to each input and that is to be searched for, and of performing output;

a step of reading a first pointer value from a pointer table by using an output value of the input-fixed-length-data processing step as an index;

a pointer processing step of performing specified processing by using the first pointer value and the output of the input-fixed-length-data processing step;

a step of reading a second pointer value from the pointer table by using, as an index, an output value of the pointer processing step that uses the first pointer value;

a pointer processing step of performing specified processing by using the second pointer value and the input fixed-length data;

a step of reading a fixed-length-data table in which at least one of data corresponding to fixed-length data required for searching and data required for searching, and a large number of pieces of fixed-length data addressed by an output of the pointer processing step that uses the second pointer are held;

a pointer processing step of performing specified processing by using an output from the fixed-length-data table;

a step of reading the fixed-length-data table;

a comparing step of simultaneously comparing, using a specified method, multiple pieces of fixed-length data stored in the fixed-length-data table with the input fixed-length data to be searched for, and of outputting a comparison result;

a step of reading, based on the comparison result, a data table in which various data corresponding to the fixed-length data stored in the fixed-length-data table are held;

a modifying step of modifying data read in accordance with the comparison result; and

a outputting step of outputting a search result, a fixed-length-data name, and other data output in the comparing step and the modifying step.

24-53. -53. (canceled)

56-64. -64. (canceled)