 |
|
|
|
|
|
 Title: |
US5930789:
System and method for discovering similar time sequences in databases
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Lin, King-Ip; College Park, MD
Sawhney, Harpreet Singh; Plainsboro, NJ
Shim, Kyuseok; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1999-07-27
/ 1997-08-28
|
| Application Number: |
US1997000920031
|
| IPC Code: |
Advanced:
G06F 12/00;
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S4P8Q; G06F17/30S4P8T;
|
| U.S. Class: |
Current:
707/006;
707/001;
707/003;
Original:
707/006;
707/003;
707/001;
|
| Field of Search: |
707/006,3,7,1
|
| Priority Number: |
|
| Abstract: |
A system and method for discovering similar time sequences in a database of time sequences includes a computer-implemented program which first breaks each sequence into small windows. The windows from the first sequence are compared to selected windows from the second sequence to determine which windows are similar. Pairs of similar windows are then stitched together when certain stitching constraints are met to establish pairs of similar subsequences. Likewise, pairs of similar subsequences are stitched together, and the lengths of the stitched subsequences are then compared to the overall length of the time sequences to determine whether the time sequences meet a similarity criteria.
|
| Attorney, Agent or Firm: |
Gray Cary Ware Freidenrich ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Robinson, Greta L.
|
| INPADOC Legal Status: |
None
Family Legal Status Report
|
|
|
|
|
|
|
| Parent Case: |
This application is a continuation of application Ser. No. 08/437,746, filed May 9, 1995, now U.S. Pat. No. 5,664,174.
|
| Designated Country: |
DE FR GB
|
| Family: |
Show 9 known family members
|
First Claim:
Show all 3 claims |
We claim:
1. A computer system for identifying recurring patterns in data elements stored in a database, comprising:
- a computer;
- first means in the computer for identifying at least a first and a second time sequence in data elements stored in a database, each data element being characterized by at least a time and a magnitude;
- second means in the computer for identifying at least first and third subsequence windows, each having a plurality of the data elements, 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 the 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
- third means for 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, when the first and third windows and the second and fourth windows are separated by respective time gaps and each gap is less than a predetermined value.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 13 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
R. Agrawal et al., "Database Mining: A Performance Perspective", Proc. 4th Int'l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, 1993.
R. Agrawal et al., "Efficient Similarity Search in Sequence Databases", Proceeding of the Fourth Int'l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, Oct. 1993.
A. Califano, et al., "Multidimensional Indexing for Recognizing Visual Shapes", IEEE Trans. on Pattern Analysis and Machine Intelligence, 16(4):373-392, 1994.
(20 pages)
Cited by 10 patents
[ISI abstract]
C. Faloutsos et al., "Fast Sequence Matching in Time-Series Databases", Proc. ACM Sigmod Conf. on Mangement of Data, May, 1994.
W.E.L. Grimson et al., "On the Sensitivity of Geometric Hashing", Proc. 3rd Int'l Conf. on Computer Vision, pp. 334-338, 1990.
Y. Lamdan et al., "Geometric Hashing: A general and Efficient Model-Based Recognition Scheme", Proc. 2nd Int'l Conf. on Computer Vision, pp. 238-249, 1988.
T. Sellis et al., "The R+-- Tree: A Dynamic Index for Multi-Dimensional Objects", Proc. 13th Int'l. Conf. on VLDB, pp. 507-518, England, 1987.
"Mining Sequential Patterns", Rakesh Agrawal & Ramakrishnan Srikant, IEEE Comput. Soc. Press, 1063-6382, pp. 3-14, Mar. 1995.
"Set-Oriented Mining For Association Rules In Relational Databases", Maurice Houtsma & Arun Swami, IEEE Comput. Soc. Press, 1063-6382, pp. 25-33, Mar. 1995.
|
|
 Nominate this for the Gallery...
|
|
