Index compression
View Patent ↗Systems and methods for compressing an index are described. In one exemplary method, the results of a search are annotated and then encoded into one or more chunks of compressed data in accordance with the annotations of the results. The annotations include an indication of a best encoding method selected from a set of available encoding methods, and an indication of whether to switch to a new chunk during encoding or to continue encoding in the current chunk. Other methods are described and data processing systems and machine readable media are also described.
1. A machine implemented method of compressing results of a search, the method comprising:
receiving a list identifying items containing a search term, the items being listed in order by each item's unique identifier;
accumulating compression cost statistics for the list, the statistics tracking compression costs associated with available encoding methods for separately compressing each item's unique identifier;
determining a best encoding for each item in the list, wherein the best encoding for an item in the list is an available encoding method that separately compresses the item's unique identifier into a least amount of storage space in a chunk of output based on comparing the compression costs associated with available encoding methods for compressing the item's unique identifier;
annotating each item in the list in a first order by each item's unique identifier with an annotation indicating the best encoding for each of the items; and
determining whether to encode each item in the list in a same or new chunk of output based on the best encoding for each of the items, wherein the best encoding for the item is one of a plurality of available encoding methods selected from any of a bitmap encoding method, an include encoding method, and an exclude encoding method.
2. The method of claim 1 , further comprising:
encoding each of the items in the list into at least one chunk of output, wherein encoding is performed in a second order opposite to the first order by each item's unique identifier in accordance with the item's annotation indicating the best encoding for the item.
3. The method of claim 1 , wherein the items contain the search term in at least one of a content and a metadata associated with the items.
4. A machine readable medium containing executable program instructions for causing a data processing system to perform a method of compressing results of a search, the method comprising:
receiving a list identifying items containing a search term, the items being listed in order by each item's unique identifier;
accumulating compression cost statistics for the list, the statistics tracking compression costs associated with available encoding methods for separately compressing each item's unique identifier;
determining a best encoding for each item in the list, wherein the best encoding for an item in the list is an available encoding method that separately compresses the item's unique identifier into a least amount of storage space in a chunk of output based on comparing the compression costs associated with available encoding methods for compressing the item's unique identifier;
annotating each item in the list in a first order by each item's unique identifier with an annotation indicating the best encoding for each of the items; and
determining whether to encode each item in the list in a same or new chunk of output based on the best encoding for each of the items, wherein the best encoding for the item is one of a plurality of available encoding methods selected from any of a bitmap encoding method, an include encoding method, and an exclude encoding method.
5. A machine readable medium as in claim 4 , wherein the method further comprises:
encoding each of the items in the list into at least one chunk of output, wherein encoding is performed in a second order opposite to the first order by each item's unique identifier in accordance with the item's annotation indicating the best encoding for the item.
6. A machine readable medium as in claim 4 , wherein the items contain the search term in at least one of a content and metadata associated with the items.
7. A data processing system comprising:
means for receiving a list identifying items containing a search term, the items being listed in order by each item's unique identifier;
means for accumulating compression cost statistics for the list, the statistics tracking compression costs associated with available encoding methods for separately compressing each item's unique identifier;
means for determining a best encoding for each item in the list, wherein the best encoding for an item in the list is an available encoding method that separately compresses the item's unique identifier into a least amount of storage space in a chunk of output based on comparing the compression costs associated with available encoding methods for compressing the item's unique identifier;
means for annotating each item in the list in a first order by each item's unique identifier with an annotation indicating the best encoding for each of the items; and
means for determining whether to encode each item in the list in a same or new chunk of output based on the annotation indicating the best encoding for each the items, wherein the means for compressing the item's unique identifier into the least amount of storage space in the chunk of output are selected from any of a bitmap encoding means, an include encoding means, and an exclude encoding means.
8. A data processing system as in claim 7 , wherein the method further comprises:
means for encoding each of the items in the list into at least one chunk of output, wherein encoding is performed in a second order opposite to the first order by each item's unique identifier in accordance with the item's annotation indicating the best encoding for the item.
9. A data processing system as in claim 7 , wherein the items contain the search term in at least one of a content and metadata associated with the items.