Method and system for performing count-distinct queries in a large data set that stores presence bitmaps corresponding to different time periods
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 determining distinctiveness within multi-dimensional data condensed in a selected dimension, the method comprising:
receiving a query regarding distinctiveness of the multi-dimensional data within a specified range of time, across:
the selected dimension; and
one or more dimensions other than the selected dimension;
for each unique key comprising a value in the selected dimension and values in the one or more other dimensions, accessing, with a computer, at least one associated presence bitmap comprising separate indicators corresponding to each of multiple time periods; and
aggregating a count of unique keys for which at least one associated presence bitmap comprises an indicator having a first value and corresponding to a time period within the specified range of time.
2. The method of claim 1 , wherein each indicator within a presence bitmap is one of:
the first value indicating that at least one record comprising the associated unique key was added to the multi-dimensional data during the corresponding time period; and
a second value indicating that no record comprising the associated unique key was added to the multi-dimensional data during the corresponding time period.
3. The method of claim 1 , wherein a 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 associated unique key.
4. The method of claim 3 , wherein a second 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 associated unique key.
5. The method of claim 1 , wherein a 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 associated unique key.
6. The method of claim 1 , wherein a first presence bitmap corresponds to a year and comprises:
for each week of the year, a corresponding daily indicator configured to indicate whether at least one record created in the multi-dimensional data during the week comprises the associated unique key.
7. The method of claim 1 , further comprising, prior to said accessing:
identifying presence bitmaps comprising indicators corresponding to time periods encompassed by the range of time, including the at least one presence bitmap.
8. The method of claim 1 , wherein said aggregating comprises:
for each presence bitmap associated with a given unique key and comprising one or more indicators corresponding to time periods within the range of time, performing a bit-wise OR between the presence bitmap and a constant value.
9. The method of claim 8 , wherein:
the constant value comprises a separate bit pertaining to each indicator of the presence bitmap, each bit having:
the first value if the pertinent indicator corresponds to a time period within the range of time; and
a second value if the pertinent indicator corresponds to a time period not within the range of time.
10. The method of claim 1 , wherein:
the query is a COUNT DISTINCT query; and
accessing the at least one presence bitmap comprises executing a COUNT query on the at least one presence bitmap instead of executing the COUNT DISTINCT query on the multi-dimensional data.
11. A system, comprising:
a first data repository storing multi-dimensional data, each multi-dimensional data record comprising:
a selected dimension; and
one or more dimensions other than the selected dimension;
a second data repository storing presence bitmaps representing the multi-dimensional data as condensed in the selected dimension, wherein each presence bitmap is associated with a unique key comprising a value in the selected dimension and values in the one or more other dimensions; and
a query module comprising a non-transitory computer readable medium storing instructions for:
receiving a query regarding distinctiveness of the multi-dimensional data within a specified range of time, across the selected dimension and the one or more other dimensions;
accessing one or more presence bitmaps, each accessed presence bitmap comprising one or more indicators that each correspond to a time period within the range of time; and
aggregating a count of unique keys associated with an accessed presence bitmap that comprises at least one indicator corresponding to a time period within the range of time and has a first value;
wherein the first value indicates that at least one record created in the multi-dimensional data during the corresponding time period comprises the unique key.
12. The system of claim 11 , wherein the non-transitory computer readable medium of the query module further stores instructions for:
converting a COUNT DISTINCT query targeting the first data repository into a substitute COUNT query targeting the second data repository.
13. The system of claim 11 , wherein:
a 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 associated unique key.
14. The system of claim 13 , wherein:
a 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 associated unique key.
15. The system of claim 11 , wherein:
a first presence bitmap corresponds to a year and comprises:
for each predetermined 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 associated unique key.
16. The system of claim 15 , wherein the predetermined time period is a day.
17. The system of claim 11 , further comprising:
a condenser module comprising a non-transitory computer readable medium storing instructions for, after termination of a first repeating time period:
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.
18. Apparatus for determining distinctiveness within multi-dimensional data condensed in a selected dimension, the apparatus comprising:
one or more processors;
a data repository comprising presence bitmaps representing the condensed multi-dimensional data, wherein each presence bitmap is associated with a unique key comprising a value in the selected dimension and values in one or more other dimensions of the multi-dimensional data, and comprises:
for each of multiple repeating time periods, a corresponding indicator configured to indicate whether a record created in the multi-dimensional data during the time period comprises the unique key; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
receive a query regarding distinctiveness of the multi-dimensional data within the selected dimension and the one or more other dimensions during a range of time; and
computing a number of unique keys associated with at least one presence bitmap having at least one indicator corresponding to a given time period during the range of time and indicating that a record having the unique key was created in the multi-dimensional data during the given time period.
19. The apparatus of claim 18 , wherein:
a 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 associated unique key; and
a 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 associated unique key.
20. The apparatus of claim 18 , wherein:
a first presence bitmap corresponds to a year and comprises:
for each predetermined repeating time period of the year, a corresponding indicator configured to indicate whether at least one multi-dimensional data record created during the predetermined time period comprises the associated unique key.