Interactive data retrieval apparatus

• US 4,433,392 A
• Filed: 12/11/1981
• Issued: 02/21/1984
• Est. Priority Date: 12/19/1980
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beaven, Paul A.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Niessen, William G.
• Application Number:
  US06/329,831
• Time in Patent Office: 802 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 340/146.2, 340/146.3 WD, 382/34, 382/40, 382/57
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An interactive data retrieval apparatus in which a data base store is searched by content using search keys entered by an operator. Dedicated hardware includes a plurality of search modules and apparatus for clocking the byte-wide data stream read from the data store through successive search modules. In each module, the data is compared with an entered search key. When a match is found between the data stream and the search keys, the data record is displayed to the operator. The apparatus can detect near matches to allow for misspellings etc. In one embodiment of the search module, a plurality of comparison cells perform byte-equality operations on search key data stored in a search key register and the data stream. In a second embodiment, an associative store contains the n-character search key, the associative store being addressed by each character in the data stream as it is clocked past its data port. n shift registers are connected to the outputs of the associative store and are shifted in synchronism with the data stream.

Claims

1. An interactive data retrieval apparatus comprising

a data store to store data records,

a keyboard to enable an operator to enter search key data and control data,

a data processor to control the storage and retrieval of data records in said data store, and

search means to compare search key data entered by the operator with data read from said store thereby to locate a data record within said data store, the search means including,

a search store for storing said entered search key data,

a data stream buffer and means for clocking successive bytes of data records forming a data stream which is read from said data store through said data stream buffer, and

comparison logic means to compare the contents of said data stream buffer within the contents of said search store and to indicate that a match has occurred

wherein the improvement comprises,

a plurality of comparison cells in said comparison logic means and means connecting the comparison cells to compare the contents of corresponding positions of said data stream buffer and said search store and to compare the contents of positions of said data stream buffer adjacent said corresponding positions with said corresponding positions of said search store, and

logic combination means to combine logically the outputs of predetermined groups of said comparison cells to give indictions of an exact match and matching within a predetermined distance

when said search key data is the same as said data stream or differs from said data stream but only by a predetermined amount.

2. Apparatus as defined in claim 1, wherein said search means includes a plurality of search modules each having a search store in the form of an associative memory,

a data stream buffer and means connecting said data stream buffer to said associative search store for receiving successive characters in said data stream from said data store, and

a plurality of shift registers connected to said associative search store to receive the outputs therefrom and

logic combination means to combine logically the outputs of said shift registers,

means in said clocking means to clock said data stream through said data stream buffer and said associative store outputs through said shift registers in synchronism.

3. Apparatus as defined in claim 2, wherein said logic combination means includes

means for logically combining the contents of the last stages of each shift register for detecting a near match of the search keys with the data stream.

4. Apparatus as defined in claims 2 or 3, further comprising means to collate the output of each search module before indicating a match between the entered search key data and a data record in the data stream.