INDEX COMPRESSION

• US 20090319549A1
• Filed: 06/20/2008
• Published: 12/24/2009
• Est. Priority Date: 06/20/2008
• Status: Active Grant

• Current Assignee: Perfect Search Corporation
• Original Assignee: Perfect Search Corporation
• Inventors: Millett, Ronald P.
• Granted Patent: US 8,032,495 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Compressing and decompressing compressed index lists. One or more index lists include at least a portion of the list that is compressed. A method includes reading an entry from a list. The method further includes determining that the entry indicates the start of a compressed block of the list. The compressed block is compressed using a compression algorithm including a plurality of delta pointers. Each of the delta pointers point to data store entries by reference to a difference from a reference in a previous entry in the list. An entry size indicator is referenced. The entry size indicator is configured to indicate a memory storage size for a delta pointer, and the entry size indicator supports indications for all of fixed storage sizes, variable storage sizes, and run length encoding. The compressed block of the list is decompressed according to the entry size indicator.

Claims

1. In a computing environment comprising one or more index lists, wherein at least one of the one or more index lists comprises at least a portion of the list that is compressed, a method of reading portions of a compressed index list, the method comprising:

reading an entry from a list;

determining that the entry indicates the start of a compressed block of the list, wherein the compressed block is compressed using a compression algorithm where the compressed block includes a plurality of delta pointers, wherein each of the delta pointers point to data store entries by reference to a difference from a reference in a previous entry in the list;

referencing an entry size indicator, wherein the entry size indicator is configured to indicate a memory storage size for a delta pointer, and the entry size indicator supports indications for all of fixed storage sizes, variable storage sizes, and run length encoding; and

decompressing the compressed block of the list according to the entry size indicator.

2. The method of claim 1, wherein one or more compressed blocks in the list are selected to include 64 reference entries or less.

3. The method of claim 1, wherein the entry size indicator includes a variable storage size indicator, and wherein decompressing the compressed block of the list according to the entry size indicator comprises:

(a) referencing a portion of a differential indicator, wherein the differential indicator is divided into a plurality of portions, wherein the differential indicator is divided into a plurality of portions, wherein at least some of the portions each correspond to a compressed entry in the compressed block, and wherein each of the portions in the at least some of the portions indicates a memory size of a compressed entry; and

(b) reading a compressed entry by reading a memory entry of the indicated memory size of the compressed entry; and

(c) repeating acts (a)-(b) for subsequent portions and subsequent corresponding compressed entries.

4. The method of claim 3, wherein the differential indicator is sized to correspond to a native memory bus size of a processor executing portions of the method.

5. The method of claim 3, wherein the differential indicator is divided into a number of portions, where each of the portions has an equal number of bits, and wherein the bits for each of the portions represents the number of bytes that should be read to decompress a compressed entry.

6. The method of claim 1, wherein reading an entry from a list is performed in response to reading an entry from an offset correlation table.

7. The method of claim 1, wherein reading an entry from a list is performed in response to following a pointer from a speed-up data structure, the speed-up data structure allowing for skipping of entries in the list.

8. The method of claim 1, wherein determining that the entry indicates the start of a compressed block of the list comprises determining that the entry is a negative number.

9. The method of claim 1, wherein the compressed portion comprises a sufficient number of filler entries such that the compressed portion begins and ends at native memory boundaries.

10. The method of claim 9, wherein the compressed portion is a whole integer multiple of a native memory bus size of a processor executing portions of the method.

11. In a computing environment comprising one or more index lists, wherein at least one of the one or more index lists comprises at least a portion of the list that is compressed, a method of reading portions of a compressed index list, the method comprising:

(a) reading an entry from a list;

(b) determining that the entry indicates the start of a compressed block of the list, wherein the compressed block is compressed using a compression algorithm where the compressed block includes a plurality of delta pointers, wherein each of the delta pointers point to data store entries by reference to a difference from a reference in a previous entry in the list;

(c) referencing a portion of a differential indicator, wherein the differential indicator is divided into a plurality of portions, wherein at least some of the portions each correspond to a compressed entry in the compressed block, and wherein each of the portions in the at least some of the portions indicates a memory size of a compressed entry; and

(d) decompressing a compressed entry by reading a memory entry of the indicated memory size of the compressed entry; and

(e) repeating acts (c)-(d) for subsequent portions and subsequent corresponding compressed entries.

12. The method of claim 11, wherein the method is practiced in a computing environment including one or more registers, the method further comprising loading the differential indicator into a register, and wherein referencing a portion of the differential indicator comprises reading the portion from the register.

13. The method of claim 12, wherein the method is performed in a binary system, and wherein repeating act (c)-(d) for subsequent portions and subsequent corresponding compressed entries comprises iteratively reading a predetermined number of bits and shifting the register by the predetermined number of bits.

14. The method of claim 11, wherein the differential indicator is divided into a number of portions, where each of the portions has an equal number of bits, and wherein the bits for each of the portions represents the number of bytes that should be read to decompress a compressed entry.

15. A computer readable medium comprising a data structure, the data structure comprising one or more index lists, wherein at least one of the one or more index lists comprises at least a portion of the list that is compressed, the data structure comprising:

a compressed portion, the compressed portion using a compression algorithm including a plurality of delta pointers, wherein each of the delta pointers point to data store entries by reference to a difference from a reference in a previous entry in the list;

a first field, wherein the first field comprises a flag indicator indicating the beginning of the compressed portion of a list;

an entry size indicator, wherein the entry size indicator is configured to indicate a memory storage size for the delta pointers, and the entry size indicator supports indications for all of fixed storage sizes, variable storage sizes, and run length encoding;

16. The computer readable medium of claim 15, wherein the entry size indicator includes an indicator indicating the compressed portion is using run-length encoding, and wherein the delta pointers are included in the compressed portion implicitly based on the run-length encoding.

17. The computer readable medium of claim 15, wherein the entry size indicator includes an indicator indicating variable storage sizes, and wherein the data structure further comprises a differential indicator, wherein the differential indicator is divided into a plurality of portions, wherein at least some of the portions each correspond to a compressed entry in the compressed block, and wherein each of the portions in the at least some of the portions indicates a memory size of a compressed entry.