Locating a value through deterministic searching
AssigneePure Storage, Inc.
InventorEthan L. Miller
Life of this patent
Estimating the term…
Abstract
A method for efficiently supporting deletion in a probabilistic data structure, and related computing or storage system are described. A processor, computing system or storage system constructs a table and a summary table for determining whether there is an entry for a value in the table. The summary table has buckets pointed to by address fields of values. Each bucket has a prefix table, a transit table, signature table and a first indicator. The system tracks deletion and addition of items of the table and summary table through the first indicators.
Claims20
A method, comprising:
- separating a value into a first set of bits, a second set of bits, and a third set of bits;
- identifying a bucket associated with an address specified by the first set of bits, the bucket comprised of a prefix table with bits set corresponding to the second set of bits and a signature table containing the third set of bits;
- maintaining an indicator associated with at least one of the prefix table or the signature table;
- and
- determining, by a processor, a result based on a function of the prefix table and the signature table and the second set of bits and the third set of bits, and the indicator, the result indicating whether the value matches a value in a table.
A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to perform a method comprising:
- separating a value into a first set of bits, a second set of bits, and a third set of bits;
- identifying a bucket at an address specified by the first set of bits, the bucket comprised of a prefix table with bits set corresponding to the second set of bits and a signature table containing the third set of bits;
- maintaining an indicator associated with at least one of the prefix table or the signature table, the indicator being maintained independently of updates to the prefix table and the signature table;
- and
- determining, by a processor, a result based on a function of the prefix table and the signature table and the second set of bits and the third set of bits, the result indicating whether the value matches a value in a table.
A storage system, comprising:
- one or more processors configured to determine if a value is stored in a table, the determining comprising:
- separating a value into a first set of bits, a second set of bits, and a third set of bits, identify a bucket at an address specified by the first set of bits, the bucket comprised of a prefix table with bits set corresponding to the second set of bits and a signature table containing the third set of bits;
- maintaining an indicator associated with at least one of the prefix table or the signature table, the indicator being maintained independently of updates to the prefix table and the signature table;
- and
- determining, by the one or more processors, a result based on a function of the prefix table and the signature table and the second set of bits and the third set of bits, the result indicating whether the value matches a value in the table.
Dependencies are inferred from the claim text.