Patent Description:
Collecting and analyzing data about different objects in a digital environment (e.g., online interactions, components, resources, etc.) can be beneficial to providers of content, products, and/or services. In some cases, providers can aggregate data for numerous (e.g., millions or billions) objects to, for example, improve the provider's services and/or improve a user online experience. For example, providers may aggregate the data for components or resources of a server farm to determine how frequently components of the server farm are failing (or operating in a certain manner). As another example, providers may aggregate the data about several devices interacting with certain content to determine how frequently these devices interact with the content. These types of operations, particularly when performed on large datasets, can present significant technical challenges in efficiently processing, querying, and storing the data, and obtaining accurate results can cause significant system latency.

<CIT> relates to user events of a platform that are processed to extract aggregate information about users of the platform at an event processor. This document states that a memory-efficient way of obtaining an approximate unique user count across many nodes is to use a probabilistic data structure, such as HyperLogLog++. This document proposes that, to compute the unique number of users for a certain query, it is sufficient to simply count the boundaries between different users who satisfy an applied filter, without any requirement to store a record of all the user IDs encountered so far.

<CIT> relates to user events that are processed to estimate a unique user count. This document states that the "LogLog" family of cardinality estimation techniques provide efficient means of estimating a unique user count across a set of user events and that the unique user count can be estimated from final hash bucket values with a variety of averaging methods. It proposes that, in response to an aggregation query (unique user and interaction) counts may be generated for several buckets.

The object of the invention is solved by the features of the independent claims. In general, one innovative aspect of the subject matter described in this specification can be embodied in methods that include the operations of obtaining activity data for a plurality of objects in a dataset, wherein each object in the dataset performs activities in a digital environment and the activity data represents the activities; for each data item in the dataset: generating, using an identifier for an object specified in the data item, a hashed parameter for the object, wherein the hashed parameter has a binary representation; identifying a register from among a set of registers based on the binary representation of the hashed parameter, wherein each register in the set of registers is used to store data about objects in the dataset; determining, based on the binary representation of the hashed parameter, that the hashed parameter for the object contributes to an aggregation amount that specifies a number of occurrences of the object in the dataset; and in response to determining that the hashed parameter for the object contributes to the aggregation amount, updating the aggregation amount stored in the register; and generating, based on aggregate amounts stored in the set of registers, a reporting output that indicates a set of data items, wherein each data item identifies an estimated number of objects in the dataset that performed activities in the digital environment at a particular aggregation amount. Other embodiments of this aspect include corresponding systems, devices, apparatus, and computer programs configured to perform the actions of the methods. The computer programs (e.g., instructions) can be encoded on computer storage devices.

In some implementations, each object represents a user; and an aggregation amount represents a frequency value.

Identifying a register from among a set of registers based on the binary representation of the hashed parameter, comprises: identifying a first portion of the binary representation of the hashed parameter; and identifying the register using the first portion of the binary representation of the hashed parameter.

Each register in the set of registers comprises a data structure that stores data about a received hashed parameter, wherein the data structure includes: a first field for storing data specifying a number of leading zeroes in a second portion of the received hashed parameter; a second field for storing data specifying trailing bits in a second portion of the received hashed parameter; and a third field for storing data specifying an aggregation amount that indicates a number of occurrences when (i) an existing data value in the first field matches the number of leading zeroes and (ii) an existing data value in the second field matches the trailing bits.

In some implementations, determining, based on the binary representation of the hashed parameter, that the hashed parameter for the object contributes to an aggregation amount, comprises: determining a number of leading zeros from the second portion of the binary representation of the hashed parameter; determining trailing bits from the second portion of the binary representation of the hashed parameter; and determining, based on the number of leading zeros and the trailing bits, that the hashed parameter impacts an existing data value stored in the third field of the data structure of the register.

In some implementations, determining, based on the number of leading zeros and the maximum number of trailing bits, that the hashed parameter impacts an existing data value stored in the third field of the data structure of the register, comprises: determining that the existing data value stored in the first field of the data structure of the register is the same as the number of leading zeros; and determining that the existing data value stored in the second field of the data structure of the register is the same as the maximum number of trailing bits.

In some implementations, updating the aggregation amount stored in the register, comprises incrementing the existing data value stored in the third field of the data structure of the register by one.

