SYSTEM AND METHOD FOR MEASURING SIMILARITY OF SEQUENCES WITH MULTIPLE ATTRIBUTES

• US 20080235222A1
• Filed: 03/21/2007
• Published: 09/25/2008
• Est. Priority Date: 03/21/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mojsilovic, Aleksandra
• Application Number:
  US11/689,490
• Publication Number:
  US 20080235222A1
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 2218/16 by matching signal segments

Abstract

A method (and structure) for quantifying an ordered sequence of data, includes receiving data of the ordered sequence and determining a skeleton of the ordered sequence. The skeleton includes a plurality of perceptually important points (PIPs) of the ordered sequence, as derived by determining one or more points of local maxima of the data over the ordered sequence.

Claims

1. A computer configured to execute a process of quantifying an ordered sequence of data, said computer comprising:

a data receiver to receive data of said ordered sequence; and

a calculator to determine a skeleton of said ordered sequence,

wherein said skeleton comprises a plurality of perceptually important points (PIPs) of said ordered sequence, as derived by determining one or more points of local maxima of said data over said ordered sequence.

2. The computer of claim 1, wherein said ordered sequence is multivariate.

3. The computer of claim 1, wherein said ordered sequence comprises a time series of data.

4. The computer of claim 1, wherein data of said ordered sequence is preliminarily converted into a metric space when said ordered sequence data is not presented in a manner allowing metric operations on said data.

5. The computer of claim 4, wherein a successive PIP is determined by said calculator by constructing a line between two previous PIPs and a maximum relative to said line is identified for data between said two previous PIPs, to become said successive PIP.

6. The computer of claim 5, wherein successive PIPs are sequentially determined by said calculator until a termination test determines that said skeleton is sufficiently developed.

7. The computer of claim 6, wherein said termination test comprises a local similarity measure.

8. The computer of claim 5, wherein a starting endpoint and an ending endpoint are identified for said ordered sequence of data and said starting and ending endpoints are assigned to be a first PIP and a second PIP for said ordered sequence.

9. The computer of claim 1, said calculator further selectively determining a local similarity metric d for said ordered sequence, for use in determining said PIPs, and a global similarity metric, for use in comparing said skeleton with a skeleton of another ordered sequence.

10. The computer of claim 9, said calculator further processing at least one of the following procedures:

comparing a similarity of said skeleton with a skeleton of another ordered sequence;

searching for similarities within said ordered sequence;

searching for similar ordered sequence in a database;

recognizing or identifying events or specific sequences;

searching for an event or similar event;

analyzing an ordered sequence expressed as a time series;

discovering relationships within a time series or between two different time series;

categorizing signals into groups or clusters;

an optimization processing;

a time-series compression; and

an indexing of data.

11. The computer of claim 10, wherein said procedure involves a time series of financial data.

12. A computerized method of quantifying an ordered sequence of data, comprising:

receiving data of said ordered sequence; and

determining a skeleton of said ordered sequence,

wherein said skeleton comprises a plurality of perceptually important points (PIPs) of said ordered sequence, as derived by determining one or more points of local maxima of said data over said ordered sequence.

13. The method of claim 12, further comprising preliminarily converting said ordered sequence data into a metric space when said ordered sequence data is not presented in a manner allowing metric operations on said data.

14. The method of claim 12, wherein a successive PIP is determined by constructing a line between two previous PIPs and a maximum relative to said line is identified for data between said two previous PIPs, to become said successive PIP.

15. The method of claim 14, wherein successive PIPs are sequentially determined by until a termination test determines that said skeleton is sufficiently developed.

16. The method of claim 12, wherein a starting endpoint and an ending endpoint are identified for said ordered sequence of data and said starting and ending endpoints are assigned to be a first PIP and a second PIP for said ordered sequence.

17. The method of claim 12, said method further selectively:

determining a local similarity metric d for said ordered sequence, for use in determining said PIPs; and

determining a global similarity metric, for use in comparing said skeleton with a skeleton of another ordered sequence.

18. The method of claim 12, said method further comprising at least one of:

comparing a similarity of said skeleton with a skeleton of another ordered sequence;

searching for similarities within said ordered sequence;

searching for similar ordered sequence in a database;

recognizing or identifying events or specific sequences;

searching for an event or similar event;

analyzing an ordered sequence expressed as a time series;

discovering relationships within a time series or between two different time series;

categorizing signals into groups or clusters;

an optimization processing;

a time-series compression; and

an indexing of data.

19. The method of claim 12, as implemented into a service entity that provides consultation service to another entity.

20. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of quantifying an ordered sequence of data, said method comprising:

receiving data of said ordered sequence; and

determining a skeleton of said ordered sequence,

wherein said skeleton comprises a plurality of perceptually important points (PIPs) of said ordered sequence, as derived by determining one or more points of local maxima of said data over said ordered sequence.