Method for generating a compressed index of information of records of a database

• US 6,016,493 A
• Filed: 04/03/1998
• Issued: 01/18/2000
• Est. Priority Date: 08/09/1996
• Status: Expired due to Term

• Current Assignee: Eureka Database Solutions, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Burrows, Michael
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/054,431
• Time in Patent Office: 655 Days
• Field of Search: 707/101, 707/102, 707/2, 707/3, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A computer implemented method for generating a compressed index of information. The information is stored as a plurality of records in a database. Indexable portions of information are sequentially parsed to generate words and metawords. The words represent the portions, and the metawords represent attributes of the portions. A location is sequentially assigned to each word and metaword in the order that the portions are parsed to form pairs. The pairs are sorted first according to the words and metawords, and second according to the locations. Index entries are written to a memory for each unique word and metaword. Each index entry includes a word entry or a metaword entry, and one or more location entries. The word and metaword entries use a prefix encoding which indicates the number of bytes that the unique word or metaword of a next index entry has in common with the unique word or metaword of a previous index entry. The location entries use a delta value encoding.

Claims

1. A computer implemented method for generating a compressed index of information, the information represented by a plurality of information portions, the method comprising the steps of:

encoding a representation of a first of the plurality of information portions; and

storing the encoded representation of the first of the plurality of information portions in the index of information;

wherein the encoded representation indicates a number of bytes that the first of the plurality of information portions has in common with a representation of a second of the plurality of information portions and bytes that differ between the first of the plurality of information portions and a representation of the second of the plurality of information portions.

2. The method of claim 1, further comprising the step of:

generating a metaword identifying a common attribute of at least a subset of the plurality of information;

wherein a representation of the generated metaword is the first of the plurality of information.

3. The method of claim 1, further comprising the step of:

sorting the plurality of information portions to facilitate the encoding.

4. The method of claim 1, wherein each of the plurality of information portions has an associated location representation, comprising the step of:

storing the location representation of the first of the plurality of information portions with the first entry;

wherein the location representation is a delta value encoding.

5. A system for generating a compressed index of information, the information represented by a plurality of information portions, comprising:

a memory for storing the index; and

a processor configured to;

encode a representation of a first of the plurality of information portions; and

store the encoded representation of the first of the plurality of information portions in the index of information;

wherein the encoded representation indicates a number of bytes that the representation of the first of the plurality of information portions has in common with a representation of a second of the plurality of information portions and bytes that differ between the representation of the first of the plurality of information portions and a representation of the second of the plurality of information portions.

6. The system of claim 5, wherein the processor is further configured to:

generate a metaword identifying a common attribute of at least a subset of the plurality of information;

wherein a representation of the generated metaword is the first of the plurality of information.

7. The system of claim 5, wherein the processor is further configured to:

sort the plurality of information portions to facilitate the encoding.

8. The system of claim 5, wherein each of the plurality of information portions has an associated location representation and the processor is further configured to:

store the location representation of the first of the plurality of information portions with the first entry;

wherein the location representation is a delta value encoding.

9. The system of claim 5, further comprising:

a network connected to the processor;

wherein the network facilitates transfer of the information represented by the plurality of information portions.

10. An article of manufacture for generating a compressed index of information, the information represented by a plurality of information portions, the article of manufacture comprising:

at least one processor readable carrier; and

instructions contained on the carrier;

wherein the instructions are configured to be readable from the at least one carrier by one or more processors and thereby cause the one or more processors to operate so as to;

encode a representation of a first of the plurality of information portions; and

store the representation of the first of the plurality of information portions in the index of information;

wherein the encoded representation indicates a number of bytes that the representation of the first of the plurality of information portions has in common with a representation of a second of the plurality of information portions and the bytes that differ between the representation of the first of the plurality of information portions and a representation of the second of the plurality of information portions.

11. The article of manufacture of claim 10, wherein the instructions are further configured to cause the at least one processor to operate so as to:

generate a metaword identifying a common attribute of at least a subset of the plurality of information;

wherein a representation of the generated metaword is the first of the plurality of information.

12. The article of manufacture of claim 10, wherein the instructions are further configured to cause the at least one processor to operate so as to:

sort the plurality of information portions to facilitate the encoding.

13. The article of manufacture of claim 10, wherein each of the plurality of information portions has an associated location representation, and the instructions are further configured to cause the at least one processor to operate so as to:

store the location representation of the first of the plurality of information portions with the first entry;

wherein the location representation is a delta value encoding.