In some implementations, generating, based on aggregate amounts stored in the set of registers, a reporting output that indicates a set of data items, wherein each data item identifies an estimated number of objects in the dataset that performed activities in the digital environment at a particular aggregation amount, comprises: identifying a set of unique aggregate amounts based on aggregation amounts stored in the set of registers; for each particular aggregation amount in the set of aggregation amounts, determining an estimated number of objects of the dataset that performed activities at the particular aggregation amount, the determining includes: determining a number of registers storing an aggregation amount that matches the particular aggregation amount; adjusting the number of registers storing the aggregation amount that matches the particular aggregation amount based on a hash collision correction factor; determining an average number of object stored in each register of the set of registers; and scaling the adjusted number of registers by the average number of objects.

Particular embodiments of the subject matter described in this specification can be implemented to enhance probabilistic data structures, such as HyperLogLog (HLL), by storing activity data (as further described below) about objects in a space-efficient manner that in turn enables efficiently determining a distribution of the objects in the dataset based on their activity data. Conventional methods require substantially more computing and storage resources than those required by techniques and/or systems described in this specification, which is especially the case when performing these operations on large datasets. In contrast, the techniques and/or systems in this specification require substantially less storage and can perform more time and resource efficient processing of large datasets to determine a frequency distribution of the objects in the dataset based on the objects' activity data.

This specification describes techniques for using a probabilistic cardinality estimator, such as a HyperLogLog data structure, for providing a distribution of objects in a dataset across different aggregate values (e.g., frequencies) based on the activity data for the objects. The techniques described in this specification enhance conventional HyperLogLog (HLL) data structures in a manner that enables computing such aggregate (e.g., frequency) distributions, which is not possible using the conventional HLL data structures. It will be appreciated that other types of probabilistic data structures may also be used to implement the techniques described in this specification.

An object is an entity, resource, or component, such as users, spam events, system components, digital assets, etc. Each object in the dataset is associated with or performs certain activities in a digital environment and the activity data in the dataset represents the activities of the objects. This can include, for example, data describing device interactions with certain digital assets (e.g., portions of content), such as which users clicked on, viewed, or otherwise interacted with a content for a particular digital campaign. As another example, the activity data can include log data about hardware/component events (e.g., failures, resets, outages, network calls, memory access, or other events) in a network environment.

For context, the conventional HLL data structure can be used to measure or estimate the number of unique objects in a large dataset (i.e., the cardinality of the dataset). However, the conventional HLL data structures cannot determine an aggregate distribution of the objects based on the activity data of the objects. For example, while the conventional HLL data structure can be used to determine the number of users in a dataset that have interacted with a particular digital content, this data structure cannot be used to determine a distribution of the number of users who have viewed the content at particular frequencies (e.g., one time, two times, three times, etc.).

As described below and in greater detail throughout this specification, the techniques described in this specification enhance conventional HLL data structures to enable determining an aggregate (e.g., frequency) distribution of objects in a dataset based on the activity data for these objects in a digital environment. The HLL registers of the HLL data structure can be enhanced to include three fields: one field that stores the number of leading zeros for an object in a dataset, which also represents the bit position of the most significant non-zero bit (as already stored by standard HLL registers), a second field that stores the trailing bits for that object (or another stable identifier of the object, such as for example, a separate hash value for the object that is made up of p bits), and a third field that stores an aggregation counter that is based on the result of a commutative reduction function f(S_t,I) = S_[t+<NUM>], which stores information about all the objects with the same key. Examples of such aggregation counters can include, among others, (<NUM>) a frequency counter that counts the number of occurrences of the object in the dataset, (<NUM>) a counter that counts the most recent timestamp at which a particular event was recorded at, and (<NUM>) a counter that counts counting the number of times an error code was observed at each error logging levels.

An HLL data engine assigns objects in the dataset to a set of M registers. When data for an object is received, the object's unique identifier (as further described below) is hashed using a hash function to generate a hashed parameter (as further described below) that has a binary representation. The HLL data engine uses a certain number of bits (e.g., the first four bits) of the hashed parameter to assign the object to one of the M registers.

