Method and apparatus for representing and interrogating an index in a digital memory

• US 5,293,616 A
• Filed: 10/22/1991
• Issued: 03/08/1994
• Est. Priority Date: 10/22/1991
• Status: Expired due to Fees

• Current Assignee: Orin O. Flint
• Original Assignee: Orin O. Flint
• Inventors: Flint, Orin O.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US07/780,203
• Time in Patent Office: 868 Days
• Field of Search: 395/600, 364/DIG. 1 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method apparatus for retrieval of data from an index database is disclosed. Each address in an index memory corresponds to an attribute that may be possessed by one or more records in the index database. Index memory datawords located at each index memory address include a number of binary bits equal to the number of records in the index database. If a record possesses an attribute, the value of the bit at a position corresponding to the record'"'"'s address in that attribute'"'"'s index memory dataword will be a binary "1". Priority encoder circuitry is provided to locate the positions of each of the 1'"'"'s in the index memory datawords so that all of the records in the index database that possess an attribute can be determined. Logic circuitry is provided to combine index memory datawords logically to form new datawords that can be used to identify records that possess either all of a plurality of selected attributes, or one or more of a plurality of selected attributes. This retrieval system employs parallel hardware circuitry to increase data retrieval speed.

Claims

1. A method for locating and retrieving data from an index database comprising the steps of:

storing records to be located and retrieved in an index database;

selecting at least one attribute that may be possessed by one or more records to be retrieved from the index database;

inputting said at least one attribute into a processing means;

said processing means including a processor memory and an index memory, said index memory containing a plurality of datawords located at addresses corresponding to said at least one attribute possessed by said one or more records in said index database;

determining the identity of an address in the index memory which corresponds to said at least one selected attribute;

reading a dataword from said index memory which is stored therein at the location corresponding to the address specified by said at least one selected attribute, said dataword including a plurality of binary bits with each said bit corresponding to a record in said index database; and

determining from the values of the bits in the dataword, the one or more records in said index database which possess said attributes.

2. The method of claim 1 wherein the step of determining from the value of the bits in the dataword comprises determining the positions of all of the bits in the dataword which are a binary "1", and using said positions to address a look up table in said processor memory which contains the identities of the one or more records in the index database that possess the selected at least one attribute.

3. The method of claim 2, wherein more than one attribute is selected, and the datawords read from the index memory for each of the attributes are logically ANDed to form a new dataword that can be used to determine which records in the index database possess all of the selected attributes.

4. The method of claim 2, wherein more than one attribute is selected, and the datawords read from the attribute memory for each of the attributes are logically ORed to form a new dataword that can be used to determine which records in the index database possess one or more of the selected attributes.

5. A data locating and retrieval system for locating and retrieving data from an index database comprising:

a) processor means;

b) an index database interfaced to said processor means containing a plurality of records;

c) at least a first match determination circuit interfaced to said processor means and including;

i) an index memory containing a plurality of datawords, each said dataword being specified by an index memory address and including a plurality of binary bits, each of which correspond to an address of a record in said index database; and

ii) means to determine the binary values of each of the bits of one or more selected datawords of said index memory;

d) means to input one or more selected attributes to said processor means which are to be matched with records in said index database; and

e) processor memory means interfaced to said processor means including;

i) means for mapping each selected attribute to an address in said index memory; and

ii) means for mapping each bit of the datawords in said index memory at the one or more addresses corresponding to each selected attribute to a corresponding address of each of said records in said index database;

whereby, said processor means can determine the identity of any records in said index database which possess the selected attributes from the values of the bits of each corresponding index memory dataword.

6. The system of claim 5 further including at least a second match determination circuit interfaced to said processor means in parallel with said first match determination circuit.

7. The system of claim 5 wherein said match determination circuit further includes means to combine selected index memory datawords logically to form a new dataword which can be used to determine which records of said index database possess more than one selected attribute.

8. The system of claim 7 wherein said means to combine comprises a parallel binary accumulator interfaced to said index memory.

9. The system of claim 5 wherein said means in said match determination circuit to determine the binary values of each of the bits of one or more selected datawords of said index memory comprises means to determine the bit positions of all binary "1"s in each selected dataword.