Pure Storage, Inc.
DYNAMICALLY RESIZABLE STRUCTURES FOR APPROXIMATE MEMBERSHIP QUERIES

Abstract:

A computing or storage system constructs a table in memory, and constructs a summary table that summarizes the table. The summary table is for determining whether there is likely an entry for a value in the table. The summary table has buckets pointed to by address fields of values. The first bucket in the summary table is split into a second bucket and a third bucket. Prior to the split, the first bucket is pointed to by a first address field of a first value. After the split, the second bucket and the third bucket are pointed to by the first address field plus one extra bit derived from a remainder of the first value.