The HLL data engine determines an aggregate number of times that the object has been associated with or performed a certain activity. As described below and in greater detail throughout this specification, the HLL data engine accomplishes this by evaluating whether the remaining bits of the hashed parameter (i.e., the bits other than those that were used to identify the register) contribute to an aggregation amount, e.g., that specifies a number of occurrences of the object in the dataset.

The HLL data engine determines the number of leading zeros (which also represents the bit position of the most significant non-zero bit) for the remaining bits of the hashed parameter. If the number of leading zeros is the same as the value stored in the first field of the register, the HLL data engine determines a set of trailing bits for the previously determined most significant bit (or another appropriate stable identifier, as described above). If the determined trailing bits are the same as the value stored in the trailing p bits field of the register, the HLL data engine determines that the current object is the same as the object for which data is already stored in the register. As a result, the HLL data engine updates the aggregation counter field of the register, e.g., by incrementing the value stored in that field by one or by performing another appropriate commutative reduction operation.

The HLL data engine can determine the number of objects in the dataset that occurred at and/or above a certain aggregate value (e.g., frequency). The HLL data engine computes this value by scaling the number of registers (e.g., adjusted to account for any hash collisions) for which the aggregation counter was set to a certain aggregate value by the average number of objects per register.

Further to the descriptions throughout this document, a user may be provided with controls allowing the user to make an election as to both if and when systems, programs, or features described herein may enable collection of information (e.g., information about a user's social network, social actions, or activities, profession, a user's preferences, or a user's current location), and if the user is sent content or communications from a server. In addition, certain data may be treated in one or more ways before it is stored or used, so that personally identifiable information is removed. For example, a user's identity may be treated so that no personally identifiable information can be determined for the user, or a user's geographic location may be generalized where location information is obtained (such as to a city, ZIP code, or state level), so that a particular location of a user cannot be determined. Thus, the user may have control over what information is collected about the user, how that information is used, and what information is provided to the user.

<FIG> is a block diagram of an example computing system <NUM> for computing information for a dataset. System <NUM> generally includes a computing server <NUM>, a HLL data engine <NUM>, a data storage device <NUM>, and a data ingest engine <NUM>. As described in more detail below, the system <NUM> includes special-purpose hardware circuitry configured to execute specific computational rules that measure or estimate the aggregate distribution of the objects in a dataset based on the activity data for the objects. These techniques can be applied to various applications. For example, the techniques described in this specification can be used in digital campaign reach assessment, which includes generating data describing a distribution of users that have interacted with a particular campaign at different frequencies, e.g., how many unique users interacted (e.g., viewed, clicked on, etc.) with a digital content once, twice, thrice, etc. As another example, the techniques described in this specification can be used to analyze hardware/component failures in a large scale network environment, which includes generating statistics about how frequently certain components or computing devices fail in the network environment. It will be understood that the techniques described in this specification may be used in other applications as well.

As shown in <FIG>, the system <NUM> includes a computing server <NUM>, which is configured to use a HyperLogLog (HLL) data engine <NUM> to determine an aggregate distribution of objects in a dataset based on their activity levels. As used in this specification, the term engine refers to a data processing apparatus that performs a set of tasks.

The HLL data engine <NUM> is included within computing server <NUM> as a subsystem of hardware circuits (e.g., special-purpose circuitry) that includes one or more processor microchips. In general, computing server <NUM> can include processors (e.g., central or graphics processing units), memory, and data storage devices <NUM> that collectively form computer systems of computing server <NUM>. Processors of these computer systems process instructions for execution by server <NUM>, including instructions stored in the memory or on the dataset storage device <NUM> to display graphical information for output at an example display monitor of system <NUM>.

In some implementations, execution of the stored instructions causes one or more of the actions described in this specification to be performed by the computing server <NUM> or the HLL data engine <NUM>. In some implementations, multiple processors may be used, as appropriate, along with multiple memories and types of memory. For example, computing server <NUM> may be connected with multiple other computing devices, with each device (e.g., a server bank, groups of servers, modules, or a multi-processor system) performing portions of the actions, operations, or logical flows described in this specification.

System <NUM> can receive, via data ingest engine <NUM>, a dataset including activity data for a plurality of objects in a digital environment. The received dataset is provided to the HLL data engine <NUM> of the computing server <NUM>.

As further described below with reference to <FIG>, the HLL data engine <NUM> uses the logic engine <NUM>, including the hashing logic <NUM>, the leading zero logic <NUM>, and the register ID logic <NUM>, to store the data of the dataset in a set of M registers <NUM> in memory <NUM>.

Data ingest engine <NUM> also receives queries, which request data about the number of objects in the dataset that are associated with or otherwise performed activities in the digital environment at particular frequencies. For example, a query <NUM> can request data about the number of unique users in the dataset that viewed, accessed, or otherwise interacted with content a certain number of times (e.g., one time, two times, three times, etc.). The data ingest engine <NUM> sends the query <NUM> to the computing server <NUM>, which in turn uses the HLL data engine <NUM> (and in particular, the reporting logic <NUM>) to determine the number of distinct users in a dataset and their distribution across different frequencies based on their activity data. The HLL data engine <NUM> then, alone or in combination with a front end engine of the computing server <NUM>, provides the determined distribution data as reporting output <NUM>. In the above example, the reporting output <NUM> can be statistics in the form of text or a visual representation (e.g., a histogram, a pie chart, etc.) showing the number of users who are associated with or otherwise performed certain activities at different frequencies, e.g., one time, two times, etc. Alternatively or in addition, the reporting output <NUM> may be in the form of a data structure that can be processed by computing server <NUM> or by another computing device.

The components of the HLL data engine <NUM> (as shown in <FIG>) that are used in generating such statistics and the respective operations of these components are described further with reference to <FIG> below.

<FIG> is a flowchart of an example process <NUM> for computing aggregate distributions based on activity data for objects in a dataset. Process <NUM> can be implemented or executed using computing resources of system <NUM>, and in particular the HLL data engine <NUM>, described above. Operations of the process <NUM> are described below for illustration purposes only. Operations of the process <NUM> can be performed by any appropriate device or system, e.g., any appropriate data processing apparatus. Operations of the process <NUM> can also be implemented as programmed instructions stored on a non-transitory computer readable medium (such as the memory and/or data storage device <NUM>, described with reference to <FIG>) and executed by at least one processor of the computing server <NUM>.

The data ingest engine <NUM> obtains activity data for a plurality of objects in a dataset (at <NUM>). In some implementations, the data ingest engine <NUM> receives data logs specifying the activity data in a digital environment for objects in a dataset (wherein each object can occur one or more times in the dataset). The data logs can include separate fields (or delimiters that can be used to delineate different data items) corresponding to an object identifier for the object and the corresponding activity data for the object. As used in this specification, the object identifier is a value (e.g., a number, alphanumeric string, data structure) that uniquely identifies a particular object in the dataset. In some implementations, the object identifier is a byte (e.g., eight bits), while in other implementations the object identifier is a data word formed by, e.g., <NUM> bits, <NUM> bits, <NUM> bits, or <NUM> bits. In some cases, a variable number of bits can be used to form the object identifier, such as more than <NUM> bits or fewer than <NUM> bits.

The data ingest engine <NUM> sends the received dataset to the HLL data engine <NUM> of the computing server <NUM>. For each data item in the dataset, the process <NUM> then performs the operations <NUM>, <NUM>, <NUM>, and <NUM>, which are further described below. As a result of performing these operations, the process <NUM> accumulates an aggregate distribution of objects in the data set based on the activity data associated with or performed by these objects.

The HLL data engine <NUM> generates a hashed parameter <NUM> for the object using the hashing logic <NUM> (at <NUM>). In some implementations, the hashing logic <NUM> applies one or more hash functions (which may include any conventional hash function/s) to the object identifier for the object to generate the hashed parameter (which may also be referred to as a hash, hash code, or hash value). The hashed parameter has a binary representation whose length is dependent upon the hash function itself or the parameters of the hash function. The hash of object identifier for the object is indicated as the hashed parameter <NUM>, as shown in <FIG>.

The HLL data engine <NUM> identifies a register from among a set of registers that can be used to store data about the object (at <NUM>). In some implementations, data for a dataset can be stored in a set of M registers <NUM>. Using a first portion (e.g., first four bits) of the object's hashed parameter <NUM>, the register ID logic <NUM> identifies one of the M registers that can be used to store data about the object. For example, for the hashed parameter <NUM> (<NUM><NUM><NUM>), the register ID logic <NUM> can uses the first four bits (<NUM>) to identify one of the M registers. It will be appreciated that the number of registers <NUM> is less than the number of data items in the dataset.

The HLL data engine <NUM> determines whether the hashed parameter contributes to a frequency amount (at <NUM>). In some implementations, the hashing logic <NUM> identifies a second portion of the hashed parameter <NUM>, which includes the bits of the hashed parameter without the first set of bits that are used to identify the appropriate register (as described above at operation <NUM>). For the hashed parameter <NUM> (<NUM><NUM><NUM>), the bits (<NUM><NUM>) do not include the first four bits that are used by the register ID logic <NUM> to identify the appropriate register (as described in the preceding paragraph).

The leading zero logic <NUM> determines the number of leading zeros (which also represents the bit position of the most significant non-zero bit) in the second portion or set of bits. In some implementations, the leading zero logic <NUM> determines the number of leading zeros by counting the number of zeros, from left to right, in the second set of bits until the bit position of the first "<NUM>" in the second set of bits is identified. For example, the number of leading zeros for the second set of bits (<NUM><NUM>) of the hashed parameter <NUM> is one because, when counting from left to right, one zero is identified before the first "<NUM>" is encountered.

The HLL data engine <NUM> determines the number of trailing bits for the most significant bit in the second set of bits, as identified in the previous paragraph. In some implementations, the HLL data engine <NUM> determines the trailing bits by identifying all the bits in the second set of bits after the most significant bit, which is the location where the first "<NUM>" is identified when counting from left to right (as described in the preceding paragraph). For example, the trailing bits in the second set of bits (<NUM><NUM>) is "<NUM>" because these are the bits that follow the first "<NUM>" that was identified when counting the leading zeros for the second set of bits.

As shown in <FIG>, each register in the set of M registers <NUM> includes a data structure <NUM> that has three fields: a field for the most significant bit <NUM>, a field for the trailing p bits <NUM>, and a field for the aggregation counter <NUM>. In some implementations, instead of storing the trailing p bits, field <NUM> stores any number of trailing bits for the most significant bit in the second set of bits or alternatively, a stable identifier for the object, such as a separate hash value made up of p bits.

In total, the total amount of information stored in each register may only be two bytes (or <NUM> bits). In contrast, the standard HLL algorithm, which only stores the number of leading zeros in each register, generally required six bits of data. In other words, relative to the standard HLL algorithm, the HLL registers described in this specification can store additional data about objects in the dataset with only a marginal increase in storage requirement per register (as compared with storing the entirety of the activity data for objects in the dataset, which would require much more than two bytes of storage space).

In some implementations, the aggregation counter field <NUM> stores the frequency amount, which specifies a number of occurrences of the object in the dataset. As further described below, the object's hashed parameter contributes to the aggregation amount based on a comparison of the number of leading zeros and the trailing bits of the hashed parameter (as determined by the HLL data engine <NUM>) with the values stored in the most significant bit field <NUM> and the trailing p bits field <NUM> of the data structure <NUM> in the register (identified in operation <NUM>), respectively. In some implementations, instead of storing a frequency count for each object, the aggregation counter field <NUM> can aggregate information about objects with the same key (e.g., counting the most recent timestamp that a particular event was recorded at, counting the number of times an error code was observed at each error logging levels, etc.).

When the number of leading zeros determined by the leading zero logic <NUM> is less than the value stored in field <NUM>, the leading zero logic <NUM> does not update the data structure <NUM>. In other words, the existing values in fields <NUM>, <NUM>, and <NUM> are retained. Because this operation does not result in updating the aggregation counter field <NUM>, the object's hashed parameter does not contribute to the aggregation (e.g., frequency) amount.

When the number of leading zeros determined by the leading zero logic <NUM> exceeds the value stored in field <NUM>, the leading zero logic <NUM> updates field <NUM> with the value of the most significant bit determined by the leading zero logic <NUM>. In such instances, the HLL data engine <NUM> also (<NUM>) updates the value stored in field <NUM> with the trailing bits value calculated by the HLL data engine <NUM> and (<NUM>) resets the value stored in field <NUM> to zero.

When the number of leading zeros determined by the leading zero logic <NUM> is the same as the value stored in field <NUM>, the leading zero logic <NUM> does not update the value stored in the field <NUM>. In such instances, the HLL data engine <NUM> also determines whether to update the values stored in the fields <NUM> and <NUM>. As further described below, it does so by comparing the trailing bits determined by the HLL data engine <NUM> with the value stored in the trailing p bits field <NUM> of the data structure <NUM>.

If the value of the trailing bits determined by the HLL data engine <NUM> is larger than the value stored in the trailing p bits field <NUM> of the data structure <NUM>, the HLL data engine <NUM> (<NUM>) updates the field <NUM> with the value of the trailing bits determined by the HLL data engine <NUM> and (<NUM>) resets the value of the aggregation counter field <NUM> to zero.

If the value of the trailing bits determined by the HLL data engine <NUM> is less than the value stored in the trailing p bits field <NUM> of the data structure <NUM>, the HLL data engine engine <NUM> retains (i.e., does not update) the values stored in fields <NUM>, <NUM>, and <NUM>.

If, however, the value of the trailing bits determined by the HLL data engine <NUM> is the same as the value stored in the trailing p bits field <NUM> of the data structure <NUM>, the HLL data engine <NUM> determines that the current object is the same as the object for which data is already stored in the data structure <NUM>. In such instances, the HLL data engine <NUM> (<NUM>) does not update the value already stored in the trailing p bits field <NUM> and (<NUM>) updates the value stored in the aggregation counter field <NUM> based on the commutative reduction function involving the current value of the field and the object (at <NUM>). In implementations where the aggregation counter field <NUM> is a frequency counter, the HLL data engine updates the value in this field by incrementing the value stored in this field <NUM> by one (e.g., if the value stored in the aggregation counter field <NUM> is <NUM>, the HLL data engine <NUM> increments that value by one, which results in a value of <NUM>). It will be appreciated that when an aggregation distribution other than frequency is to be determined, the HLL data engine <NUM> uses the commutative reduction function to appropriate scale (e.g., multiplying, dividing, incrementing by more than one, etc.) the value in the field <NUM>.

Because the above-described operation results in updating the aggregation counter field <NUM>, the object's hashed parameter contributes to the aggregation amount.

As described above, in some implementations, the HLL data engine <NUM> performs operations <NUM>, <NUM>, and <NUM> based on the single hash representation generated for the object at operation <NUM>. In other implementations, the HLL data engine <NUM> can perform operations <NUM>, <NUM>, and <NUM> using separate hash representations. In other words, the hashing logic <NUM> can use the object identifier to generate separate hash representations: one hash representation can be used to identify the appropriate register in the set of M registers <NUM>, a second hash representation from which the number of leading zeros are determined, and a third hash representation from which the trailing bits are determined. The above described operations <NUM> to <NUM> can then be performed using these separate hash representations.

The data ingest engine <NUM> receives a query <NUM> requesting an aggregation distribution of the number of objects in the dataset that performed activities in the digital environment at different frequencies (at <NUM>). For example, the query <NUM> can request a frequency distribution of the number of users in a dataset that interacted with certain digital content at different frequencies (one time, two times, three times, etc.). In some implementations, the data ingest engine <NUM> sends the query <NUM> to the computing server <NUM>, which in turn routes the query <NUM> to the reporting logic <NUM> of the logic engine <NUM>.

In response to the query <NUM>, the reporting logic <NUM> generates a reporting output that represents an aggregate distribution of the objects in the dataset based on the associated activities or activities performed by these objects in the digital environment (at <NUM>). The reporting logic <NUM> estimate the aggregate distribution based on the aggregate value stored in the registers <NUM>. The reporting logic <NUM> generates this reporting output by performing the following operations. In some implementations, the reporting logic <NUM> determines the different possible aggregate values by identifying a set of values including the unique aggregate values stored in aggregation counter field <NUM> in the set of registers <NUM>. In some implementations, the query <NUM> may identify the aggregate values, in which case, the reporting logic <NUM> can skip the operation of identifying the different possible aggregate values stored in field <NUM> of the registers. In some implementations, the reporting logic <NUM> may access a set of aggregate values specified by an administrator of the system (and stored in the data storage device <NUM>), in which case, the reporting logic <NUM> can skip the operation of identifying the different possible aggregate values stored in the registers.

In some implementations, for each identified aggregate value, the reporting logic <NUM> determines a number of registers that have the same value stored in the aggregation counter field <NUM> as the identified aggregate value. In such implementations, the reporting logic <NUM> counts all registers for which the value in the aggregation counter field <NUM> is the same as the identified aggregate value. In other implementations, the reporting logic <NUM> counts all registers for which the value in the aggregation counter field <NUM> is the same as or greater than the identified aggregate value.

In some instances, hash collisions may arise when storing and updating values in the data structure <NUM> of the registers <NUM>. For example, two object identifiers for two different objects in the dataset, when hashed by the hashing logic <NUM>, may update the same register and may have the same number of leading zeros and the same trailing bits. In the case of a frequency counter, the value of this field should only be incremented by one in this scenario; however, because of the hash collision, value of this field <NUM> is instead incorrectly incremented by two. In other words, even though both objects, e.g., may have interacted with the same content only once, the aggregation counter field <NUM> may incorrectly reflect that a single object interacted with the same content twice. In some implementations where another aggregate (i.e., other than frequency) is being measured, the reporting logic <NUM> counts all registers that satisfy some criteria, which can be specified in the query (e.g. having more errors at one reporting level than another, or having a value between two bounds), that provides a function to map the value in field <NUM> to a boolean (e.g., include in the count or not).

To account for such error arising from hash collisions, the reporting logic <NUM> obtains the count of registers for which the value in the aggregation counter field <NUM> is the same as or greater than the identified aggregate value and then adjusts (e.g., reduces) this count by a correction factor. The correction factor (also referred to as a hash collision correction factor), F, can be represented by F(C, M, n)), and estimates the number of hash collisions expected at the identified aggregate value (n) for a number of distinct objects (C) in the dataset that have performed or are associated with certain activity, which are stored in the set of M registers <NUM>. The number of distinct elements that have performed or are associated with certain activity (i.e., the cardinality of the dataset (C)) is determined using the standard HLL algorithm. In some implementations, the correction factor is based on empirically determined lookup table of reduction values indexed by C, M, and f.

