US5664174A — System and method for discovering similar time se…

Claim 1

Independent Claim 278 words

A computer program device comprising: a computer program storage device readable by a digital processing apparatus; and a program means on the program storage device and including instructions executable by the digital processing apparatus for performing method steps for identifying similarities between a first time sequence stored in a database and a second time sequence stored in the database to thereby identify recurring patterns in the database, the method steps comprising: (a) identifying at least first and third subsequence windows, each having a plurality of data elements, each data element being characterized by at least a time and a magnitude, each of the first and third windows being a subset of the first time sequence, to be respectively similar to at least second and fourth subsequence windows, each having a plurality of data elements and each being a subset of the second time sequence, when the difference between a magnitude of a data element of the first window and a magnitude of a data element of the second window is no more than a predetermined value and the difference between a magnitude of a data element of the third window and a magnitude of a data element of the fourth window is no more than the predetermined value; and (b) when the first and third windows and second and fourth windows are separated by respective time gaps, and each gap is less than a predetermined value, joining the first and third windows to establish a first subsequence representative of the first time sequence and joining the second and fourth windows to establish a second subsequence representative of the second time sequence for identifying recurring patterns in the database.

Claim 2

Dependent Claim 278 words

A computer program device comprising: a computer program storage device readable by a digital processing apparatus; and a program means on the program storage device and including instructions executable by the digital processing apparatus for performing method steps for identifying similarities between a first time sequence stored in a database and a second time sequence stored in the database to thereby identify recurring patterns in the database, the method steps comprising: (a) identifying at least first and third subsequence windows, each having a plurality of data elements, each data element being characterized by at least a time and a magnitude, each of the first and third windows being a subset of the first time sequence, to be respectively similar to at least second and fourth subsequence windows, each having a plurality of data elements and each being a subset of the second time sequence, when the difference between a magnitude of a data element of the first window and a magnitude of a data element of the second window is no more than a predetermined value and the difference between a magnitude of a data element of the third window and a magnitude of a data element of the fourth window is no more than the predetermined value; and (b) when the first and third windows and second and fourth windows are separated by respective time gaps, and each gap is less than a predetermined value, joining the first and third windows to establish a first subsequence representative of the first time sequence and joining the second and fourth windows to establish a second subsequence representative of the second time sequence for identifying recurring patterns in the database.

Claim 3

Dependent Claim 51 words

The program device of claim 1, wherein the method steps further comprise the step of establishing the first and second subsequences when the first and third windows overlap each other in time by a first overlap distance and the second and fourth windows overlap each other by the first overlap distance.

Claim 4

Dependent Claim 47 words

The program storage device of claim 2, wherein the first and second subsequences are established only when the times of the earliest data elements in the third and fourth windows are later than the times of the earliest data elements in the first and second windows, respectively.

Claim 5

Dependent Claim 103 words

The program storage device of claim 3, wherein the method steps further comprise the steps of: establishing third and fourth subsequences respectively representative of the first and second time sequences, wherein the times of each data element in the third and fourth subsequences is later than the times of each data element in the first and second subsequences, respectively, such that the first and third subsequences are separated by a gap and the second and fourth subsequences are separated by a gap; and joining the first and third subsequences and second and fourth subsequences when the gaps do not exceed a predetermined value.

Claim 6

Dependent Claim 80 words

The program storage device of claim 4, wherein each subsequence and the first and second time sequences are characterized by respective lengths, and the method steps further comprise the steps of: comparing the sum of the lengths of the subsequences to at least one of the lengths of the time sequences to generate a comparison value; and identifying the first and second time sequences as being similar when the comparison value is equal to or greater than a predetermined value.

Claim 7

Dependent Claim 33 words

The program storage device of claim 1, wherein the method steps further comprise the step of normalizing the data elements in at least the first and third windows, prior to the identifying step.

Claim 8

Dependent Claim 31 words

The program storage device of claim 5, wherein each window contains ω data elements, and each window is represented as a data point in a hierarchical data tree having ω dimensions.

Claim 9

Dependent Claim 265 words

A computer program product for use with a computer system, a central processing unit and means coupled to the central processing unit for storing a database to identify similar time sequences which are stored in the database, comprising: a data storage device including a computer usable medium having computer readable program means for identifying whether a first time sequence in the database is similar to a second time sequence in the database, the computer usable code means having: computer readable code means for identifying first and third subsequence windows, each having a predetermined number of data elements and each being a subset of the first time sequence, to be respectively similar to second and fourth subsequence windows, each having the predetermined number of data elements and each being a subset of the second time sequence, when the difference between each data element of the first window and the corresponding data elements of the second window is no more than a predetermined value and the difference between each data element of the third window and the corresponding data elements of the fourth window is no more than the predetermined value; and computer readable code means for joining, when the first and third windows and second and fourth windows are separated by respective gaps, and each gap is less than a predetermined value, the first and third windows to establish a first subsequence representative of the first time sequence and the second and fourth windows to establish a second subsequence representative of the second time sequence for identifying whether the first and second time sequences are similar.

