Detecting an event from time-series data sequences

• US 10,108,582 B2
• Filed: 06/25/2015
• Issued: 10/23/2018
• Est. Priority Date: 06/26/2014
• Status: Active Grant

• Current Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Original Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Inventors: Hassan, Ehtesham, Agarwal, Puneet, Shroff, Guatam
• Primary Examiner(s): Lee, Cheung
• Application Number:
  US14/749,881
• Publication Number:
  US 20150378963A1
• Time in Patent Office: 1,216 Days
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• 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
• CPC Class Codes: G07C 5/0808 Diagnosing performance data testing of vehicles G01M17/00; testing of electrical installation on vehicles G01R31/005

Abstract

The present subject matter discloses a system and a method for detecting an event from time-series data sequences. The system receives time-series data sequences generated by sensors, wherein the time-series data sequences comprise sample points. The system pairs the sample points with one another for determining pairs of the sample points. The system computes Euclidean distances and angles between the sample points for determining distance matrix and angle matrix corresponding to the sample points. Further, the system determines global distribution of the plurality of pairs of sample points, wherein the global distribution of the plurality of pairs of sample points represent 2D shape histogram for the time-series data sequence. Further, the system concatenates the 2D shape histogram for each time-series data sequence to generate a concatenated shape histogram. Finally the system matches the concatenated shape histogram to pre-stored shape histograms for determining the event.

Claims

1. A method for detecting an event from time-series data sequences, the method comprising:

receiving, by a processor, the time-series data sequences of variable lengths, generated by a plurality of sensors, wherein the time-series data sequences comprise timestamp information;

sampling the time-series data sequences at a uniform sampling rate for generating sample points;

generating, by the processor, a plurality of pairs of sample points using the sample points, wherein the plurality of pairs of sample points are generated by pairing each sample point with one another;

computing, by the processor, a distance matrix (D) and an angle matrix (A) for one or more pairs of the sample points of the plurality of pairs of sample points;

generating, by the processor, a two-dimensional (2D) shape histogram for the time-series data sequences using the distance matrix (D) and the angle matrix (A), wherein the 2D shape histogram have a constant dimension and the 2D shape histogram represents a global distribution of the plurality of pairs of sample points, wherein the global distribution of the plurality of pairs of sample points is obtained by computing a shape context of each sample point and wherein the shape context of each sample point is defined based on a distance-angle based distribution of each sample point with respect to remaining sample points;

concatenating, by the processor, the 2D shape histograms for one or more time-series data sequences based on the timestamp information to generate a concatenated shape histogram; and

matching, by the processor, the concatenated shape histogram with a pre-stored set of shape histograms to detect an event.

2. The method of claim 1, wherein the distance matrix (D) is computed by calculating Euclidean distances between the sample points present in the pairs of the sample points, and wherein the Euclidean distances are computed in a two-dimensional Euclidean space.

3. The method of claim 2 further comprising normalizing the distance matrix (D) by dividing the Euclidean distances of one or more rows with a maximum Euclidean distance of the one or more rows.

4. The method of claim 1, wherein the angle matrix (A) is computed by calculating angles between the sample points present in the pairs of the sample points, and wherein the angles are computed in a two-dimensional Euclidean space.

5. The method of claim 1, wherein the 2D shape histograms for the one or more time-series data sequences comprising proximate timestamp information are concatenated to generate the concatenated shape histogram, and concatenating of the 2D shape histograms brings together discriminating features of the 2D shape histograms for the one or more time-series data sequences.

6. The method of claim 1, wherein the concatenated shape histogram is generated by converting the distance matrix (D) and the angle matrix (A) into one-dimensional vectors and merging the one-dimensional (1 D) vectors.

7. The method of claim 1, wherein the concatenated shape histogram is matched with the pre-stored set of shape histograms using a Support Vector Machine (SVM) classifier.

8. The method of claim 1, wherein the pre-stored set of shape histograms comprise shape histograms corresponding to a relevant event.

