# US 12,216,788 B2 · Meta-estimation of bloom filters with vectors of counts > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,216,788 B2 - Document ID: US12216788B2 - Status: Granted - Kind: B2 - Application number: 17/917,083 - Filed: 2021-10-05 - Published: 2023-05-18 - Granted: 2025-02-04 - Earliest claimed: 2021-10-05 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Preston Wooju Lee; Craig William Wright; Joseph Sean Cahill Goodknight Knightbrook; Evgeny Skvortsov - Web page: https://patentgrep.com/patent/US12216788B2 ## CPC - G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries} - G06F 16/24: Querying - G06F 21/60: Protecting data - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems and methods for the meta-estimation of data structures representing identifiers are disclosed. The system maintain one or more data records comprising one or more identifiers and one or more attributes. Using the data records, the system can generate a first data structure, such as a probabilistic data structure, that represents the plurality of data records. The first data structure can have a plurality of registers. The system can identify a subset of the plurality of registers that are equal to a predetermined value, and generate a second data structure that represents the subset of the plurality of registers. The system can then store the second data structure as a meta-estimation of the first, and can utilize the second data structure in further processing operations. ## Claims ### Claim 1 A system for improving data sketch processing in data processing systems, comprising: one or more processors; and one or more memory devices storing computer-readable instructions that, when implemented, cause the one or more processors to perform operations, the operations comprising: retrieving one or more generation parameters corresponding to a first initial sketch comprising a plurality of first initial sketch registers, wherein a subset of the plurality of first initial sketch registers are populated according to the one or more generation parameters and based at least in part on hashes of a plurality of data records; retrieving a first meta-estimation sketch comprising a plurality of first meta-estimation sketch registers populated based at least in part on hashes of index values of each of the subset of the plurality of first initial sketch registers; and determining, using the one or more generation parameters, one or more set properties using the first meta-estimation sketch and a second meta-estimation sketch. ### Claim 2 (depends on 1) The system of claim 1, wherein the second meta-estimation sketch comprises a plurality of second meta-estimation sketch registers populated based at least in part on hashes of index values of each of a subset of a plurality of second initial sketch registers of a second initial sketch. ### Claim 3 (depends on 2) The system of claim 2, wherein the one or more set properties comprise a cardinality estimate of a union of the first initial sketch and the second initial sketch. ### Claim 4 (depends on 1) The system of claim 1, wherein determining the one or more set properties comprises determining an intersection of the first meta-estimation sketch and the second meta-estimation sketch. ### Claim 5 (depends on 1) The system of claim 1, wherein determining the one or more set properties comprises determining a union of the first meta-estimation sketch and the second meta-estimation sketch. ### Claim 6 (depends on 1) The system of claim 1, wherein the first initial sketch is a bloom filter sketch. ### Claim 7 (depends on 1) The system of claim 1, wherein the first initial sketch is an exponential bloom filter sketch. ### Claim 8 (depends on 1) The system of claim 1, wherein the plurality of data records corresponds to a plurality of identifiers associated with one or more attributes. ### Claim 9 (depends on 1) The system of claim 1, wherein the operations further comprise: generating the first meta-estimation sketch by, for a respective index value of the index values of each of the subset of the plurality of first initial sketch registers: determining a respective first meta-estimation sketch index based on hashing the respective index value; and incrementing a respective one of the plurality of first meta-estimation sketch registers associated with the respective first meta-estimation sketch index. ### Claim 10 A system for improving data sketch processing in data processing systems, comprising: one or more processors; and one or more memory devices storing computer-readable instructions that, when implemented, cause the one or more processors to perform operations, the operations comprising: generating a first initial sketch comprising a plurality of first initial sketch registers, wherein a subset of the plurality of first initial sketch registers are populated according to one or more generation parameters and based at least in part on hashes of a plurality of data records; and generating a first meta-estimation sketch comprising a plurality of first meta-estimation sketch registers populated based at least in part on hashes of index values of each of the subset of the plurality of first initial sketch registers. ### Claim 11 (depends on 10) The system of claim 10, wherein the first initial sketch is a bloom filter sketch. ### Claim 12 (depends on 10) The system of claim 10, wherein the plurality of data records corresponds to a plurality of identifiers associated with one or more attributes. ### Claim 13 (depends on 10) The system of claim 10, wherein the operations further comprise: generating the first meta-estimation sketch by, for a respective index value of the index values of each of the subset of the plurality of first initial sketch registers: determining a respective first meta-estimation sketch index based on hashing the respective index value; and incrementing a respective one of the plurality of first meta-estimation sketch registers associated with the respective first meta-estimation sketch index. ### Claim 14 (depends on 10) The system of claim 10, wherein the operations further comprise: receiving, from a computing device, a meta-estimation sketch request; and transmitting, to the computing device and responsive to the meta-estimation sketch request, the first meta-estimation sketch. ### Claim 15 (depends on 14) The system of claim 14, wherein the meta-estimation sketch request identifies at least one parameter for the identifiers or the attributes to be represented in the first initial sketch. ### Claim 16 (depends on 14) The system of claim 14, wherein the meta-estimation sketch request contains the one or more generation parameters of the first initial sketch. ### Claim 17 (depends on 10) The system of claim 10, wherein the one or more generation parameters include at least one parameter selected from a type of hash function used, a number of hash functions used, and a number of registers. ### Claim 18 A method for improving data sketch processing in data processing systems, comprising: maintaining, by a data processing system comprising one or more processors and a memory, a plurality of data records comprising a plurality of identifiers and one or more attributes; generating, by the data processing system, a first data structure that represents the plurality of data records, the first data structure having a plurality of first registers, wherein at least one of the plurality of first registers is populated based on hashes of each of the plurality of identifiers; identifying, by the data processing system, a subset of the plurality of first registers that are equal to a predetermined value, each of the subset of the plurality of first registers identified by an index value; generating, by the data processing system, a second data structure that represents the subset of the plurality of first registers, the second data structure having a plurality of second registers, wherein at least one of the plurality of second registers is populated based on hashes of the index values of each of the subset of the plurality of first registers; and storing, by the data processing system, in the memory, the second data structure that represents the subset of the plurality of first registers. ### Claim 19 (depends on 18) The method of claim 18, further comprising: retrieving, by the data processing system, a third data structure having a plurality of third registers, each of the plurality of third registers corresponding to a respective one of the plurality of second registers of the second data structure; and determining, by the data processing system, an intersection value of information represented by the second data structure and information represented by the third data structure using the second data structure and the third data structure. ### Claim 20 (depends on 19) The method of claim 19, further comprising determining, by the data processing system, a union value of the information represented by the second data structure and the information represented by the third data structure using the intersection value.