METHOD AND SYSTEM FOR ANALYZING TIME SERIES DATA

• US 20080170507A1
• Filed: 01/16/2007
• Published: 07/17/2008
• Est. Priority Date: 01/16/2007
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Handley, John C., Virdhagriswaran, Sankar
• Granted Patent: US 7,770,072 B2
• Time in Patent Office: Days
• US Class Current: 370/242
• CPC Class Codes: G06F 11/0733 in a data processing system embedded in an image processing device, e.g. printer, facsimile, scanner
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36

Abstract

Systems and methods for performing fault analysis using numerically coded time series data are disclosed. First time series data, including a plurality of first time entries and an associated first data value for each first time entry, may be received for a machine variable for a first printer. Second time series data, including a plurality of second time entries and an associated second data value for each second time entry, may be received for the machine variable for each of a plurality of second printers. For each second printer, a similarity measurement may be determined for the first time series data for the first printer and the second time series data for the second printer. One or more closest matching second printers may be determined based on the similarity measurements. An association may be displayed between the first printer and each closest matching second printer.

Claims

1. A method of performing fault analysis using numerically coded time series data from a plurality of printers, the method comprising:

receiving first time series data for a machine variable for a first printer, wherein the first time series data comprises a plurality of first time entries and an associated first data value for each first time entry;

receiving second time series data for the machine variable for a plurality of second printers, wherein the second time series data comprises a plurality of second time entries and an associated second data value for each second time entry;

for each second printer, determining a similarity measurement for the first time series data for the machine variable for the first printer and the second time series data for the machine variable for the second printer;

determining one or more closest matching second printers based on the similarity measurements; and

displaying an association between the first printer and each closest matching second printer.

2. The method of claim 1 wherein each of the first time series data and the second time series data comprises non-constant time series data.

3. The method of claim 1 wherein determining a similarity measurement comprises:

scaling each first data value to a scaled first data value based on first data values having a minimum value and a maximum value in the first time series data; and

scaling each second data value to a scaled second data value based on first data values having a minimum value and a maximum value in the second time series data; and

determining a similarity measurement using the scaled first data values and scaled second data values.

4. The method of claim 1 wherein determining a similarity measurement comprises:

initializing one or more similarity values;

for each first time entry in the first time series data;

for each second time entry in the second time series data;

evaluating a cost function based on the first data value associated with the first time entry and the second data value associated with the second time entry to determine a cost value,

calculating a minimum similarity value from one or more previously calculated similarity values,

summing the minimum similarity value and the cost value to produce a similarity value associated with the first time entry and the second time entry, and

storing the similarity value associated with the first time entry and the second time entry; and

setting the similarity measurement to the similarity value associated with the last first time entry and the last second time entry.

5. The method of claim 1 wherein determining a similarity measurement comprises:

initializing one or more similarity values;

for each first time entry in the first time series data;

for each second time entry in the second time series data;

determining whether the data value for the first time entry equals the data value for the second time entry,

if so, setting the similarity value associated with the first time entry and the second time entry to the sum of one and the similarity value associated with the time entry preceding the first time entry and the time entry preceding the second time entry, and

if not, setting the similarity value associated with, the first time entry and the second time entry to the maximum of the similarity value associated with the time entry preceding the first time entry and the second time entry and the similarity value associated with the first time entry and the time entry preceding the second time entry; and

setting the similarity measurement to the similarity value associated with the last first time entry and the last second time entry.

6. The method of claim 1 wherein determining a similarity measurement comprises:

compressing the first time series data;

determining a first value, wherein the first value comprises a size of the compressed first time series data;

compressing the second time series data;

determining a second value, wherein the second value comprises a size of the compressed second time series data;

concatenating the first time series data and the second time series data to produce concatenated time series data;

compressing the concatenated time series data;

determining a third value, wherein the first value comprises a size of the compressed first time series data;

setting the similarity measurement to the third value divided by the sum of the first value and the second value.

7. The method of claim 1 wherein determining a similarity measurement comprises:

for each first time entry in the first time series data, setting a similarity value associated with the first time entry and an initial second time entry to one minus the square of the difference between the data value for the first time entry and the data value for the initial second time entry;

for each second time entry in the second time series data, setting a similarity value associated with an initial first time entry and the second time entry to one minus the square of the difference between the data value for the initial first time entry and the data value for the second time entry;

for each first time entry other than the initial first time entry;

for each second time entry other than the initial second time entry;

setting an intermediate value to one minus the square of the difference between, the data value for the first time entry and the data value for the second time entry, and

setting a similarity value associated with the first time entry and the second time entry to the maximum of zero, the sum of the intermediate value and the similarity value associated with the time entry preceding the first time entry and the time entry preceding the second time entry, the sum of a penalty value and the maximum, similarity value associated with the first time entry, and the sum of a penalty value and the maximum similarity value associated with the second time entry; and

setting the similarity measurement to the largest similarity value divided by the smaller of a number of first time entries and a number of second time entries.

8. A method of performing fault analysis using numerically coded time series data from a printer, the method comprising:

receiving time series data for a plurality of machine variables for the printer;

for at least one machine variable;

determining a plurality of similarity measurements for the machine variable, wherein each similarity measurement corresponds to a similarity between the machine variable and a second machine variable, and

determining one or more closest matching machine variables for the machine variable based on the similarity measurements; and

