Method and system for estimating a number of users of a website based on lossy compressed data

1. A method for estimating a number of accessing entities which are accessing a website, the method comprising:

dividing a period of time for which the number of accessing entities is to be estimated into a plurality of time intervals;

providing a plurality of arrays of bits, the number of the arrays of bits corresponding to the number of time intervals and each array of bits having a number of S bits;

associating each array of bits with one of the plurality of time intervals, respectively;

repeatedly determining that the website is accessed by an accessing entity during each of the plurality of time intervals;

determining, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, identification data comprising a characterizing number x dependent on the accessing entity, each accessing entity being characterized by a characterizing number x taken from the interval 0 to M−1;

calculating, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, a hash bucket H(x) for the accessing entity by mapping the characterizing number x dependent on the accessing entity onto a value between 0 and S−1 according to a non-linear mapping function H(x);

activating, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, the bit corresponding to the determined hash bucket H(x) for the accessing entity in the array of bits corresponding to the current time interval;

determining, after the end of the period of time, a combined array of bits by combining the plurality of arrays of bits associated with the plurality of time intervals by using a logical OR-operation between the bits of the arrays of bits having the same significance; and

estimating the number of accessing entities of the website which accessed the website during the period of time based on the activated bits of the combined array of bits.

2. The method of claim 1 wherein estimating the number of accessing entities of the website based on the activated bits of the combined array of bits uses a maximum likelihood analysis which is based on a pattern of the activated bits of the combined array of bits.

3. The method of claim 1 wherein estimating the number of accessing entities of the website based on the activated bits of the combined array of bits comprises:

providing an estimation function relating a number of activated bits of the combined array of bits with a number of accessing entities;

determining a number of activated bits by counting the number of activated bits of the combined array of bits; and

estimating the number of accessing entities of the website based on the number of activated bits of the array of bits according to a relation given by the estimation function.

4. A system for estimating a number of accessing entities which are accessing a website, the system comprising a data processing apparatus adapted to execute:

dividing a period of time for which the number of accessing entities is to be estimated into a plurality of time intervals;

providing a plurality of arrays of bits, the number of the arrays of bits corresponding to the number of time intervals and each array of bits having a number of S bits;

associating each array of bits with one of the plurality of time intervals, respectively;

repeatedly determining that the website is accessed by an accessing entity during each of the plurality of time intervals,

determining, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, identification data comprising a characterizing number x dependent on the accessing entity, each accessing entity being characterized by a characterizing number x taken from the interval 0 to M−1;

calculating, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, a hash bucket H(x) for the accessing entity by mapping the characterizing number x dependent on the accessing entity onto a value between 0 and S−1 according to a non-linear mapping function H(x);

activating, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, the bit corresponding to the determined hash bucket H(x) for the accessing entity in the array of bits corresponding to the current time interval;

determining, after the end of the period of time, a combined array of bits by combining the plurality of arrays of bits associated with the plurality of time intervals by using a logical OR-operation between the bits of the arrays of bits having the same significance; and

estimating the number of accessing entities of the website which accessed the website during the period of time based on the activated bits of the combined array of bits.

5. The system of claim 4 wherein, when estimating the number of accessing entities of the website based on the activated bits of the combined array of bits, the data processing apparatus is adapted to use a maximum likelihood analysis which is based on a pattern of the activated bits of the combined array of bits.

6. The system of claim 4 wherein, when estimating the number of accessing entities of the website based on the activated bits of the combined array of bits, the data processing apparatus is adapted to execute:

providing an estimation function relating a number of activated bits of the combined array of bits with a number of accessing entities,

determining a number of activated bits by counting the number of activated bits of the combined array of bits, and

estimating the number of accessing entities of the website based on the number of activated bits of the combined array of bits according to a relation given by the estimation function.

7. A non-transitory computer readable medium having a computer program recorded therein, the computer program comprising a set of instructions which, when executed by a data processing apparatus, cause the data processing apparatus to:

divide a period of time for which the number of accessing entities is to be estimated into a plurality of time intervals;

provide a plurality of arrays of bits, the number of the arrays of bits corresponding to the number of time intervals and each array of bits having a number of S bits;

associate each array of bits with one of the plurality of time intervals, respectively;

repeatedly determine that the website is accessed by an accessing entity during each of the plurality of time intervals,

determine, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, identification data comprising a characterizing number x dependent on the accessing entity, each accessing entity being characterized by a characterizing number x taken from the interval 0 to M−1;

calculate, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, a hash bucket H(x) for the accessing entity by mapping the characterizing number x dependent on the accessing entity onto a value between 0 and S−1 according to a non-linear mapping function H(x);

activate, in reaction to each access of the website by an accessing entity during a current time interval of the plurality of time intervals, the bit corresponding to the determined hash bucket H(x) for the accessing entity in the array of bits corresponding to the current time interval;

determine, after the end of the period of time, a combined array of bits by combining the plurality of arrays of bits associated with the plurality of time intervals by using a logical OR-operation between the bits of the arrays of bits having the same significance; and

estimate the number of accessing entities of the website which accessed the website during the period of time based on the activated bits of the combined array of bits.

8. The non-transitory computer readable medium of claim 7 wherein the instructions to estimate the number of accessing entities of the website based on the activated bits of the combined array of bits uses a maximum likelihood analysis which is based on a pattern of the activated bits of the combined array of bits.

9. The non-transitory computer readable medium of claim 7 wherein the instructions to estimate the number of accessing entities of the website based on the activated bits of the combined array of bits comprise instructions to:

provide an estimation function relating a number of activated bits of the combined array of bits with a number of accessing entities;

determine a number of activated bits by counting the number of activated bits of the combined array of bits; and

estimate the number of accessing entities of the website based on the number of activated bits of the combined array of bits according to a relation given by the estimation function.