Methods and apparatus to determine statistical dominance point descriptors for multidimensional data

• US 8,160,837 B2
• Filed: 12/12/2008
• Issued: 04/17/2012
• Est. Priority Date: 12/12/2008
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Korn, Philip, Srivastava, Divesh
• Primary Examiner(s): Tsai, Carol
• Application Number:
  US12/334,252
• Publication Number:
  US 20100153064A1
• Time in Patent Office: 1,222 Days
• Field of Search: 702/179, 707/600, 707/769, 707/999.002, 707/999.03, 707/776, 707/E17.03, 382/168, 382/103, 342/90, 342/192, 342/193, 342/195, 342/146, 345/650, 345/661, 345/676, 345/156
• US Class Current: 702/179
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

Methods and apparatus to determine statistical dominance point descriptors for multidimensional data are disclosed. An example method disclosed herein comprises determining a first joint dominance value for a first data point in a multidimensional data set, data points in the multidimensional data set comprising multidimensional values, each dimension corresponding to a different measurement of a physical event, the first joint dominance value corresponding to a number of data points in the multidimensional data set dominated by the first data point in every dimension, determining a first skewness value for the first data point, the first skewness value corresponding to a size of a first dimension of the first data point relative to a combined size of all dimensions of the first data point, and combining the first joint dominance and first skewness values to determine a first statistical dominance point descriptor associated with the first data point.

Claims

1. A method to determine statistical dominance point descriptors for a multidimensional data set, the method comprising:

determining, using a programmable processor, a first joint dominance value for a first data point in the multidimensional data set, each data point in the multidimensional data set comprising a multidimensional value, each dimension of the multidimensional value corresponding to a different measurement of a physical event, the first joint dominance value corresponding to a number of data points in the multidimensional data set dominated by the first data point in every dimension;

determining, using the programmable processor, a first skewness value for the first data point, the first skewness value corresponding to a size of a first dimension of the first data point relative to a combined size of all dimensions of the first data point; and

combining, using the programmable processor, the first joint dominance value and the first skewness value to determine a first statistical dominance point descriptor associated with the first data point.

2. A method as defined in claim 1 further comprising:

storing the multidimensional data set in a computer memory; and

presenting the first joint dominance value via a graphical user interface.

3. A method as defined in claim 1 wherein the physical event corresponds to data network traffic, a first dimension of the multidimensional value corresponds to first measurements of numbers of packets in a data flow included in the data network traffic, and the second dimension of the multidimensional value corresponds to second measurements of numbers of bytes included in the packets in the data flow.

4. A method as defined in claim 1 wherein the physical event corresponds to an examination taken by a plurality of participants, the examination producing a plurality of measured scores for each participant, a first dimension of the multidimensional value corresponds to first measured scores attained by the plurality of participants and the second dimension of the multidimensional value corresponds to second measured scores attained by the plurality of participants.

5. A method as defined in claim 1 further comprising:

obtaining specified second joint dominance and skewness values;

identifying a first subset of data points in the multidimensional data set associated with joint dominance values less than or equal to the specified second joint dominance value;

identifying a second subset of data points in the multidimensional data set associated with skewness values less than or equal to the specified second skewness value;

identifying a third subset of data points comprising an intersection of the first and second subsets of data points;

identifying a fourth subset of data points comprising those data points in the third subset of data points that are not jointly dominated by any other data point in the third subset of data points; and

identifying a second data point in the multidimensional data set to be associated with a second statistical dominance point descriptor corresponding to the specified second joint dominance and skewness values, the second data point identified as being associated with a largest skewness value relative to all other data points in the fourth subset of data points.

6. A method as defined in claim 1 wherein determining the first joint dominance value for the first data point comprises:

determining a count of the number of data points in the multidimensional data set jointly dominated by the first data point, wherein the first data point jointly dominates a second data point when a first dimensional value of the first data point is greater than or equal to a first dimensional value of the second data point and a second dimensional value of the first data point is greater than or equal to a second dimensional value of the second data point; and

dividing the determined count by a total number of data points in the multidimensional data set.

7. A method as defined in claim 1 further comprising:

obtaining a specified second joint dominance value; and

