TEMPORAL CLONES TO IDENTIFY VALID ITEMS FROM A SET OF ITEMS

摘要

Techniques are provided for using bitmaps to indicate which items, in a set of items, are invalid. The bitmaps include an “active” bitmap and one or more “temporal clones”. The active bitmap indicates which items in the set are currently valid. The temporal clones are outdated versions of the active bitmap that indicate which items in the set were invalid at previously points in time. Temporal clones may not be very different from each other. Therefore, temporal clones may be efficiently compressed. For example, a bitmap may be selected as a “base bitmap”, and one or more other bitmaps are encoded using delta encoding. Run length encoding may then be applied to further compress the bitmap information. These bitmaps may then be used to determine which items are valid relative to past-version requests.