9. A system for detecting an event from time-series data sequences, the system comprising:

a processor;

a memory coupled to the processor, wherein the processor is capable for executing a plurality of modules stored in the memory, and wherein the plurality of modules comprising;

a pairing module,

to receive the time-series data sequences of variable lengths generated by a plurality of sensors, wherein the time-series data sequences comprise timestamp information;

to sample the time-series data sequences at a uniform sampling rate for generating sample points;

to generate a plurality of pairs of sample points using the sample points such that each sample point is paired with one another;

a matrix computing module,

to compute a distance matrix (D) and an angle matrix (A) for one or more pairs of the sample points of the plurality of pairs of sample points;

a histogram generating and event determining (HGED) module,

to generate a two-dimensional (2D) shape histogram for the time-series data sequences using the distance matrix (D) and the angle matrix (A), wherein the 2D shape histogram have a constant dimension, and the 2D shape histogram represents global distribution of the plurality of pairs of sample points, wherein the global distribution of the plurality of pairs of sample points is obtained by computing a shape context of each sample point and wherein the shape context of each sample point is defined based on a distance-angle based distribution of each sample point with respect to remaining sample points;

to concatenate the 2D shape histograms for one or more time-series data sequences based on the timestamp information to generate a concatenated shape histogram; and

to match the concatenated shape histogram with a pre-stored set of shape histograms to detect an event.

10. The system of claim 9, wherein the distance matrix (D) is computed by calculating Euclidean distances between the sample points present in the pairs of the sample points, and wherein the Euclidean distances are computed in a two-dimensional Euclidean space.

11. The system of claim 10, wherein the matrix computing module further normalizes the distance matrix (D) by dividing the Euclidean distances of one or more rows with a maximum Euclidean distance of the one or more rows.

12. The system of claim 9, wherein the angle matrix (A) is computed by calculating angles between the sample points present in the pairs of the sample points, and wherein the angles are computed in a two-dimensional Euclidean space.

13. The system of claim 9, wherein the time-series data sequences comprising proximate timestamp information are concatenated to generate the concatenated shape histogram, and concatenating the 2D shape histograms brings together discriminating features of the 2D shape histograms for the one or more time-series data sequences.

14. The system of claim 9, wherein the concatenated shape histogram is generated by converting the distance matrix (D) and the angle matrix (A) into one-dimensional vectors and merging the one-dimensional (1D) vectors.

15. The system of claim 9, wherein the concatenated shape histogram is matched with the pre-stored set of shape histograms using a Support Vector Machine (SVM) classifier.

16. The system of claim 9, wherein the pre-stored set of shape histograms comprise shape histograms corresponding to a relevant event.

17. A non-transitory computer readable medium embodying a program executable in a computing device for detecting an event from time-series data sequences, the program comprising:

a program code for receiving the time-series data sequences of variable lengths generated by a plurality of sensors, wherein the time-series data sequences comprise timestamp information;

a program code for sampling the time-series data sequences at a uniform sampling rate for generating sample points;

a program code for generating a plurality of pairs of sample points using the sample points such that each sample point is paired with one another,

a program code for computing a distance matrix (D) and an angle matrix (A) for one or more pairs of the sample points of the plurality of pairs of sample points;

a program code for generating a two-dimensional (2D) shape histogram for the time-series data sequences using the distance matrix (D) and the angle matrix (A), wherein the 2D shape histogram have a constant dimension, and the 2D shape histogram represents global distribution of the plurality of pairs of sample points, wherein the global distribution of the plurality of pairs of sample points is obtained by computing a shape context of each sample point, wherein the global distribution of the plurality of pairs of sample points is obtained by computing a shape context of each sample point and wherein the shape context of each sample point is defined based on a distance-angle based distribution of each sample point with respect to remaining sample points;

a program code for concatenating 2D shape histograms for one or more time-series data sequences based on the timestamp information to generate a concatenated shape histogram; and

a program code for matching the concatenated shape histogram with a pre-stored set of shape histograms to detect an event.