determining a joint dominance quantour corresponding to the specified second joint dominance value, the joint dominance quantour comprising a subset of data points in the multidimensional data set associated with joint dominance values less than or equal to the specified second joint dominance value, each data point in the subset of data points also not being jointly dominated by any other data point in the subset of data points.

8. A method as defined in claim 1 wherein determining the skewness value for the first data point comprises:

determining a first rank of the first data point in the first dimension, the first rank corresponding to the size of the first dimension of the first data point;

determining a second rank of the first data point in a second dimension; and

dividing the first rank by a sum of the first and second ranks, the sum of the first and second ranks corresponding to the combined size of all dimensions of the first data point.

9. A method as defined in claim 1 further comprising:

obtaining a specified second skewness value; and

determining a skewness radial corresponding to the specified second dominance-skewness value, the skewness radial comprising a subset of data points in the multidimensional data set associated with skewness values less than or equal to the specified second skewness value, each data point in the subset of data points also having first dimensional values that are not less than and second dimensional values that are not greater than, respectively, corresponding first and second dimensional values of any other point in the subset of data points.

10. A method as defined in claim 1 wherein the multidimensional data set comprises a first summary data set, and further comprising:

obtaining a second measured data set comprising measured data points obtained by measuring the physical event;

summarizing the second measured data set to determine the first summary data set; and

storing the first summary data set in a computer memory, an amount of memory required to store the first summary data set being less than an amount of memory that would be required to store the second measured data set.

11. A method as defined in claim 10 wherein the summary data set comprises a first dimensional sequence of tuples, a second dimensional sequence of tuples and a two-dimensional data summary indexed by the first and second dimensional sequences of tuples, each tuple comprising (1) a value of one measured data point lying in the data value range represented by the tuple and (2) a count of the number of measured data points lying in the data value range represented by the tuple, and wherein summarizing the second measured data set to determine the first summary data set comprises:

inserting a first dimensional value of a measured data point from the measured data set into a first tuple included in the first dimensional sequence of tuples;

inserting a second dimensional value of the measured data point into a second tuple included in the second dimensional sequence of tuples;

inserting the measured data point into a cell of the two-dimensional data summary indexed by the first and second tuple by incrementing a count value associated with the cell; and

compressing the first dimensional sequence of tuples, the second dimensional sequence of tuples and the two-dimensional data summary.

12. A method as defined in claim 10 wherein the summary data set comprises a first dimensional sequence of tuples and separate second dimensional sequences of tuples, each second dimensional sequence of tuples associated with a respective tuple in the first dimensional sequence of tuples, each tuple comprising (1) a value of one measured data point lying in the data value range represented by the tuple and (2) a count of the number of measured data points lying in the data value range represented by the tuple, and wherein summarizing the second measured data set to determine the first summary data set comprises:

inserting a first dimensional value of a measured data point from the measured data set into a first tuple included in the first dimensional sequence of tuples;

inserting a second dimensional value of the measured data point into a second tuple included in a particular second dimensional sequence of tuples indexed by the first tuple; and

compressing the first dimensional sequence of tuples and the second dimensional sequences of tuples.

13. A method as defined in claim 10 wherein the summary data set comprises a first dimensional hierarchical arrangement of tuples and separate second dimensional hierarchical arrangements of tuples, each second dimensional hierarchical arrangement of tuples associated with a respective tuple in the first dimensional hierarchical arrangement of tuples, each tuple comprising (1) a value of one measured data point lying in the data value range represented by the tuple and (2) a count of the number of measured data points lying in the data value range represented by the tuple, and wherein summarizing the second measured data set to determine the first summary data set comprises:

inserting a first dimensional value of a measured data point from the measured data set into a first tuple included in the first dimensional hierarchical arrangement of tuples;

inserting a second dimensional value of the measured data point into respective second tuples included in corresponding second dimensional hierarchical arrangements of tuples indexed by the first tuple and all ancestors of the first tuple included in the first dimensional hierarchical arrangement of tuples; and

compressing the first dimensional hierarchical arrangement of tuples and the second dimensional hierarchical arrangements of tuples.

14. A tangible article of manufacture storing machine readable instructions which, when executed, cause a machine to at least:

