Methods and systems to operate on group-by sets with high cardinality

• US 9,633,104 B2
• Filed: 05/05/2014
• Issued: 04/25/2017
• Est. Priority Date: 05/03/2013
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Wu, Xunlei, Schabenberger, Oliver
• Primary Examiner(s): Richardson, James E
• Application Number:
  US14/270,297
• Publication Number:
  US 20140330827A1
• Time in Patent Office: 1,086 Days
• 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 include multiple disjoint subsets of the data set, multiple intersecting subsets of the data set, or multiple subsets of the data set which are formed on different combinations of group-by variables;

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;

generating a statistical summary of the defined subset;

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 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.

11. 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 include multiple disjoint subsets of the data set, multiple intersecting subsets of the data set, or multiple subsets of the data set which are formed on different combinations of group-by variables;

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;

generating a statistical summary of the defined subset;

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.

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

13. The system of claim 11, 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.

14. The system of claim 13, 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.

15. The system of claim 14, 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 sub sets.

16. The system of claim 13, 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.

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

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

19. The system of claim 11, 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.

20. The system 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.

21. 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 include multiple disjoint subsets of the data set, multiple intersecting subsets of the data set, or multiple subsets of the data set which are formed on different combinations of group-by variables;

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;

generating a statistical summary of the defined subset;

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.

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

23. The method of claim 21, 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.

24. The method of claim 23, 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.

25. The method of claim 24, 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 sub sets.

26. The method of claim 23, 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.

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

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

29. The method of claim 21, 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.

30. The method of claim 21, 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.