Claim 10

Dependent Claim 265 words

A computer program product for use with a computer system, a central processing unit and means coupled to the central processing unit for storing a database to identify similar time sequences which are stored in the database, comprising: a data storage device including a computer usable medium having computer readable program means for identifying whether a first time sequence in the database is similar to a second time sequence in the database, the computer usable code means having: computer readable code means for identifying first and third subsequence windows, each having a predetermined number of data elements and each being a subset of the first time sequence, to be respectively similar to second and fourth subsequence windows, each having the predetermined number of data elements and each being a subset of the second time sequence, when the difference between each data element of the first window and the corresponding data elements of the second window is no more than a predetermined value and the difference between each data element of the third window and the corresponding data elements of the fourth window is no more than the predetermined value; and computer readable code means for joining, when the first and third windows and second and fourth windows are separated by respective gaps, and each gap is less than a predetermined value, the first and third windows to establish a first subsequence representative of the first time sequence and the second and fourth windows to establish a second subsequence representative of the second time sequence for identifying whether the first and second time sequences are similar.

Claim 11

Dependent Claim 47 words

The program product of claim 8, further comprising computer readable code means for establishing the first and second subsequences when the first and third windows overlap each other by a first overlap distance and the second and fourth windows overlap each other by the first overlap distance.

Claim 12

Dependent Claim 61 words

The program product of claim 9, wherein each data element in each window is characterized by a corresponding time, and the code means establish the first and second subsequences only when the times of the earliest data elements in the third and fourth windows are later than the times of the earliest data elements in the first and second windows, respectively.

Claim 13

Dependent Claim 105 words

The program product of claim 10, further comprising: computer readable code means for establishing third and fourth subsequences respectively representative of the first and second time sequences, wherein the times of each data element in the third and fourth subsequences is later than the times of each data element in the first and second subsequences, respectively, such that the first and third subsequences are separated by a gap and the second and fourth subsequences are separated by a gap; and computer readable code means for joining the first and third subsequences and second and fourth subsequences when the gaps do not exceed a predetermined value.

Claim 14

Dependent Claim 85 words

The program product of claim 11, wherein each subsequence and the first and second time sequences are characterized by respective lengths, and the product further comprises: computer readable code means for comparing the sum of the lengths of the subsequences to at least one of the lengths of the time sequences to generate a comparison value; and computer readable code means for identifying the first and second time sequences as being similar when the comparison value is equal to or greater than a predetermined value.

Claim 15

Dependent Claim 30 words

The program product of claim 8, further comprising computer readable code means for normalizing the data elements in at least the first and third windows, prior to the identifying step.

Claim 16

Dependent Claim 29 words

The program product of claim 12, wherein each window contains ω data elements, and window is represented as a data point in a hierarchical data tree having ω dimensions.

Claim 17

Dependent Claim 252 words

A program storage device readable by a digital processing apparatus and tangibly embodying a program of instructions executable by the digital processing apparatus to perform method steps for identifying first and second time sequences stored in a database as being similar, the method steps comprising: (a) identifying first and third subsequence windows, each having a plurality of data elements, each data element being characterized by at least a time and a magnitude, each of the first and third windows being a subset of the first time sequence, to be respectively similar to second and fourth subsequence windows, each having a plurality of data elements and each being a subset of the second time sequence, when the difference between a magnitude of a data element of the first window and a magnitude of a data element of the second window is no more than a predetermined value and the difference between a magnitude of a data element of the third window and a magnitude of a data element of the fourth window is no more than the predetermined value; and (b) when the first and third windows and second and fourth windows are separated by respective time gaps, and each gap is less than a predetermined value, joining the first and third windows to establish a first subsequence representative of the first time sequence and joining the second and fourth windows to establish a second subsequence representative of the second time sequence for identifying whether the first and second time sequences are similar.

Claim 18

Dependent Claim 252 words