store a multidimensional data set in a computer memory;

determine a first joint dominance value for a first data point in the multidimensional data set, each data point in the multidimensional data set comprising a multidimensional value, the first joint dominance value corresponding to a number of data points in the multidimensional data set dominated by the first data point in every dimension;

determine a first skewness value for the first data point, the first skewness value corresponding to a size of a first dimension of the first data point relative to a combined size of all dimensions of the first data point;

combine the first joint dominance value and the first skewness value to determine a first statistical dominance point descriptor associated with the first data point; and

present the first joint dominance value via a graphical user interface.

15. An article of manufacture as defined in claim 14 wherein the machine readable instructions, when executed, further cause the machine to:

obtain specified second joint dominance and skewness values;

identify a first subset of data points in the multidimensional data set associated with joint dominance values less than or equal to the specified second joint dominance value;

identify a second subset of data points in the multidimensional data set associated with skewness values less than or equal to the specified second skewness value;

identify a third subset of data points comprising an intersection of the first and second subsets of data points;

identify a fourth subset of data points comprising those data points in the third subset of data points that are not jointly dominated by any other data point in the third subset of data points; and

identify a second data point in the multidimensional data set to be associated with a second statistical dominance point descriptor corresponding to the specified second joint dominance and skewness values, the second data point identified as being associated with a largest skewness value relative to all other data points in the fourth subset of data points.

16. A network monitoring device to determine statistical dominance point descriptors associated with monitoring network traffic, the network monitoring device comprising:

a data capture interface to obtain a two-dimensional data set, each data point in the data set comprising a first dimensional value corresponding to a first measurement of the data network traffic and a second dimensional value corresponding to a different second measurement of the data network traffic;

a joint dominance processor to determine a first joint dominance value for a first data point in the two-dimensional data set, the first joint dominance value corresponding to a number of data points in the data set dominated by the first data point in both dimensions;

a skewness processor to determine a first skewness value for the first data point, the first skewness value corresponding to a size of the first dimensional value of the first data point relative to a combined size of the first and second dimensional values of the first data point; and

a dominance-skewness quantile processor to at least one of (1) combine the first joint dominance value and the first skewness value to determine a first statistical dominance point descriptor associated with the first data point, or (2) identify a second data point associated with a second statistical dominance point descriptor corresponding to specified second joint dominance and skewness values.

17. A network monitoring device as defined in claim 16 further comprising a presentation interface to present at least one of the first statistical dominance point descriptor determined to be associated with the first data point or the second data point identified as being associated with the second statistical dominance point descriptor.

18. A network monitoring device as defined in claim 16 wherein the dominance-skewness quantile processor is further to:

identify a first subset of data points in the two-dimensional data set associated with joint dominance values less than or equal to the specified second joint dominance value;

identify a second subset of data points in the two-dimensional data set associated with skewness values less than or equal to the specified second skewness value;

identify a third subset of data points comprising an intersection of the first and second subsets of data points;

identify a fourth subset of data points comprising those data points in the third subset of data points that are not jointly dominated by any other data point in the third subset of data points; and

identify the second data point in the two-dimensional data set that is to be associated with the second statistical dominance point descriptor corresponding to the specified second joint dominance and skewness values, the second data point identified as being a particular point in the fourth subset of data points associated with a largest skewness value relative to all other data points in the fourth subset of data points.

19. A network monitoring device as defined in claim 16 wherein the joint dominance processor is further to:

determine a count of the number of data points in the two-dimensional data set jointly dominated by the first data point, wherein the first data point jointly dominates a third data point when the first dimensional value of the first data point is greater than or equal to the first dimensional value of the third data point and the second dimensional value of the first data point is greater than or equal to the second dimensional value of the third data point; and

dividing the determined count by a total number of data points in the multidimensional data set to determine the first joint dominance value for the first data point.

20. A network monitoring device as defined in claim 16 wherein the skewness processor is further to

determine a first rank associated with the first dimensional value of the first data point;

determine a second rank associated with the second dimensional value of the first data point; and

divide the first rank by a sum of the first and second ranks to determine the first skewness value for the first data point.