# US 12,762,124 B2 · Locating a value through deterministic searching > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,762,124 B2 - Document ID: US12762124B2 - Status: Granted - Kind: B2 - Application number: 18/767,767 - Filed: 2024-07-09 - Published: 2024-10-31 - Granted: 2026-10-13 - Earliest claimed: 2015-09-04 - Assignees: Pure Storage, Inc. - Applicants: Pure Storage, Inc - Inventors: Ethan L. Miller - Web page: https://patentgrep.com/patent/US12762124B2 ## CPC - G06F 16/2455: Query execution - G06F 16/2255: {Hash tables} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the result is a determination that the value is not contained in the table. ### Claim 3 (depends on 1) The method of claim 1, wherein each bucket includes a transit table that indicates whether a corresponding third set of bits from the signature table have a same prefix as a preceding set of signature bits from the signature table. ### Claim 4 (depends on 1) The method of claim 1, wherein the method uses a transit table, the prefix table, and the signature table to determine whether the value is contained in the table. ### Claim 5 (depends on 1) The method of claim 1, wherein the value being searched for is an entirety of a key stored in the table and wherein the indicator comprises a unary counter. ### Claim 6 (depends on 1) The method of claim 1, wherein determining a result indicates an approximate location in the table at which the value would be found. ### Claim 7 (depends on 1) The method of claim 1, wherein identifying the bucket comprises: determining whether the prefix table of the bucket has a bit set according to prefix bits of the value; and determining whether the signature table of the bucket contains the signature bits from the value. ### Claim 8 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. ### Claim 9 (depends on 8) The computer-readable media of claim 8, wherein determining the result includes determining that the value is not contained in the table. ### Claim 10 (depends on 8) The computer-readable media of claim 8, wherein the bucket includes a transit table indicating whether a corresponding third set of bits from the signature table have a same prefix as a preceding set of signature bits from the signature table. ### Claim 11 (depends on 8) The computer-readable media of claim 8, wherein the transit table, prefix table, and signature table are used to determine whether the value is contained in the table. ### Claim 12 (depends on 8) The computer-readable media of claim 8, wherein the value is an entirety of a key stored in the table and wherein the indicator comprises a unary counter. ### Claim 13 (depends on 8) The computer-readable media of claim 8, wherein determining a result indicates an approximate location in the table at which the value would be found the container. ### Claim 14 (depends on 8) The computer-readable media of claim 8, wherein the bucket is one of a plurality of buckets in a summary table that includes encoding locality of hash values of a hash table into transit tables of the plurality of buckets. ### Claim 15 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. ### Claim 16 (depends on 15) The storage system of claim 15, wherein the result includes a determination that the value is not contained in the table. ### Claim 17 (depends on 15) The storage system of claim 15, further comprising: the one or more processors configured to generate a summary table having a plurality of buckets, wherein each bucket of the plurality of buckets has a transit table that indicates whether a corresponding third set of bits from the signature table have a same prefix as a preceding set of bits from the signature table. ### Claim 18 (depends on 15) The storage system of claim 15, wherein the one or more processors use a transit table, the prefix table and the signature table to determine whether the value is contained in the table. ### Claim 19 (depends on 15) The storage system of claim 15, wherein the value being searched for is an entirety of a key stored in the table and wherein the indicator comprises a unary counter. ### Claim 20 (depends on 15) The storage system of claim 15, wherein determining the result indicates an approximate location in the table at which the desired value is found.