To obtain the total number of objects at a particular aggregate value, the reporting logic <NUM> scales (e.g., multiplies) the adjusted number of registers (as determined in the previous paragraph) at the particular aggregate value by the average number of objects per register. The average number of objects per register is determined by dividing the cardinality of the dataset C (as determined using the standard HLL algorithm) by M, which is the number of registers <NUM>. The reporting logic <NUM> repeats the above operations for each identified frequency. As such, the total number of object at a particular aggregate value can be represented using the following equation: <MAT> where (<NUM>) Rn is the number of objects at a particular aggregate value n, (<NUM>) Bn is the number of buckets with the aggregation counter field set to n, (<NUM>) C is the cardinality of the dataset, (<NUM>) M is the total number of registers <NUM>, and (<NUM>) F(C,M,n) is the correction factor.

In some implementations, reporting logic <NUM> sends the identified frequencies and the corresponding number of determined objects to a front end engine of the computing server <NUM>, which uses these values to generate a report, e.g., reporting output <NUM>, that is provided to the entity from which the query <NUM> was received. The front end engine can use the values provided by the reporting logic <NUM> to generate statistics that include a set of data items, in which each data item identifies an estimated number of objects in the dataset that is associated with or performed activities in the digital environment at a particular frequency. These statistics can be in the form of text and/or visuals (e.g., a histogram, a pie chart, etc.) on the reporting output <NUM>, and show the distribution of the number of objects at different frequencies based on the activity data of the objects.