A program storage device readable by a digital processing apparatus and tangibly embodying a program of instructions executable by the digital processing apparatus to perform method steps for identifying first and second time sequences stored in a database as being similar, the method steps comprising: (a) identifying first and third subsequence windows, each having a plurality of data elements, each data element being characterized by at least a time and a magnitude, each of the first and third windows being a subset of the first time sequence, to be respectively similar to second and fourth subsequence windows, each having a plurality of data elements and each being a subset of the second time sequence, when the difference between a magnitude of a data element of the first window and a magnitude of a data element of the second window is no more than a predetermined value and the difference between a magnitude of a data element of the third window and a magnitude of a data element of the fourth window is no more than the predetermined value; and (b) when the first and third windows and second and fourth windows are separated by respective time gaps, and each gap is less than a predetermined value, joining the first and third windows to establish a first subsequence representative of the first time sequence and joining the second and fourth windows to establish a second subsequence representative of the second time sequence for identifying whether the first and second time sequences are similar.

Claim 19

Dependent Claim 52 words

The program storage device of claim 15, wherein the method steps further comprise the step of establishing the first and second subsequences when the first and third windows overlap each other in time by a first overlap distance and the second and fourth windows overlap each other by the first overlap distance.

Claim 20

Dependent Claim 164 words

The program storage device of claim 16, wherein each sub sequence and the first and second time sequences are characterized by respective lengths, and the method steps further comprise the steps of: establishing third and fourth subsequences respectively representative of the first and second time sequences, wherein the times of each data element in the third and fourth subsequences is later than the times of each data element in the first and second subsequences, respectively, such that the first and third subsequences are separated by a gap and the second and fourth subsequences are separated by a gap; joining the first and third subsequences and second and fourth subsequences when the gaps do not exceed a predetermined value; comparing the sum of the lengths of the subsequences to at least one of the lengths of the time sequences to generate a comparison value; and identifying the first and second time sequences as being similar when the comparison value at least equals a predetermined value.

Claim 21

Dependent Claim 35 words

The program storage device of claim 17, wherein the method steps further comprise the step of representing each window having ω data elements as a data point in a hierarchical data tree having ω dimensions.

Claim 22

Dependent Claim 240 words

A database mining system for discovering, for a first time sequence stored therein, a second time sequence that is similar to the first, comprising: a match determiner for generating first and second sets of subsequence windows respectively representing the first and second sequences, at least one window being characterized by a respective normalized value, the match determiner matching a test window in the first set of subsequence windows with a test window in the second set of subsequence windows when the difference between the values of the test windows is less than or equal to a predetermined difference, the match determiner designating as a pair of matched windows the test window from the first set of subsequence windows and the test window from the second set of subsequence windows; and a window stitcher for joining at least two pair of matched windows to establish a first subsequence and for joining at least two pair of matched windows to establish a second subsequence when (1) the two windows in the first subsequence do not overlap in time and are separated by a time gap and the two windows in the second subsequence do not overlap in time and are separated by a time gap, and the gaps are each less than a predetermined value, or (2) when the two windows in the first subsequence overlap each other the same amount as two corresponding windows in the second subsequence overlap each other.

Claim 23

Dependent Claim 240 words

A database mining system for discovering, for a first time sequence stored therein, a second time sequence that is similar to the first, comprising: a match determiner for generating first and second sets of subsequence windows respectively representing the first and second sequences, at least one window being characterized by a respective normalized value, the match determiner matching a test window in the first set of subsequence windows with a test window in the second set of subsequence windows when the difference between the values of the test windows is less than or equal to a predetermined difference, the match determiner designating as a pair of matched windows the test window from the first set of subsequence windows and the test window from the second set of subsequence windows; and a window stitcher for joining at least two pair of matched windows to establish a first subsequence and for joining at least two pair of matched windows to establish a second subsequence when (1) the two windows in the first subsequence do not overlap in time and are separated by a time gap and the two windows in the second subsequence do not overlap in time and are separated by a time gap, and the gaps are each less than a predetermined value, or (2) when the two windows in the first subsequence overlap each other the same amount as two corresponding windows in the second subsequence overlap each other.

Claim 24

Dependent Claim 65 words

The database mining system of claim 19, wherein the first and second subsequences are inserted into respective first and second subsequence sets, and the system further comprises: a similarity identifier for identifying the first time sequence as being similar to the second time sequence when the first and second subsequences bear a predetermined relationship to at least one of the first or second time sequences.

Claim 25

Dependent Claim 135 words

A computer-based system for discovering similarities between first and second time sequences, each having respective sets of first and second subsequence windows, each window including ω data points, each data point characterized by at least a time and a magnitude, the system comprising: a hierarchical database accessible by the computer for electronically storing the windows as corresponding points in ω-dimensional space; means for identifying one or more second windows as being similar to one or more corresponding first windows when the second window lies within a predetermined distance of the first window in the ω-dimensional space to thereby establish a pair of similar windows; and means for stitching pairs of first and second windows together when the windows satisfy one or more predetermined stitching criteria to identify similarities in the first and second time sequences.

Claim 26

Dependent Claim 135 words

