Aggregation of unique user invocations in an online environment
AssigneeInternational Business Machines Corporation
InventorChristopher M. Curtin
Life of this patent
Estimating the term…
Abstract
Methods and systems for determining a unique invocation of an online feature are disclosed. A key is distributed to multiple users. Upon performing a user action, the key is sent to a Bloom filter. If the output of the Bloom filter is a negative activation, the invocation is deemed to be unique. If the output of the Bloom filter is a positive activation, the invocation is deemed to be non-unique. For a large data set, the computational overhead of processing the key with the Bloom filter is significantly less than the brute force database approach. Thus, in large systems with many millions of users and possible user actions, disclosed embodiments allow assessment of a unique action in a timely manner.
Claims20
A computer-implemented method for tracking a usage of an online feature, comprising:
- distributing a key to a plurality of users;
- creating a Bloom filter configured to receive the key for a single online feature by selecting a plurality of different hash functions based on the key;
- identifying utilization of the single online function by unique users by ANDing, for each instance in which any of the plurality of users utilizes the single online feature, results of a hash of the key by each of the plurality of different hash functions in the Bloom filter and updating, in response to an indication of a negative activation, a hash table value corresponding to a hash function that returned a logical 0 result;
- using the Bloom filter, in isolation from other Bloom filters, to probabilistically determine a subset of users included in the plurality of users that have utilized the online feature based on a negative activation of the Bloom filter in response to the key;
- determining a false positive rate for the Bloom filter;
- and
- creating a new Bloom filter that is associated with the single online feature, wherein the new Bloom filter contains an increased number of Hash functions in the false positive rate exceeding a predetermined threshold.
A system for tracking a usage of an online feature, comprising:
- a Bloom filter server, the Bloom filter server comprising:
- a processor;
- a memory coupled to the processor, wherein the memory contains instructions, that when executed by the processor, perform the steps of:
- distributing a key to a plurality of users;
- creating a Bloom filter configured to receive the key for a single online feature by selecting a plurality of different hash functions based on the key;
- identify utilization of the single online function by unique users by ANDing, for each instance in which any of the plurality of users utilizes the single online feature, results of a hash of the key by each of the plurality of different hash functions in the Bloom filter and updating, in response to an indication of a negative activation, a hash table value corresponding to a hash function that returned a logical 0 result;
- using the Bloom filter, in isolation from other Bloom filters, to probabilistically determine a subset of users included in the plurality of users that have utilized the online feature based on a negative activation of the Bloom filter in response to the key;
- determining a false positive rate for the Bloom filter;
- and
- creating a new Bloom filter that is associated with the single online feature, wherein the new Bloom filter contains an increased number of Hash functions in the false positive rate exceeding a predetermined threshold.
A computer program product for tracking a usage of an online feature, comprising a computer readable storage device having program instructions embodied therewith, the program instructions executable by a processor to cause the electronic device to:
- distribute a key to a plurality of users;
- create a Bloom filter configured to receive the key for a single online feature by selecting a plurality of different hash functions based on the key;
- identify utilization of the single online function by unique users by ANDing, for each instance in which any of the plurality of users utilizes the single online feature, results of a hash of the key by each of the plurality of different hash functions in the Bloom filter and updating, in response to an indication of a negative activation, a hash table value corresponding to a hash function that returned a logical 0 result;
- utilize the Bloom filter, in isolation from other Bloom filters, to probabilistically determine a subset of users included in the plurality of users that have utilized the online feature based on a negative activation of the Bloom filter in response to the key;
- determine a false positive rate for the Bloom filter;
- and
- create a new Bloom filter that is associated with the single online feature, wherein the new Bloom filter contains an increased number of Hash functions in the false positive rate exceeding a predetermined threshold.
Dependencies are inferred from the claim text.