METHODS AND SYSTEMS TO OPERATE ON GROUP-BY SETS WITH HIGH CARDINALITY

• US 20140330827A1
• Filed: 05/05/2014
• Published: 11/06/2014
• Est. Priority Date: 05/03/2013
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Wu, Xunlei, Schabenberger, Oliver
• Granted Patent: US 9,633,104 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

This disclosure describes methods, systems, computer-readable media, and apparatuses for efficiently calculating group-by statistics. A data set that includes multiple entries is accessed. The multiple entries are grouped into group-by subsets which are formed on two or more group-by variables and which are subsets are subsets of the data set. Cardinality data is determined for each of the group-by subsets, wherein cardinality data represents a number of entries in a group-by subset. At least one summary of data in each of the group-by subsets is generated, wherein each of the summaries includes the cardinality data determined for the group-by subset. Objects for the group-by subsets are initialized such that the objects store the summaries. The objects may then be used to generate multiple statistical summaries of the data set.

Claims

1. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the storage medium having instructions stored thereon, and the instructions being operable to cause a data-processing apparatus to perform operations including:

accessing a data set that includes multiple entries, each of the entries including data corresponding to multiple variables;

grouping the multiple entries into group-by subsets, wherein the group-by subsets are formed on two or more group-by variables, and wherein the group-by subsets are subsets of the data set;

determining cardinality data for each of the group-by subsets, wherein cardinality data represents a number of entries in a group-by subset;

generating at least one summary of data in each of the group-by subsets, wherein each of the summaries includes the cardinality data determined for the group-by subset;

initializing objects for the group-by subsets, wherein each of the objects include the cardinality data and the at least one summary, and wherein each of the objects includes values of the group-by variables used in forming the group-by subset; and

generating multiple statistical summaries of the data set using the objects.

2. The computer-program product of claim 1, wherein the multiple statistical summaries include a histogram that represents a variable distribution with respect to the group-by subsets.

3. The computer-program product of claim 1, wherein the data set is partitioned and distributed amongst multiple grid-computing devices in a grid-computing system, and wherein grouping the multiple entries into the group-by subsets includes using parallel processing involving at least two of the grid-computing devices to form at least one of the group-by subsets.

4. The computer-program product of claim 3, wherein the data set is partitioned such that the at least one of the group-by subsets is formed by identifying constituent subsets stored in a distributed manner.

5. The computer-program product of claim 4, wherein the constituent subsets are statistically summarized individually, and wherein generating at least one summary of data in each of the group-by subsets includes synthesizing statistical summaries of the constituent subsets.

6. The computer-program product of claim 3, wherein the operations further include:

using the grid-computing devices to store the objects, wherein the objects are stored in a distributed manner across the grid-computing system.

7. The computer-program product of claim 6, wherein storage locations of the objects are determined by a hash function that involves a modular operation.

8. The computer-program product of claim 7, wherein the hash function maps multiple combinations of group-by variables to integers, and wherein each of the integers represents a storage location.

9. The computer-program product of claim 1, wherein the objects are initialized in accordance with a shared organizational scheme that facilitates referencing the cardinality data and the summaries included in the objects.

10. The computer-program product of claim 1, wherein the group-by subsets include multiple disjoint subsets of the data set, multiple intersecting subsets of the data set, and multiple subsets of the data set which are formed on different combinations of group-by variables.

11. The computer-program product of claim 10, wherein the operations further include:

displaying an interface that facilitates defining a subset of the data set by referencing one or more of the group-by subsets;

receiving an input at the interface, the input defining a subset of the data set by referencing at least one of the group-by subsets; and

generating a statistical summary of the defined subset.

12. The computer-program product of claim 11, wherein the interface further facilitates defining a subset of the data set by using logical operators to indicate a union of group-by subsets or an intersection of group-by subsets.

13. A system comprising:

one or more processors configured to perform operations that include;

accessing a data set that includes multiple entries, each of the entries including data corresponding to multiple variables;

grouping the multiple entries into group-by subsets, wherein the group-by subsets are formed on two or more group-by variables, and wherein the group-by subsets are subsets of the data set;

determining cardinality data for each of the group-by subsets, wherein cardinality data represents a number of entries in a group-by subset;

generating at least one summary of data in each of the group-by subsets, wherein each of the summaries includes the cardinality data determined for the group-by subset;

initializing objects for the group-by subsets, wherein each of the objects include the cardinality data and the at least one summary, and wherein each of the objects includes values of the group-by variables used in forming the group-by subset; and