<FIG> is a block diagram of computing devices <NUM>, <NUM> that may be used to implement the systems and methods described in this document, either as a client or as a server or plurality of servers. Computing device <NUM> is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. Computing device <NUM> is intended to represent various forms of mobile devices, such as personal digital assistants, cellular telephones, smartphones, smartwatches, head-worn devices, and other similar computing devices. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations described and/or claimed in this document.

Each of the components <NUM><NUM>, <NUM>, <NUM><NUM>, <NUM>, <NUM>, and <NUM>, are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate.

In various different implementations, the storage device <NUM> may be a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations.

The high-speed controller <NUM> manages bandwidth-intensive operations for the computing device <NUM>, while the low speed controller <NUM> manages lower bandwidth-intensive operations.

The processor <NUM> can process instructions for execution within the computing device <NUM>, including instructions stored in the memory <NUM>. The processor may also include separate analog and digital processors.

The display <NUM> may be, for example, a TFT LCD display or an OLED display, or other appropriate display technology. External interface <NUM> may provide, for example, for wired communication (e.g., via a docking procedure) or for wireless communication (e.g., via Bluetooth or other such technologies).

Expansion memory <NUM> may also be provided and connected to device <NUM> through expansion interface <NUM>, which may include, for example, a SIMM card interface. Thus, for example, expansion memory <NUM> may be provided as a security module for device <NUM>, and may be programmed with instructions that permit secure use of device <NUM>.