displaying an association between a particular machine variable and the one or more closest matching machine variables for the particular machine variable.

9. The method of claim 8 wherein the time series data comprises non-constant time series data.

10. The method of claim 8 wherein determining a plurality of similarity measurements for the machine variable comprises determining a correlation between the machine variable and a second machine variable.

11. The method of claim 8 wherein the time series data for each machine variable comprises a plurality of time entries and an associated data value for each time entry.

12. The method of claim 11, further comprising:

for each machine variable, scaling each data value to a scaled data value based on data values having a minimum value and a maximum value in the time series data, and

wherein the step of determining a plurality of similarity measurements is performed using the scaled data values for the machine variable and the scaled data values for the second machine variable.

13. A system for performing fault analysis using numerically coded time series data from a plurality of printers, the system comprising:

a processor;

a processor-readable storage medium in communication with the processor; and

a communications interface in communication with the processor,

wherein the processor-readable storage medium contains one or more programming instructions for performing a method of performing fault analysis using numerically coded time series data from a plurality of printers, the method comprising;

receiving first time series data for a machine variable for a first printer via the communications interface, wherein the first time series data comprises a plurality of first time entries and an associated first data value for each first time entry,

receiving second time series data for the machine variable for a plurality of second printers via the communications interface, wherein the second time series data comprises a plurality of second time entries and an associated second data value for each second time entry,

for each second printer, determining a similarity measurement for the first time series data for the machine variable for the first printer and the second time series data for the machine variable for the second printer,

determining one or more closest matching second printers based on the similarity measurements, and

displaying an association between the first printer and each closest matching second printer.

14. The system of claim 13 wherein determining a similarity measurement comprises:

initializing one or more similarity values;

for each first time entry in the first time series data;

for each second time entry in the second time series data;

evaluating a cost function based on the first data value associated with the first time entry and the second data value associated with, the second time entry to determine a cost value,

calculating a minimum similarity value from one or more previously calculated similarity values,

summing the minimum similarity value and the cost value to produce a similarity value associated with the first time entry and the second time entry, and

storing the similarity value associated with the first time entry and the second time entry; and

setting the similarity measurement to the similarity value associated with the last first time entry and the last second time entry.

15. The system of claim 13 wherein determining a similarity measurement comprises:

initializing one or more similarity values;

for each first time entry in the first time series data;

for each second time entry in the second time series data;

determining whether the data value for the first time entry equals the data value for the second time entry,

if so, setting the similarity value associated with the first time entry and the second time entry to the sum of one and the similarity value associated with the time entry preceding the first time entry and the time entry preceding the second time entry, and

if not, setting the similarity value associated with the first time entry and the second time entry to the maximum of the similarity value associated with, the time entry preceding the first time entry and the second time entry and the similarity value associated with the first time entry and the time entry preceding the second time entry; and

setting the similarity measurement to the similarity value associated with the last first time entry and the last second time entry.

16. The system of claim 13 wherein determining a similarity measurement comprises:

compressing the first time series data;

determining a first value, wherein the first value comprises a size of the compressed first time series data;

compressing the second time series data;

determining a second value, wherein the second value comprises a size of the compressed second time series data;

concatenating the first time series data and the second time series data to produce concatenated time series data;

compressing the concatenated time series data;

determining a third value, wherein the first value comprises a size of the compressed first time series data;

setting the similarity measurement to the third value divided by the sum of the first value and the second value.

17. The system of claim 13 wherein determining a similarity measurement comprises:

for each first time entry in the first time series data, setting a similarity value associated with the first time entry and an initial second time entry to one minus the square of the difference between the data value for the first time entry and the data value for the initial second time entry;

for each second time entry in the second time series data, setting a similarity value associated with an initial first time entry and the second time entry to one minus the square of the difference between the data value for the initial first time entry and the data value for the second time entry;

for each first time entry other than the initial first time entry;

for each second time entry other than the initial second time entry;

setting an intermediate value to one minus the square of the difference between the data value for the first time entry and the data value for the second time entry, and

setting a similarity value associated with the first time entry and the second time entry to the maximum of zero, the sum of the intermediate value and the similarity value associated with the time entry preceding the first time entry and the time entry preceding the second time entry, the sum of a penalty value and the maximum similarity value associated with the first time entry, and the sum of a penalty value and the maximum similarity value associated with the second time entry; and

setting the similarity measurement to the largest similarity value divided by the smaller of a number of first time entries and a number of second time entries.

18. A system for performing fault analysis using numerically coded time series data for a printer, the system comprising:

a processor; and

a processor-readable storage medium in communication with the processor,

wherein the processor-readable storage medium contains one or more programming instructions for performing a method of performing fault analysis using numerically coded time series data for a printer, the method comprising;

receiving time series data for a plurality of machine variables for the printer,

for at least one machine variable;

determining a plurality of similarity measurements for the machine variable, wherein each similarity measurement corresponds to a similarity between the machine variable and a second machine variable, and

determining one or more closest matching machine variables for the machine variable based on the similarity measurements, and

displaying an association between a particular machine variable and the one or more closest matching machine variables for the particular machine variable.

19. The system of claim 18 wherein determining a plurality of similarity measurements for the machine variable comprises determining a correlation between the machine variable and a second machine variable.

20. The system of claim 18, further comprising a communications interface in communication with the processor, wherein receiving time series data comprises receiving time series data for a plurality of machine variable for the printer via the communications interface,