Method and apparatus using run length encoding to evaluate a database

• US 6,446,066 B1
• Filed: 08/25/2000
• Issued: 09/03/2002
• Est. Priority Date: 07/25/1997
• Status: Expired due to Fees

• Current Assignee: Justsystems Evans Research Incorporated
• Original Assignee: Claritech Corporation
• Inventors: Horowitz, Michael L.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/645,953
• Time in Patent Office: 739 Days
• Field of Search: 707/3, 707/6, 707/5, 707/101
• US Class Current: 707/759
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/3341 using boolean model
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The present invention provides a method and apparatus for generating a database search result. The creation of the search result is achieved by representing the subdocument lists of an inverted database with encoded bit strings. The encoded bit strings are space efficient methods of storing the correspondence between terms in the database and their occurrence in subdocuments. Logical combinations of these bit strings are then obtained by identifying the intersection, union, and/or inversion of a plurality of the bit strings. Since keywords for a database search can be identified by selecting the terms of the inverted database, the logical combinations of bit strings represent search results over the database. This technique for method for generating a search result is computationally efficient because computers combine bit strings very efficiently. Also, the search elements of the present invention are not just limited to keywords. The search elements also include types of fields (e.g., date or integer fields) or other extracted entities.

Claims

1. A method of storing data, comprising:

creating a plurality of subdocuments of approximately equal length from a database;

representing the occurrence of a plurality of terms in each of said subdocuments by an encoded bit string;

combining a plurality of said bit strings, wherein said combination represents a search result from said database.

2. The method of claim 1, further comprising generating a comparison list indicating the relation between a first encoded bit string and a second encoded bit string.

3. The method of claim 2, wherein said comparison list indicates the intersection between said first and said second encoded bit strings.

4. The method of claim 2, wherein said comparison list indicates the union between said first and said second encoded bit strings.

5. An apparatus for storing data, comprising;

a computer coupled to a disk storage unit, said disk storage unit stores a database, said computer creates a plurality of subdocuments of approximately equal length from said database;

said computer represents the occurrence of a plurality of terms in each of said subdocuments by an encoded bit string;

said computer combines a plurality of said encoded bit strings; and

said computer stores said plurality of said encoded bit strings.

6. The apparatus of claim 5, wherein said processor further generates a comparison list that indicates the relation between a first and a second encoded bit string.

7. The apparatus of claim 5, wherein said comparison list indicates the intersection between said first and said second encoded bit string.

8. The apparatus of claim 5, wherein said comparison list indicates the union between said first and said second encoded bit string.

9. A method of retrieving data from a database, comprising the steps of:

creating a plurality of subdocuments from a database;

representing the occurrence of at least one term in said subdocuments by an encoded bit string;

identifying said subdocuments containing said bit string; and

retrieving said subdocuments containing said bit string.

10. The method of claim 9, wherein said encoded bit string represents the number of sequential subdocuments that contain the occurrence of said term.

11. The method of claim 9 further comprising the step of storing said subdocuments containing said bit string.