A computer-based system for discovering similarities between first and second time sequences, each having respective sets of first and second subsequence windows, each window including ω data points, each data point characterized by at least a time and a magnitude, the system comprising: a hierarchical database accessible by the computer for electronically storing the windows as corresponding points in ω-dimensional space; means for identifying one or more second windows as being similar to one or more corresponding first windows when the second window lies within a predetermined distance of the first window in the ω-dimensional space to thereby establish a pair of similar windows; and means for stitching pairs of first and second windows together when the windows satisfy one or more predetermined stitching criteria to identify similarities in the first and second time sequences.

Claim 27

Dependent Claim 128 words

The system of claim 21, wherein the stitching criteria include (1) stitching first and second pairs of windows together when the first window in the first pair is separated by a gap from the first window in the second pair and the second window in the first pair is separated by a gap from the second window in the second pair and each gap is less than a predetermined value; and (2) stitching first and second pairs of windows together when the first window in the first pair overlaps, by a first distance, the first window in the second pair and the second window in the first pair overlaps, by a second distance, the second window in the second pair and the first distance equals the second distance.

Claim 28

Dependent Claim 76 words

The database mining system of claim 20, wherein the first set of subsequence windows includes first and third subsequence windows and the second set of subsequence windows includes second and fourth subsequence windows, and the system further comprises: means for establishing the first and second subsequences when the first and third windows overlap each other in time by a first overlap distance and the second and fourth windows overlap each other by the first overlap distance.

Claim 29

Dependent Claim 69 words

The database mining system of claim 23, wherein each window has a plurality of data elements, each data element being characterized by at least a time and a magnitude, and wherein the first and second subsequences are established only when times of the earliest data elements in the third and fourth windows are later than the times of the earliest data elements in the first and second windows, respectively.

Claim 30

Dependent Claim 100 words

The database mining system of claim 24, further comprising: means for establishing third and fourth subsequences respectively representative of the first and second time sequences, wherein the times of each data element in the third and fourth subsequences is later than the times of each data element in the first and second subsequences, respectively, such that the first and third subsequences are separated by a gap and the second and fourth subsequences are separated by a gap; and means for joining the first and third subsequences and second and fourth subsequences when the gaps do not exceed a predetermined value.

Claim 31

Dependent Claim 75 words

The database mining system of claim 25, wherein each subsequence and the first and second time sequences are characterized by respective lengths, and the system further comprises: means for comparing the sum of the lengths of the subsequences to at least one of the lengths of the time sequences to generate a comparison value; and means for identifying the first and second time sequences as being similar when the comparison value equals a predetermined value.

Claim 32

Dependent Claim 28 words

The database mining system of claim 26, further comprising means for normalizing the data elements in at least the first and third windows, prior to the identifying step.

Claim 33

Dependent Claim 31 words

The database mining system of claim 27, wherein each window contains ω data elements, and each window is represented as a data point in a hierarchical data tree having ω dimensions.

Claim 34

Dependent Claim 72 words

The computer-based system of claim 22, wherein the first window in the second pair is a third window and the second window in the second pair is a fourth window, and the system further comprises: means for establishing first and second subsequences when the first and third windows overlap each other in time by a first overlap distance and the second and fourth windows overlap each other by the first overlap distance.

Claim 35

Dependent Claim 45 words

The computer-based system of claim 29, wherein the first and second subsequences are established only when times of the earliest data elements in the third and fourth windows are later than the times of the earliest data elements in the first and second windows, respectively.

Claim 36

Dependent Claim 99 words

The computer-based system of claim 30, further comprising: means for establishing third and fourth subsequences respectively representative of the first and second time sequences, wherein the times of each data element in the third and fourth subsequences is later than the times of each data element in the first and second subsequences, respectively, such that the first and third subsequences are separated by a gap and the second and fourth subsequences are separated by a gap; and means for joining the first and third subsequences and second and fourth subsequences when the gaps do not exceed a predetermined value.

Claim 37

Dependent Claim 74 words

The computer-based system of claim 31, wherein each subsequence and the first and second time sequences are characterized by respective lengths, and the system further comprises: means for comparing the sum of the lengths of the subsequences to at least one of the lengths of the time sequences to generate a comparison value; and means for identifying the first and second time sequences as being similar when the comparison value equals a predetermined value.

Claim 38

Dependent Claim 27 words

The computer-based system of claim 32, further comprising means for normalizing the data elements in at least the first and third windows, prior to the identifying step.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2000-09-01	2001-03-03	2001-09-02	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2004-09-01	2005-03-03	2005-09-02	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2008-09-01	2009-03-03	2009-09-02	$7700.00	Window Closed / Lapsed

System and method for discovering similar time sequences in databases

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag