Method for automated detection of data glitches in large data sets

• US 7,805,266 B1
• Filed: 07/17/2001
• Issued: 09/28/2010
• Est. Priority Date: 07/17/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Dasu, Tamraparni, Johnson, Theodore
• Primary Examiner(s): Assouad; Patrick
• Application Number:
  US09/906,104
• Time in Patent Office: 3,360 Days
• Field of Search: 702/66, 702/179, 702/180, 702/181, 702/189, 702/190, 702/191, 707/1, 707/3, 707/6, 709/223, 709/229
• US Class Current: 702/66
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data

Abstract

Embodiments of the invention allow the efficient detection of glitches in a set of data. In one embodiment, a set of datapoints is received. The datapoints are transformed into a transformed space, and the transformed space is segmented into a plurality of regions. For each datapoint, a time series is generated representing the trajectory of the transformed datapoint through regions of the segmented transformed space. Data corresponding to transformed datapoints whose trajectories exhibit an unusual pattern are transmitted.

Claims

1. A method for detecting data glitches in a set of datapoints comprising:

receiving a set of datapoints, each of the datapoints having n attributes, where n is an integer greater than zero;

transforming the datapoints into a datasphere representation;

segmenting the datasphere into a plurality of regions;

determining a plurality of time series representing the trajectories of the transformed datapoints through regions of the segmented datasphere; and

transmitting data in connection with transformed datapoints whose trajectories exhibit an unusual pattern.

2. The method of claim 1 wherein the transforming step includes choosing a common center for the datapoints and transforming the values of the attributes of each datapoint based on the common center.

3. The method of claim 2 wherein the boundaries of the segments of the datasphere are at least partially based on the common center.

4. The method of claim 3 wherein at least part of the boundaries of the segments of the datasphere are formed by concentric hyperspheres of dimension n centered on the common center.

5. The method of claim 4 wherein at least another part of the boundaries of the segments of the hypersphere are formed by the boundaries of n-dimensional pyramids given by the following formulae:

x_i=x_j, for 1≦

i<

j≦

d

where x_i denotes the transformed value of the i^th attribute, and d denotes the total number of attributes.

6. The method of claim 5 wherein in the transforming step, the transformed value of an attribute for a datapoint is calculated based on the difference between the value of the attribute for the datapoint and the mean value of the attribute over all datapoints and all time, scaled by the standard deviation of the value of the attribute for the datapoint over all datapoints and all time.

7. The method of claim 1 wherein the unusual pattern is identified based on the frequency of at least one transition of a transformed datapoint between regions of the segmented datasphere.

8. The method of claim 1 including the step of statistical analysis of datapoints corresponding to the transformed datapoints whose trajectories exhibit an unusual pattern.

9. The method of claim 1 wherein the unusual pattern, for one of the transformed datapoints, includes a transition from a first region of the segmented datasphere to a second region followed by a transition from the second region back to the first region.

10. The method of claim 1 wherein the unusual pattern is an infrequent transition.

11. A computer-readable medium having stored thereon instructions that, when executed, cause a processor to:

receive a set of datapoints, each of the datapoints having n attributes, where n is an integer greater than zero;

transform the datapoints into a datasphere representation;

segment the datasphere into a plurality of regions;

determine a plurality of time series representing the trajectories of the transformed datapoints through regions of the segmented datasphere; and

transmit data in connection with transformed datapoints whose trajectories exhibit an unusual pattern.

12. A method for detecting data glitches in a set of datapoints comprising:

receiving a set of datapoints;

transforming the datapoints into transformed space;

segmenting the transformed space into a plurality of regions;

determining a plurality of time series representing the trajectories of the transformed datapoints through regions of the segmented transformed space;

transmitting data in connection with transformed datapoints whose trajectories exhibit an unusual pattern.

13. The method of claim 12, wherein in the receiving step, a plurality of values of attributes is received for each datapoint in the set.

14. The method of claim 12, wherein at least one of the attributes for which values are received is an attribute not representing a component of spatial location.

15. The method of claim 14 wherein the transforming step transforms the datapoints into a datasphere representation.

16. The method of claim 12 including the step of statistical analysis of datapoints corresponding to the transformed datapoints whose trajectories exhibit an unusual pattern.

17. The method of claim 12 wherein the unusual pattern is an infrequent transition.

18. An apparatus for determining a network traffic anomaly, the apparatus comprising:

(a) a processor;

(b) a port coupled to the processor; and

(c) a memory, coupled to said processor, said memory storing instructions adapted to be executed by said processor, the instructions including;

receiving a set of datapoints, each of the datapoints having n attributes, where n is an integer greater than zero;

transforming the datapoints into a datasphere representation;

segmenting the datasphere into a plurality of regions;

determining a plurality of time series representing the trajectories of the transformed datapoints through regions of the segmented datasphere; and

transmitting data in connection with transformed datapoints whose trajectories exhibit an unusual pattern.

19. The method of claim 18 wherein the transforming step includes choosing a common center for the datapoints and transforming the values of the attributes based on the common center.

20. The apparatus of claim 19 wherein the unusual pattern is identified based on the frequency of at least one transition of a transformed datapoint between regions of the segmented datasphere.

21. The apparatus of claim 20 wherein the datapoints corresponding to the transformed datapoints whose trajectories exhibit an unusual pattern are analyzed statistically for glitches.

22. A method for detecting glitches in a set of data, the set of data including the values of each of a plurality of measurement vectors at a plurality of time values, the value of a measurement vector at a given time value including the values of a plurality of attributes associated with the measurement vector at the time value, the method comprising:

receiving the set of data;

transforming each measurement vector of the plurality of measurement vectors at each value of time into a datasphere representation;

segmenting the datasphere into a plurality of regions;

determining a time series representing the trajectory of each of the plurality of transformed measurement vectors through regions of the segmented datasphere; and

transmitting data in connection with transformed measurement vectors whose trajectories exhibit an unusual pattern.

23. A method for detecting data glitches comprising:

representing a datapoint as a first time-dependent vector;

generating a second time-dependent vector based on the differences between the first time-dependent vector and a center vector at each of a plurality of time values;

comparing the second time-dependent vector against a predetermined segment map at each of the plurality of time values;

determining a sector-region occupied by the second time-dependent vector based on the comparison at each of the plurality of time values; and

flagging the datapoint if the determined sector-regions match a predetermined pattern.

24. The method of claim 23 wherein the center vector is determined based on a plurality of datapoints including the datapoint.