Method and apparatus for data retrieval

Abstract

A method and apparatus for carrying out binary search based on a plurality of retrieval conditions. Retrieval object data is classified into higher order bits and lower order bits. A portion of retrieval key data, in correspondence with the higher order bits of the retrieval object data, constitutes first key data and a portion in correspondence with the lower order bits of the retrieval object data constitutes second retrieval key data. A higher order bit comparing circuit 13 is provided for comparing the higher order bits of the retrieval object data with the first retrieval key data and a lower order bit comparing circuit 14 and for comparing the lower order bits of the retrieval object data with the second retrieval key data. Further, there is provided a determining circuit 16 for determining coincidence or non-coincidence between the retrieval key data and the retrieval object data in accordance with a comparison enabling bit EB indicating coincidence conditions, a comparison result of the higher order bit comparing circuit 13 and comparison result of the lower bit comparing circuit 14.

What is claimed is:  
     
         1 . A method of retrieving data comprising: 
 classifying data of a retrieval object into a plurality of blocks;    indicating information contributing to retrieval results of respective blocks by use of a bit string; and    carrying out a plurality of retrieval conditions in one retrieval operation.    
     
     
         2 . The method of retrieving data according to  claim 1 , further comprising: 
 searching the data using a binary search.    
     
     
         3 . The method of retrieving data according to  claim 1 , further comprising: 
 using the comparison results of the plurality of blocks with respective portions of retrieval key data and information of the bit string.    
     
     
         4 . The method of retrieving data according to  claim 3 , further comprising: 
 using a retrieving table for registering data constituting the retrieval object with a retrieval condition bit string for setting the information contributing to the retrieval results of the plurality of blocks.    
     
     
         5 . The method of retrieving data according to  claim 3 , further comprising: 
 outputting retrieval results of coincidence or non-coincidence according to comparison results of the plurality of blocks and the retrieval condition bit string.    
     
     
         6 . An apparatus for retrieving data, wherein retrieval key data is classified into first retrieval key data of higher order bits and second retrieval key data of lower order bits, said apparatus of retrieving data comprising: 
 a higher order bit comparing circuit for comparing the first retrieval key data with higher order bits of retrieval object data;    a lower order bit comparing circuit for comparing the second retrieval key data with lower order bits of the retrieval object data; and    a determining circuit for determining a coincidence or a non-coincidence between the retrieval key data and the retrieval object data in accordance with: 
 a comparison enabling bit indicating coincidence conditions,  
 a comparison result of the higher order bit comparing circuit, and  
 a comparison result of the lower order bit comparing circuit.  
   
     
     
         7 . The apparatus for retrieving data according to  claim 6 , further comprising: 
 a storing device for storing the higher order bits, the lower order bits by which the retrieval object data is classified and    comparing bits indicating coincidence conditions of classified data.    
     
     
         8 . The apparatus for retrieving data according to  claim 6 , wherein the determining circuit outputs a signal representing coincidence or non-coincidence between the retrieval key and the retrieval object data and outputs a signal indicating at which portion the coincidence is established in the case of the coincidence.  
     
     
         9 . An apparatus for retrieving data comprising: 
 circuitry for classifying retrieval object data into at least two or more of a plurality of blocks and storing the retrieval object data along with comparison enabling data for indicating coincidence conditions of the plurality of blocks;    a plurality of comparing devices for classifying retrieval key data in correspondence with the plurality of blocks and for respectively comparing the retrieval key data with the plurality of blocks; and    a determining circuit for determining coincidence or non-coincidence between the retrieval key data and the retrieval object data based on the comparison enabling data and comparison results of the plurality of comparing devices.    
     
     
         10 . The apparatus of retrieving data according to  claim 9 , wherein the determining circuit outputs a signal representing the coincidence or the non-coincidence between the retrieval key data and the retrieval object data and a signal indicating at which portion the coincidence is established in the case of the coincidence.  
     
     
         11 . An apparatus for retrieving data comprising: 
 a storage device for storing retrieval object data and comparison enabling data;    an address generating circuit for generating an address for storing to and reading the retrieval object data from the storage device; and    a control circuit for comparing data read from the storage device with retrieval key data;    wherein the control circuit comprises: 
 a plurality of comparing circuits for comparing the retrieval object data with the retrieval key data;  
 circuitry for classifying the retrieval object data and the retrieval key data into pluralities of blocks of classified retrieval object data and the classified retrieval key data, and supplying the classified retrieval object data and the classified retrieval key data to the comparing circuit; and  
 a determining circuit for determining coincidence or non-coincidence between the retrieval key data and the retrieval object data based on comparison results of the comparing circuit and based on the comparison enabling data.  
   
     
     
         12 . The apparatus of retrieving data according to  claim 11 , wherein the control circuit provides the address generating circuit with information of the compared retrieval object data and retrieval key data for generating the address and outputs a determination result in accordance with retrieval conditions.  
     
     
         13 . The apparatus of retrieving data according to  claim 12 , wherein the comparison results indicate whether the retrieval key data and the retrieval object data either partially coincide with each other or totally coincide with each other.  
     
     
         14 . The apparatus of retrieving data according to  claim 11 , wherein the determining circuit outputs a signal representing the coincidence or the non-coincidence between the retrieval key data and the retrieval object data and a signal indicating at which portion the coincidence is established in the case of the coincidence.  
     
     
         15 . A network switch for receiving packets transmitted from a terminal of a transmitting party and transmitting the packets to an object of a terminal of a receiving party, said network switch comprising: 
 a retrieval table for storing registered data and comparison enabling data indicating a coincidence condition which validates a coincidence of either a portion or a total of each of portions of the registered data;    a comparing circuit for comparing respective portions of sampled data from packets with respective portions of the registered data; and    a determining circuit for determining coincidence or non-coincidence between the registered data and the sampled data according to the comparison enabling data and a comparison result of the comparing circuit.    
     
     
         16 . The network switch according to  claim 15 , wherein both the registered data and the sampled data comprise IP addresses and port numbers.  
     
     
         17 . The network switch according to  claim 15 , wherein both the registered data and the sampled data comprise destination IP addresses and data indicating attributes of other packets.  
     
     
         18 . A method for retrieving an object or data based on a retrieval key comprising: 
 identifying a first portion of a key;    identifying a second portion of a key;    outputting the object if a first portion of the object is equal to a first predetermined value and a second portion of the object is equal to the first portion of the key; and    outputting the object if the first portion of the object is equal to a second predetermined value, the second portion of the object is equal to the first portion of the key and a third portion of the object is equal to a second portion of the key.    
     
     
         19 . The method according to  claim 18  wherein the first portion of the key comprises an IP address.  
     
     
         20 . The method according to  claim 18  wherein the second portion of the key comprises a port number.  
     
     
         21 . The method according to  claim 18  wherein the first portion of the key comprises a virtual path identifier.  
     
     
         22 . The method according to  claim 18  wherein the second portion of the key comprises a virtual channel identifier.  
     
     
         23 . The method according to  claim 18  wherein the second portion of the object comprises an IP address.  
     
     
         24 . The method according to  claim 18  wherein the third portion of the object comprises a port number.  
     
     
         25 . The method according to  claim 18  wherein the second portion of the object comprises a virtual path identifier.  
     
     
         26 . The method according to  claim 18  wherein the third portion of the object comprises a virtual channel identifier.  
     
     
         27 . The method according to  claim 18  wherein the first portion of the object comprises comparison enabling bit.