Method of using signature subsets for indexing a textual database

• US 4,991,087 A
• Filed: 08/18/1988
• Issued: 02/05/1991
• Est. Priority Date: 08/19/1987
• Status: Expired due to Fees

• Current Assignee: Forbes J. Burkowski, Marke S. Krebs
• Original Assignee: Forbes J. Burkowski, Marke S. Krebs
• Inventors: Burkowski, Forbes J., Krebs, Marke S.
• Primary Examiner(s): HARRELL, ROBERT B
• Application Number:
  US07/233,601
• Time in Patent Office: 901 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300, 371/22.3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method of operating a computer system to store and retrieve information in a database uses a signature file of the database that is divided into subsets. A word signature is mapped to a particular subset during creation of the file and the same mapping information is used to retrieve the information in response to a query word. Each word signature is a logical word signature and has two components a physical word signature and a subset designation field. In this way, when information is retrieved from the database, only that subset containing the relevant word signature is scanned. The signature file is automatically created by the system as the database is stored on the data storage modules. During retrieval, the control reviews information received from the data storage means and if a match occurs between a physical word signature for a query word and a particular physical word signature arriving from the input section, the control sends the physical word signature to the FIFO buffer in memory together with the document identifier located subsequent to the matched physical word signature. The control then moves on to process the next physical word signature received from the data storage means. If there is no match, the control ignores the physical word signature and moves on to process the next physical word signature received from the data storage means. The control is effectively capable of processing several query words in parallel.

Claims

1. A method of operating a computer system to store and retrieve information in a database, said computer system having data processing means, memory means and data storage means capable of containing data records, said method comprising the steps of:

(a) storing the database on the data storage means;

(b) during loading, said system automatically creating for the database a signature file which is divided into subsets, mapping a word signature to a particular subset during creation of the file and storing said signature file subsets on said data storage means;

(c) during retrieving, after the signature file is created, entering at least one query word into the system;

(d) said system automatically creating a signature for each query word entered into the system;

(e) scanning for a word signature and retrieving the corresponding data from said database in response to a query word by using the same mapping information that was used to store the word signature in a particular subset, said system matching the signature of a query word with at least one signature in one subset of said signature file if such an appropriate word signature exists in this subset.

2. A method as claimed in claim 1 comprising the steps of, when matching a word signature in rsponse to a query word, having the system scan only that subset of the signature file containing a physical word signature that matches a signature for the query word.

3. A method as claimed in claim 2 comprising the steps of, during creation of the signature file for a particular document, automatically ignoring all common words in said document, automatically computing a logical word signature for each remaining word in the document and, automatically eliminating any duplicate logical word signatures in the document.

4. A method as claimed in claim 3 including the steps of, during the creation of the signature file, automatically dividing the signature file into a large number of subsets, generating each logical word signature so that it has two components, a physical word signature concatenated to a subset designation field, mapping all logical word signatures having the same subset designation field to the same subset, resulting in the storage in that subset of the physical word signature component of that logical word signature.

5. A method as claimed in claim 4 comprising the steps of, during the creation of the subsets, adding a document identifier, serving to identify the document from which a particular physical word signature or group of physical word signatures is derived, to that physical word signature or group of physical word signatures derived from the same document.

6. A method as claimed in claim 5 wherein the logical word signature is m-bits in length, where m ranges from 8 to 32, and has an n-bit physical word signature concatenated to a subset designation field which selects one of several subsets, where n ranges from 8 to 20.

7. A method as claimed in claim 6 wherein the representation of the document identifiers follows one or more physical word signatures stored within the signature file.

8. A method as claimed in claim 3 wherein the data storage device is a disk, said method comprising the steps of fetching one or more subsets using the data processing means in conjunction with a processor that scans a data stream emanating from said disk looking for pre-specified physical word signatures.

9. A method as claimed in claim 8 wherein each n-bit physical word signature is used as an address for a RAM table with two to the power n locations, where n is an integer ranging from 8 to 20, each location containing one bit, the processor controlled in such a fashion that it ignores physical word signatures when the addressed RAM bit location indicates a word signature of no interest to the query, and places any physical word signature into a FIFO buffer, for future reference, when the addressed RAM bit location contains the complementary bit value, the processor filtering out the physical word signatures of interest.

10. A method as claimed in claim 9 including the steps of, during creation of the signature file, generating a series of groups to make up each subset, each group having a series of physical word signatures, each group being terminated by a representation of a document identifier, each document identifier having a high, middle and low order field, the representation of the document identifier of a first group in the subset actually having a high, middle and low order field, the representations of document identifiers from subsequent groups always having a low order field but only having a middle order field or a high order field in addition to the low order field when necessary to reflect a change or changes in these fields from the document identifier represented in the immediately prior group, the document identifiers being arranged in ascending order.

11. A method as claimed in claim 10 including the steps of, during retrieval of information from the data storage means, using a processor to scan a data stream from the data storage means, the processor pushing all representations of document identifiers having a high order field into the FIFO buffer, the processor saving the last middle order field encountered in the data stream in a register for future use, said last middle order field encountered being inserted into the FIFO buffer along with the low order field that terminates a particular group only if the RAM table has indicated a match between the physical word signature derived from the query keyword and a physical word signature in the particular group.

12. A method as claimed in claim 1 wherein subsets are arranged on the data storage device with free space between consecutive subsets to allow for an increase in size of the subsets as the database is increased in size, said method comprising the steps of increasing the size of the database by adding additional information to the end thereof and in the size of the signature file by adding additional word signature groups at the end of one or more subsets.

13. A method as claimed in claim 12 wherein a logical word signature is to be associated with its corresponding word, the association between the logical word signature and the corresponding word being retained in a word dictionary, the method including the steps of choosing the subset designation field in such a way as to help in maintaining uniform lengths of all subsets and choosing the physical word signatures to ensure a one to one mapping between the logical word signatures and the corresponding word.

14. A method of operating a computer system for storing and retrieving information in a database, said computer system having a processor, a memory with address lines and a FIFO buffer, said processor having an input section, an output section and a control, said method comprising the steps of:

(i) storing the database in the data storage means;

(ii) during loading of the database, said system automatically creating for the database a signature file which is divided into subsets, mapping a word signature to a particular subset during creation of the file and storing said signature file subsets on said data storage means;

(iii) during retrieving, after the signature file is created, entering at least one query word into the system;

(iv) said system automatically creating a signature for each query word entered into the system;

(v) in response to a query word, said input section receiving information from said data storage means, said control reviewing said information and sending all word signatures to said address lines of said memory, said memory providing information to the control to enable it to determine whether a particular word signature in the input section matches a signature for said query word if a match occurs,

(a) the control sending the word signature to said FIFO buffer, the control remembering that a match has occurred and sending the document identifier located subsequent to the matched word signature to the FIFO buffer, the control then moving on to process the next word signature received from the data storage means and so on;

if there is no match,

(b) the control ignoring the word signature and moving on to process the next signature word received from the data storage means and so on;

the control thereby effectively being capable of processing several query words in parallel.