Method and system for configuring presence bitmaps identifying records with unique keys in a large data set
View Patent ↗A system, method, and apparatus are provided for supporting and/or executing count-distinct queries. A large set of data (e.g., tens or hundreds of millions of event records) is condensed daily to generate presence bitmaps to reflect the distinctiveness of a selected data dimension S (e.g., user ID) for one or more key dimensions g1, g2, . . . (e.g., advertisement ID, campaign ID, advertiser ID). The condensation process eliminates duplication and yields a single value (e.g., 1 or 0) for each tuple [S, g1, . . . ] to represent the distinctiveness of each value in the S dimension to each combination of values in the grouping dimensions. On a monthly basis, the daily values are condensed to yield a single value for the month, and a similar process is applied on any other desired time granularities (e.g., year). The condensed data may be generated for any combination of selected dimension(s) and grouping dimension(s).
1. A method of distinctively condensing multi-dimensional data in one or more selected dimensions, the method comprising:
after termination of a first repeating period of time:
for each of multiple unique keys, configuring, with a computer, a first presence bitmap associated with the first time period to indicate whether at least one record in the multi-dimensional data created during the first time period comprises the unique key;
wherein each unique key comprises values in the one or more selected dimensions and values in at least one other dimension.
2. The method of claim 1 , wherein:
the first presence bitmap corresponds to a month and comprises:
for each day of the month, a corresponding daily indicator configured to indicate whether at least one record created in the multi-dimensional data during the day comprises the unique key; and
a separate first presence bitmap is generated for each month for which the original multi-dimensional data is distinctively condensed.
3. The method of claim 2 , wherein:
the first repeating time period is a day; and
configuring the first presence bitmap comprises:
setting the daily indicator for the day corresponding to the first time period to a first value if at least one record created in the multi-dimensional data during the day comprises the unique key; and
setting the daily indicator to a second value if no record created in the multi-dimensional data during the day comprises the unique key.
4. The method of claim 1 , further comprising:
after termination of a second repeating time period that encompasses the first time period:
for each of the multiple unique keys, configuring a second presence bitmap associated with the second time period to indicate whether at least one record in the multi-dimensional data created during the second time period comprises the unique key;
wherein the second time period is different than the first time period.
5. The method of claim 4 , wherein:
the first presence bitmap corresponds to a month and comprises:
for each day of the month, a corresponding daily indicator configured to indicate whether at least one record created in the multi-dimensional data during the day comprises the unique key; and
the second presence bitmap is associated with a year and comprises:
for each month of the year, a corresponding monthly indicator configured to indicate whether at least one record created in the multi-dimensional data during the month comprises the unique key;
a separate first presence bitmap is generated for each month for which the multi-dimensional data is distinctively condensed; and
a separate second presence bitmap is generated for each year for which the original multi-dimensional data is distinctively condensed.
6. The method of claim 5 , wherein:
the first repeating time period is a day;
the second repeating time period is a month;
configuring the first presence bitmap comprises:
setting the daily indicator for the day corresponding to the first time period to a first value if at least one record created in the multi-dimensional data during the day comprises the unique key; and
setting the daily indicator to a second value if no record created in the multi-dimensional data during the day comprises the unique key; and
configuring the second presence bitmap comprises:
setting the monthly indicator for the month corresponding to the second time period to the first value if at least one record created in the multi-dimensional data during the month comprises the unique key; and
setting the monthly indicator to the second value if no record created in the multi-dimensional data during the month comprises the unique key.
7. The method of claim 1 , wherein:
the first presence bitmap corresponds to a year and comprises:
for each day of the year, a corresponding daily indicator configured to indicate whether at least one record created in the multi-dimensional data during the day comprises the unique key; and
a separate first presence bitmap is generated for each year for which the original multi-dimensional data is distinctively condensed.
8. The method of claim 7 , wherein:
the first repeating time period is a day; and
configuring the first presence bitmap comprises:
setting the daily indicator for the day corresponding to the first time period to a first value if at least one record created in the multi-dimensional data during the day comprises the unique key; and
setting the daily indicator to a second value if no record created in the multi-dimensional data during the day comprises the unique key.
9. The method of claim 1 , wherein:
the first presence bitmap corresponds to a year and comprises:
for each month of the year, a corresponding monthly indicator configured to indicate whether at least one record created in the multi-dimensional data during the month comprises the unique key; and
a separate first presence bitmap is generated for each year for which the original multi-dimensional data is distinctively condensed.
10. The method of claim 9 , wherein:
the first repeating time period is a month; and
configuring the first presence bitmap comprises:
setting the monthly indicator for the month corresponding to the first time period to a first value if at least one record created in the multi-dimensional data during the month comprises the unique key; and
setting the monthly indicator to a second value if no record created in the multi-dimensional data during the month comprises the unique key.
11. The method of claim 1 , wherein:
the first presence bitmap corresponds to a year and comprises:
for each week of the year, a corresponding weekly indicator configured to indicate whether at least one record created in the multi-dimensional data during the week comprises the unique key; and
a separate first presence bitmap is generated for each year for which the original multi-dimensional data is distinctively condensed.
12. The method of claim 11 , wherein:
the first repeating time period is a week; and
configuring the first presence bitmap comprises:
setting the weekly indicator for the week corresponding to the first time period to a first value if at least one record created in the multi-dimensional data during the week comprises the unique key; and
setting the weekly indicator to a second value if no record created in the multi-dimensional data during the week comprises the unique key.
13. A system, comprising:
a data repository storing multi-dimensional data records, each multi-dimensional data record comprising:
a selected dimension; and
one or more dimensions other than the selected dimension;
wherein each unique combination of a value for the selected dimension and values for the one or more other dimensions defines a unique key; and
a condenser module comprising a non-transitory computer readable medium storing instructions for:
after termination of a first repeating period of time:
for each unique key, configuring a first presence bitmap associated with the first time period to indicate whether at least one multi-dimensional data record created during the first time period comprises the unique key.
14. The system of claim 13 , wherein the non-transitory computer readable medium of the condenser module further stores instructions for:
after termination of a second repeating time period:
for each unique key, configuring a second presence bitmap associated with the second time period to indicate whether at least one multi-dimensional data record created during the second time period comprises the unique key;
wherein the second time period is different than the first time period.
15. The system of claim 14 , wherein:
the first presence bitmap corresponds to a month and comprises:
for each day of the month, a corresponding daily indicator configured to indicate whether at least one multi-dimensional data record created during the day comprises the unique key; and
the second presence bitmap is associated with a year and comprises:
for each month of the year, a corresponding monthly indicator configured to indicate whether at least one multi-dimensional data record created during the month comprises the unique key.
16. The system of claim 15 , wherein:
the first repeating time period is a day;
the second repeating time period is a month;
configuring the first presence bitmap comprises:
setting the daily indicator for the day corresponding to the first time period to a first value if at least one multi-dimensional data record created during the day comprises the unique key; and
setting the daily indicator to a second value if no multi-dimensional data record created during the day comprises the unique key; and
configuring the second presence bitmap comprises:
setting the monthly indicator for the month corresponding to the second time period to the first value if at least one multi-dimensional data record created during the month comprises the unique key; and
setting the monthly indicator to the second value if no multi-dimensional data record created during the month comprises the unique key.
17. The system of claim 13 , wherein:
the first presence bitmap corresponds to a year and comprises:
for each first time period of the year, a corresponding indicator configured to indicate whether at least one multi-dimensional data record created during the first time period comprises the unique key.
18. The system of claim 13 , further comprising:
a content module comprising a non-transitory computer readable medium storing instructions for serving electronic content items;
wherein the multi-dimensional data records are records of content items served by the content module.
19. The system of claim 13 , further comprising:
a query module comprising a non-transitory computer readable medium storing instructions for constructing count-distinctive queries for execution against the multi-dimensional data records.
20. The system of claim 19 , wherein the non-transitory computer readable medium of the query module further stores instructions for converting a COUNT DISTINCT query into a COUNT query.
21. Apparatus for distinctively condensing multi-dimensional data in a selected dimension, the apparatus comprising:
one or more processors;
the multi-dimensional data, wherein each multi-dimensional data record comprises:
a selected dimension; and
one or more dimensions other than the selected dimension; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to, for each unique combination of a value in the selected dimension and values in the one or more other dimensions:
configure a first presence bitmap associated with a first time period to indicate whether at least one multi-dimensional data record created during the first time period comprises the unique key.
22. The apparatus of claim 21 , wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to, for each unique combination of a value in the selected dimension and values in the one or more key dimensions:
configure a second presence bitmap associated with a second time period to indicate whether at least one multi-dimensional data record created during the second time period comprises the unique key;
wherein the second time period is different than and encompasses the first time period.