Amazon.com, Inc.
Scalable parallel elimination of approximately subsumed sets

Abstract:

Techniques for Scalable parallel elimination of approximately subsumed sets are described. A method for Scalable parallel elimination of approximately subsumed sets includes identifying a first plurality of blocks based at least on a plurality of records stored in a storage service of a provider network, determining a plurality of subsumption relationships between blocks from the first plurality of blocks, retaining a first subset of the first plurality of blocks and demoting a second subset of the first plurality of blocks based at least on the plurality of subsumption relationships, and iteratively performing dynamic blocking based at least on the first subset of the plurality of matching blocks and the second subset of the plurality of matching blocks to generate a subsequent pluralities of blocks.