The memory may include for example, flash memory and/or MRAM memory, as discussed below. The information carrier is a computer- or machine-readable medium, such as the memory <NUM>, expansion memory <NUM>, or memory on processor <NUM>.

In addition, GPS receiver module <NUM> may provide additional wireless data to device <NUM>, which may be used as appropriate by applications running on device <NUM>.

Various implementations of the systems and techniques described here can be realized in digital electronic circuitry, integrated circuitry, specially designed ASICs, computer hardware, firmware, software, and/or combinations thereof.

These computer programs, also known as programs, software, software applications or code, include machine instructions for a programmable processor, and can be implemented in a high-level procedural and/or object-oriented programming language, and/or in assembly/machine language. As used herein, the terms "machine-readable medium" "computer-readable medium" refers to any computer program product, apparatus and/or device, e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs) used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal.

To provide for interaction with a user, the systems and techniques described here can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer.

The systems and techniques described here can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component such as an application server, or that includes a front end component such as a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the systems and techniques described here, or any combination of such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication such as, a communication network.

As used in this specification, the terms "module," "engine," and "component" are is intended to include, but is not limited to, one or more computers configured to execute one or more software programs that include program code that causes a processing unit(s)/device(s) of the computer to execute one or more functions. The term "computer" is intended to include any data processing or computing devices/systems, such as a desktop computer, a laptop computer, a mainframe computer, a personal digital assistant, a server, a handheld device, a smartphone, a tablet computer, an electronic reader, or any other electronic device able to process data.