generating multiple statistical summaries of the data set using the objects.

14. The system of claim 13, wherein the multiple statistical summaries include a histogram that represents a variable distribution with respect to the group-by subsets.

15. The system of claim 13, wherein the data set is partitioned and distributed amongst multiple grid-computing devices in a grid-computing system, and wherein grouping the multiple entries into the group-by subsets includes using parallel processing involving at least two of the grid-computing devices to form at least one of the group-by subsets.

16. The system of claim 15, wherein the data set is partitioned such that the at least one of the group-by subsets is formed by identifying constituent subsets stored in a distributed manner.

17. The system of claim 16, wherein the constituent subsets are statistically summarized individually, and wherein generating at least one summary of data in each of the group-by subsets includes synthesizing statistical summaries of the constituent subsets.

18. The system of claim 15, wherein the operations further include:

using the grid-computing devices to store the objects, wherein the objects are stored in a distributed manner across the grid-computing system.

19. The system of claim 18, wherein storage locations of the objects are determined by a hash function that involves a modular operation.

20. The system of claim 19, wherein the hash function maps multiple combinations of group-by variables to integers, and wherein each of the integers represents a storage location.

21. The system of claim 13, wherein the objects are initialized in accordance with a shared organizational scheme that facilitates referencing the cardinality data and the summaries included in the objects.

22. The system of claim 13, wherein the group-by subsets include multiple disjoint subsets of the data set, multiple intersecting subsets of the data set, and multiple subsets of the data set which are formed on different combinations of group-by variables.

23. The system of claim 22, wherein the operations further include:

displaying an interface that facilitates defining a subset of the data set by referencing one or more of the group-by subsets;

receiving an input at the interface, the input defining a subset of the data set by referencing at least one of the group-by subsets; and

generating a statistical summary of the defined subset.

24. The system of claim 23, wherein the interface further facilitates defining a subset of the data set by using logical operators to indicate a union of group-by subsets or an intersection of group-by subsets.

25. A method comprising:

accessing a data set that includes multiple entries, each of the entries including data corresponding to multiple variables;

grouping the multiple entries into group-by subsets, wherein the group-by subsets are formed on two or more group-by variables, and wherein the group-by subsets are subsets of the data set;

determining cardinality data for each of the group-by subsets, wherein cardinality data represents a number of entries in a group-by subset;

generating at least one summary of data in each of the group-by subsets, wherein each of the summaries includes the cardinality data determined for the group-by subset;

initializing objects for the group-by subsets, wherein each of the objects include the cardinality data and the at least one summary, and wherein each of the objects includes values of the group-by variables used in forming the group-by subset; and

generating multiple statistical summaries of the data set using the objects.

26. The method of claim 25, wherein the multiple statistical summaries include a histogram that represents a variable distribution with respect to the group-by subsets.

27. The method of claim 25, wherein the data set is partitioned and distributed amongst multiple grid-computing devices in a grid-computing system, and wherein grouping the multiple entries into the group-by subsets includes using parallel processing involving at least two of the grid-computing devices to form at least one of the group-by subsets.

28. The method of claim 27, wherein the data set is partitioned such that the at least one of the group-by subsets is formed by identifying constituent subsets stored in a distributed manner.

29. The method of claim 28, wherein the constituent subsets are statistically summarized individually, and wherein generating at least one summary of data in each of the group-by subsets includes synthesizing statistical summaries of the constituent subsets.

30. The method of claim 27, further comprising:

using the grid-computing devices to store the objects, wherein the objects are stored in a distributed manner across the grid-computing system.

31. The method of claim 30, wherein storage locations of the objects are determined by a hash function that involves a modular operation.

32. The method of claim 31, wherein the hash function maps multiple combinations of group-by variables to integers, and wherein each of the integers represents a storage location.

33. The method of claim 25, wherein the objects are initialized in accordance with a shared organizational scheme that facilitates referencing the cardinality data and the summaries included in the objects.

34. The method of claim 25, wherein the group-by subsets include multiple disjoint subsets of the data set, multiple intersecting subsets of the data set, and multiple subsets of the data set which are formed on different combinations of group-by variables.

35. The method of claim 34, further comprising:

displaying an interface that facilitates defining a subset of the data set by referencing one or more of the group-by subsets;

receiving an input at the interface, the input defining a subset of the data set by referencing at least one of the group-by subsets; and

generating a statistical summary of the defined subset.

36. The method of claim 35, wherein the interface further facilitates defining a subset of the set of data by using logical operators to indicate a union of group-by subsets or an intersection of group-by subsets.