High-speed information retrieval system

• US 20020152352A1
• Filed: 04/08/2002
• Published: 10/17/2002
• Est. Priority Date: 04/13/2001
• Status: Abandoned Application

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kaganoi, Teruo, Ikegai, Yasuyuki
• Application Number:
  US10/117,197
• Publication Number:
  US 20020152352A1
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

An information retrieval system includes two content addressable memories to be searched for m-bit/n-bit codes identical with m-bit/n-bit retrieval key sub-codes, a data memory storing pieces of information relating to different retrieval keys expressed by the combinations of the m-bit/n-bit codes in addressable memory locations assigned addresses, respectively, and an address generating unit supplied with addresses of the m-bit/n-bit codes identical with the m-bit/n-bit retrieval key sub-codes from the content addressable memories so as to generate a target address from the addresses for accessing the piece of information relating to a given retrieval key, whereby the two content addressable memories are searched for the m-bit/n-bit codes substantially in parallel.

Claims

1. An information retrieval system for selecting a piece of information relating to a retrieval key code dividable into plural retrieval sub-codes, comprising:

a first memory including plural memory spaces respectively storing plural groups of content codes equal in bit width to said plural retrieval sub-codes, and responsive to said plural retrieval sub-codes so as to output plural address codes representative of memory locations respectively selected from said plural memory spaces, content codes identical with said plural retrieval sub-codes being stored in said memory locations;

a second memory having plural addressable memory locations for storing pieces of information, and responsive to a target address so as to select said piece of information relating to said retrieval key code from said pieces of information; and

an address generating unit connected to said first memory and said second memory, and generating said target address through an arithmetic operation on said address codes so as to supply said target address to said second memory.

2. The information retrieval system as set forth in claim 1, in which said address generating unit generates said target address further through an indirect addressing with said address codes.

3. The information retrieval system as set forth in claim 2, in which said address generating unit includes

an address memory having plural addressable memory locations for storing said values together with other values and responsive to said address codes so as to output said values from the addressable memory locations specified by said address codes, and

an arithmetic circuit connected to said address memory and said second memory and generating said target address from said values for supplying said target address to said second memory.

4. The information retrieval system as set forth in claim 3, in which said arithmetic circuit carries out an addition between said values.

5. The information retrieval system as set forth in claim 2, in which said address generating unit includes

an address memory having plural addressable memory locations for storing at least one of said values together with other values and responsive to at least one of said address codes so as to output said at least one of said values from at least one addressable memory location specified by said at least one of said address codes,

an address converter supplied with at least one of said plural retrieval sub-codes for generating the remaining values, and

an arithmetic circuit connected to said address memory and said address converter and generating said target address from said at least one of said values and said remaining values for supplying said target address to said second memory.

6. The information retrieval system as set forth in claim 5, in which said address converter is a data buffer for storing said at least one of said plural retrieval sub-codes.

7. The information retrieval system as set forth in claim 5, in which said arithmetic circuit carries out an addition between said at least one of said values and said remaining values.

8. The information retrieval system as set forth in claim 2, in which said address generating unit includes

an address converter connected to said first memory and converting said address codes to modified codes representative of said values, and

an arithmetic circuit connected to said address converter and generating said target address from said values for supplying said target address to said second memory.

9. The information retrieval system as set forth in claim 8, in which said address converter includes

a shifter connected to said first memory and shifting at least one of said address codes for generating one of said modified codes, and

a mask circuit connected to said first memory and masking predetermined order-bits of another of said address codes for generating another of said modified codes.

10. The information retrieval system as set forth in claim 8, in which said arithmetic circuit is implemented by an adder supplied with said modified codes for generating said target address.

11. The information retrieval system as set forth in claim 1, in which said plural memory spaces are created in plural memory units independent of one another, and said address generating unit includes plural memory controller associated with said plural memory units so as to access to said address codes substantially in parallel.

12. The information retrieval system as set forth in claim 11, in which said address generating unit includes

an address memory including plural memory spaces spaced from one another by a distance corresponding to certain addresses and having plural groups of addressable memory locations for storing said values together with other values,

a controller connected to said first memory and said address memory and responsive to one of said address codes for reading out one of said values from one of said plural memory spaces and calculating a modified address codes on the basis of another of said address codes and said certain addresses for reading out another of said values from another of said plural memory spaces, and

an arithmetic circuit connected to said address memory and generating said target address from said values for supplying said target address to said second memory.

13. The information retrieval system as set forth in claim 12, in which said arithmetic circuit carries out an addition between said at least one of said values and said another of said values.

14. The information retrieval system as set forth in claim 1, in which said plural memory locations of said first memory is created in a single memory device, and said first memory supplies said address codes in serial to said address generating unit.

15. The information retrieval system as set forth in claim 14, in which one of said plural memory spaces have a certain number of addressable memory locations and assigned to different codes representative of one of said plural retrieval sub-codes, and another of said plural memory spaces is divided into plural memory sub-spaces for storing plural groups of codes representative of another of said plural retrieval sub-codes, wherein said plural memory sub-spaces are alternated with said certain number of addressable memory locations in said one of said plural memory spaces.

16. The information retrieval system as set forth in claim 15, in which said address generating unit includes

an address memory having plural addressable memory locations for storing said values together with other values and responsive to said address codes so as to output said values from the addressable memory locations specified by said address codes, and

an arithmetic circuit connected to said address memory and generating said target address from said values for supplying said target address to said second memory.

17. The information retrieval system as set forth in claim 16, in which said arithmetic circuit carries out an addition between said values.