A number of embodiments have been described. Nevertheless, it will be understood that various modifications may be made without departing from the scope of the invention. Accordingly, other embodiments are within the scope of the following claims.

Claim 1:
A computer implemented method including:
obtaining (<NUM>) activity data for a plurality of objects in a dataset, wherein each object in the dataset represents an entity, resource or component that performs activities in a digital environment and the activity data represents the activities, and wherein the dataset comprises a plurality of data items, each data item including a unique identifier for an object;
for each data item in the dataset:
generating (<NUM>) a hashed parameter (<NUM>) for the object by applying one or more hash functions to the unique identifier for the object, wherein the hashed parameter (<NUM>) has a binary representation;
identifying (<NUM>) a register from among a set of registers (<NUM>) using a first portion of the binary representation of the hashed parameter (<NUM>), wherein each register in the set of registers (<NUM>) comprises a data structure (<NUM>) that stores data about the hashed parameter (<NUM>), wherein the data structure (<NUM>) includes: a first field (<NUM>) for storing data specifying a number of leading zeroes in a second portion of the received hashed parameter, a second field (<NUM>) for storing data specifying trailing bits in a second portion of the received hashed parameter; and a third field (<NUM>) for storing data specifying an aggregation amount;
determining (<NUM>), based on a comparison of a second portion of the binary representation of the hashed parameter (<NUM>) with data in the first field and the second field of the data structure of the register, that the hashed parameter (<NUM>) for the object contributes to an aggregation amount that specifies a number of occurrences of the object in the dataset; and
in response to determining that the hashed parameter (<NUM>) for the object contributes to the aggregation amount, updating (<NUM>) the aggregation amount stored in the register; and
generating (<NUM>), based on aggregate amounts stored in the set of registers (<NUM>), a reporting output (<NUM>) that indicates a set of data items, wherein each data item in the set of data items identifies an estimated number of objects in the dataset that performed activities in the digital environment at a particular aggregation amount.