A STORAGE SYSTEM FOR RANDOMLY NAMED BLOCKS OF DATA

摘要

An index is constructed that is suitable for indexing a large set of records identified by randomly distributed record names and for answering membership queries about the set. The index has more than one level and the first-level index typically resides in RAM. Like a Bloom Filter, the first level index provides a non-membership indication with certainty and a membership indication with a controlled probability of error. Unlike a Bloom filter, entries in the first level index correspond uniquely to distinct records. Use is made of the statistical properties of a sorted list of random numbers in order to represent the first level index compactly.