Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-23
2002-09-24
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06457001
ABSTRACT:
BACKGROUND OF THE INVENTION
1 Field of the Invention
The present invention relates to a method and an apparatus for data retrieval using binary search.
2. Description of the Related Art
When binary search is used, one kind of a mask pattern is employed which is used in the retrieval of one time. However, during retrieval, in some situations only a portion of retrieval key data and a portion of retrieval object data need to coincide with each other while in other situations all of the retrieval key data and all of the retrieval object data need to coincide with each other. One example thereof is a case in which Virtual Path Identifier/Virtual Channel Identifier (VPI/VCI) translation is carried out in an Asynchronous Transfer Mode (ATM) switch.
In this case, notations VPI and VCI designate identifiers added to respective cells of ATM. VPI determines which virtual path is to be used and VCI determines which virtual channel is be used. In this situation, VCI determines which virtual channel multiplexed to a virtual path is used to transmit data to another party. In the case of Virtual Path Connection (VPC), switching is carried out only based on VPI information. In the case of Virtual Channel Connection (VCC), switching is carried out based on information of the two values of VPI and VCI.
In VPI/VCI translation, VPI and VCI constitute retrieval key data. Accordingly, when VCC is used, a result of retrieval must be determined based on both values of VPI and VCI. However, when VPC is used, a result of retrieval is determined based on only the value of VPI. For example, consider the case shown in FIG.
8
. When VPI of a cell which enters a switch is 7AC and VCI is 5AB0, the cell is transmitted by replacing VPI by 902 and VCI by A77F. Further, when VPI of a cell which enters the switch in 7BC and VCI is 7990, the call is transmitted by replacing VPI by 802 and VCI by 5432. When VPI of a cell which enters the switch is 123, the cell is transmitted by replacing VPI by 345 regardless of a value of VCI.
When this is realized in a conventional retrieval apparatus which can use only one mask pattern in one time of retrieval, content of a retrieval table is ax shown by
FIG. 9
, Data of one set of VPI and VCI is inputted as retrieval key data and compared with values of VPIin and VCIin and in the case of coinaidence, VPIout and VCIout are outputted as associative data. In this case, VPI and VCI belonging to the same VPC need to register respectively and individually.
Hence, in order to differentiate whether registered data is VPC or VCC, a specific value of VCI is used as a special value to identify the differentiation. For example, consider a case in which “FFFF” of VCI is used as a value for identifying VPC. Then, a resistor table is as shown by FIG.
10
. When registration is carried out in such a style, a region of the table can be saved. Although one entry is saved in this example, as VPC becomes greater, or as data belonging to one VPC becomes greater more of the table can be saved. However, a specific value of VCI is used as an identifier of VPC and therefore, there poses a problem in which a restriction, which has not been present inherently, is added to an outside system.
As described above, in retrieval operation, there is one case where a portion of retrieval key data and a portion of retrieval object data may coincide with each other and there is another case where all of the retrieval key data and all of the retrieval object data must coincide with each. In this situation the retrieval needs to be carried out by dividing retrieval operation into plural times thereof by using different mask patterns, or mask data needs to be stored for each entry of the retrieval object data, or data needs to be registered by using a special value.
However, it is apparent that in the case of multiple retrievals, the time period required for the retrieval is increased. In the case of holding mask data for each entry, a capacity for holding data is doubled. Further, in the case of registering data by using a special value, the value cannot be used when a recognition of a total of data is needed.
SUMMARY OF THE INVENTION
The invention provides methods and apparatus that retrieve data using a binary search based on a plurality of retrieval conditions without increasing a number of times of retrieval and without complicating constitutions of retrieval key data and mask data.
According to one aspect of the invention, in data retrieval using binary search, data constituting a retrieval object is classified into a plurality of blocks. Bit string indicating information is provided which contributes to retrieval results of the respective blocks (coincidence condition for determining that coincidence may be regarded to establish when coincidence of some of the blocks is established). Further, the retrieval key data corresponding with the blocks and are compared with respective object blocks. A result of coincidence or non-coincidence, in accordance with the coincidence conditions, is output by the comparison results and the bit string. Thereby, the above-described problem is solved by carrying out the retrieval operation only once under a plurality of retrieval conditions.
Further, in order to resolve the above-described problem, according to other aspect of the invention, there is provided an apparatus of retrieving data, wherein when retrieval object data is classified into higher order bits and lower order bits, a portion of the retrieval key data, in correspondence with the higher order bits, is defined as first key data. A portion of the retrieval key data, in correspondence with the lower order bits, is defined as second key data. The data retrieval apparatus includes a higher order bit comparing circuit for comparing the higher order bits of the retrieval object data with the first retrieval key data, a lower order bit comparing circuit for comparing the lower order bits of the retrieval object data with the second retrieval key data, and a determining circuit for determining coincidence or non-coincidence between the retrieval key data and the retrieval object data. The determining circuit determines coincidence based on comparison enabling bits indicating coincidence conditions, a comparison result of the higher order bit comparing circuit and a comparison result of the lower order bit comparing circuit.
With the present invention, bits are provided that indicate whether respective blocks, constituting entries, contribute to retrieval for the respective entries of different retrieval object data. The retrieval object data is classified into higher order bits and lower order bits and stored.
A portion of the retrieval key data, in correspondence with the higher order bits of the retrieval object data, constitutes first retrieval key data and a portion thereof, in correspondence with the lower order bits constitutes second retrieval key data.
In this way, the first retrieval key data is compared with the higher order bits in the retrieval object data and the second retrieval key data is compared with the lower order bits in the retrieval object data. Further, coincidence or non-coincidence between the retrieval key data and the retrieval object data is determined in accordance with a comparison enabling bit indicating coincidence conditions, a comparison result of the higher order bits and a comparison result of the lower order bits.
For example, one entry comprising 32 bits which is retrieval object data is classified into three portions and includes a highest order of 1 bit, a high order of 15 bits and a low order of 16 bits. The highest order of 1 bit is a comparison enabling bit EB. Retrieval key data is constituted by 31 bits and higher order 15 bits constitute first retrieval key data PK and lower order 16 bits constitute second retrieval key data SK.
The comparison enabling bit EB indicates coincidence conditions of whether coincidence of only the first retrieval key data PK is validated. When the comparison enabling bit EB is “1”, the retrieval hits by coincidence of only the first retrieval
Corrielus Jean M.
Kawasaki Microelectronics Inc.
Oliff & Berridg,e PLC
Truong Cam-Y T.
LandOfFree
Method and apparatus for data retrieval does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for data retrieval, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for data retrieval will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905383