Method and device for searching fixed length data
First Claim
1. A fixed length data search device, comprising:
- a hash operation means for applying first and second similarly constructed hash function and thereby outputting multiple entry data corresponding to respective first and second hash values of an inputted fixed length datum;
a data table memory consisting of N numbers of memory banks, where N is an integer greater than or equal to two, the data table memory capable of storing a data table holding a large number of fixed length data;
a pointer table memory for storing a main memory pointer table, which is associated with the first hash function, and a subordinate memory pointer table for use when the main memory pointer table is filled to a predetermined level with respect to the N numbers of memory banks, which is associated with the second hash function that each indicates a memory address in said data table memory at which each fixed length datum is stored in said data table memory with said first and second hash values each acting as a respective index therefore;
a pointer selector table to indicate which one of said main and subordinate memory pointer tables is referred to when a fixed length datum is inputted, wherein a datum identical to the single fixed length datum inputted to said hash operation means is searched in said data table through said hash operation means, said single fixed length datum registered in said data table if the datum has not been previously registered with said data table, and wherein if another fixed length datum having the same first hash value as an inputted fixed length datum has not been registered with said data table, said inputted fixed length datum is stored in said data table memory, and said memory address at which the datum is stored is managed with said main memory pointer table; and
a comparison means for simultaneously comparing a plurality of fixed length data stored at the same memory address in said N numbers of memory banks, the comparison means for outputting results of the comparison.
1 Assignment
0 Petitions
Accused Products
Abstract
Embodiments of the present invention provide method and device for searching fixed length data. The device includes a hash operation means for operating and outputting a hash value of inputted fixed length data, a data table memory consisting of N numbers of memory banks, where N is an integer that is more than and equal to 2, the data table memory for storing a data table holding a large number of fixed length data, a pointer table memory for storing a memory pointer table holding a memory address at which each fixed length datum is stored with the hash value as an index, and a comparison means for simultaneously comparing a plurality of fixed length data stored at the same memory address in the N numbers of memory banks with a single fixed length datum inputted to the hash operation means, the comparison means for outputting results of the comparison.
41 Citations
13 Claims
-
1. A fixed length data search device, comprising:
-
a hash operation means for applying first and second similarly constructed hash function and thereby outputting multiple entry data corresponding to respective first and second hash values of an inputted fixed length datum; a data table memory consisting of N numbers of memory banks, where N is an integer greater than or equal to two, the data table memory capable of storing a data table holding a large number of fixed length data; a pointer table memory for storing a main memory pointer table, which is associated with the first hash function, and a subordinate memory pointer table for use when the main memory pointer table is filled to a predetermined level with respect to the N numbers of memory banks, which is associated with the second hash function that each indicates a memory address in said data table memory at which each fixed length datum is stored in said data table memory with said first and second hash values each acting as a respective index therefore; a pointer selector table to indicate which one of said main and subordinate memory pointer tables is referred to when a fixed length datum is inputted, wherein a datum identical to the single fixed length datum inputted to said hash operation means is searched in said data table through said hash operation means, said single fixed length datum registered in said data table if the datum has not been previously registered with said data table, and wherein if another fixed length datum having the same first hash value as an inputted fixed length datum has not been registered with said data table, said inputted fixed length datum is stored in said data table memory, and said memory address at which the datum is stored is managed with said main memory pointer table; and a comparison means for simultaneously comparing a plurality of fixed length data stored at the same memory address in said N numbers of memory banks, the comparison means for outputting results of the comparison. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A fixed length data search device, comprising:
-
a hash operation means, said hash operation means using two types of similarly constructed hash functions to determine a first and second hash values of an inputted fixed length datum wherein said first and second hash values include multiple entry data; a data table memory consisting of N numbers of memory banks, where N is an integer that is greater than or equal to two, the data table memory for storing a data table holding a large number of fixed length data; a pointer table memory for storing a first memory pointer table, said pointer table memory that indicates a memory address in said data table memory at which each fixed length datum is stored in said data table memory wherein said first hash value is an index, and a second memory pointer table for use when the first memory pointer table is determined to be filled to a predetermined level with respect to the N numbers of memory banks, which is associated with the second hash function, holding the memory address in said data table memory at which each fixed length datum is stored in said data table memory, said second hash value as an index; a pointer selector table using said first hash value as an index to indicate which one of said first and second memory pointer tables is referred to when a fixed length datum is inputted, wherein when the number of stored data of separate fixed length data having the same first hash value exceeds N, a pointer in said pointer selector table corresponding to the first hash value of an unstored fixed length datum stored is set to said second memory pointer table, said memory address at which the datum is stored managed with said second memory pointer table, wherein if another fixed length datum having the same first hash value as an inputted fixed length datum has not been registered with said data table, said inputted fixed length datum is stored in said data table memory, and said memory address at which the datum is stored is managed with said main memory pointer table; and a comparison means for simultaneously comparing a plurality of fixed length data stored at the same memory address in said N numbers of memory banks, the comparison means for outputting results of the comparison. - View Dependent Claims (7, 8, 9)
-
-
10. A method of searching fixed length data, comprising the steps of:
-
performing first and second similarly constructed hash operations to thereby outputting respective first and second hash values of inputted fixed length data, wherein each of said hash values includes multiple entry data; referring to a main memory pointer table, which is associated with the first hash operation, or a subordinate memory pointer table for use when the main memory pointer table is filled to a predetermined level with respect to N numbers of memory banks, which is associated with the second hash function, which is associated with the second hash operations, each of which holds a memory address in a data table memory at which each fixed length datum is stored in said data table memory with said first and second hash values each acting as a respective index therefor; reading N numbers of fixed length data stored at an address pointed to by a pointer in said memory pointer table from a data table stored in said data table memory consisting of N numbers of memory banks, where N is an integer that is greater than or equal to two, the data table capable of storing a large number of fixed length data, indicating in a pointer selector table which one of said main and subordinate memory pointer tables is referred to when a fixed length datum is inputted; searching an identical datum to said inputted single fixed length datum in said data table based on its hash value, and registering said inputted single fixed length datum in said data table if said identical datum has not been detected in said step of search mg; detecting an exist bit associated with said data table into which the inputted single fixed length datum is to be registered; determining if the exist bit indicates an on-state or an off-state of said data table, when the exist bit indicates the on-state, proceeding with the registering, when the exist bit indicates the off-state, proceeding with the second hash operation, and indicating that a next registered single fixed length datum is to be registered in the subordinate memory pointer table; and simultaneously comparing said read N numbers of fixed length data with said inputted single fixed length datum, and outputting results of the comparison. - View Dependent Claims (11, 12, 13)
-
Specification