 |
|
|
|
|
|
 Title: |
US5737593:
System and method for defining shapes with which to mine time sequences in computerized databases
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Psaila, Giuseppe; Dalmine, Italy
Wimmers, Edward L.; San Jose, CA
Zait, Mohamed; 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: |
1998-04-07
/ 1995-06-02
|
| Application Number: |
US1995000459018
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S4P8Q; G06F17/30S2P3; G06F17/30S4P8D;
|
| U.S. Class: |
Current:
707/006;
382/181;
382/187;
382/188;
382/189;
707/007;
Original:
395/606;
395/607;
382/181;
382/187;
382/188;
382/189;
|
| Field of Search: |
382/181,187,188,189
395/600,606,607
|
| Priority Number: |
| 1995-06-02 |
US1995000459018 |
|
| Abstract: |
A system and method including a computer shape definition language are disclosed for defining shapes and mining time sequences that resemble the shapes. The system and method include provisions for establishing a user-defined alphabet that in turn establishes a set of elemental shapes. The system also includes simple yet powerful operators for combining the elemental shapes to define a desired time sequence shape. Moreover, intervals of actual time sequences are mapped into corresponding transition sequences using the alphabet, and the transition sequences are stored in a hierarchical index structure for easily accessing the transition sequences. The index structure is entered with the desired time sequence shape, and the index structure is traversed to identify maximal actual transition sequences which conform to the desired time sequence shape, within user-definable blurry criteria.
|
| Attorney, Agent or Firm: |
Baker Maxham Jester & Meador ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Corrielus, Jean M.
|
| Maintenance Status: |
E2 Expired Check current status
CC Certificate of Correction issued
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 3 known family members
|
First Claim:
Show all 32 claims |
We claim:
1. 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 defining time sequence shape criteria and identifying electronically stored time sequences satisfying the shape criteria, the method steps comprising:
- (a) defining a set of elemental shapes;
- (b) defining a desired time sequence shape using the elemental shapes or combinations thereof;
- (c) mapping intervals of a time sequence to corresponding transition sequences, each transition sequence corresponding to one or more elemental shapes or combinations thereof that describe a respective interval of the time sequence;
- (d) identifying one or more transition sequences that match the desired time sequence shape; and
- (e) outputting parameter values representative of the one or more transition sequences that match the desired time sequence shape.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 4 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G98-239638
DERG98-239638
|
| Other References: |
S Chakravarthy et al. "Compsite events for active database: Semantics contexts and detection" database systems research and development center, p. 606-616, Jan. 1994.
Widom et al. "Detecting composite events in active database systems using Petri Nets" IEEE, pp. 1-9, Feb. 1994.
Berndt et al., "Using Dynamic time warping to find patterns in time series" workshop on knowlege discovering in database, pp. 359-369, Apr. 1994.
Agrawal et al. "Mining sequential patterns" University of Wisconsin, Madison, Jan. 1993.
Srikan et al. "Mining Sequential Patterns: Generalizations and Performance Improvement" University of Wisconsin, Madison, Jan. 1993.
Berndt, et al., "Using Dynamic Time warping to Find Patterns in Time Series", KOD-94: AAAI Workshop on Knowledge Discovery in Databases, pp. 359-370, Seattle, Washington, Jul. 1994.
N. H. Gehani, et al., "Composite Event Specification in Active Databases: Model & Implementation", Proceedings of the VLDB Conference, pp. 327-338, Vancouver, British Columbia, Canada, Aug. 1992.
Rakesh Agrawal, et al., "Database Mining: A Performance Perspevctive", IEEE Transactions on Knowledge and Data Engineering, 5(6):914-925, Dec. 1993.
(12 pages)
Cited by 35 patents
[ISI abstract]
Praveen Seshadri, et al., "SEQ: A framework for Sequence Databases", Computer Sciences department, pp. 1-24, University of Wisconsin- Macison, WI 52706, U.S.A., date unknown.
Praveen Seshadri, et al., "Sequence Query Processing", Computer Sciences Department, pp. 1-12, University of Wisconsin- Madison, WI 53706, date unknown.
Rakesh Agrawal, et al., "An Interval Classifier for Database Mining Applications", Proceddings of the 18th VLDB Conference, pp. 1-14, Vancouver, British Columbia, Canada, 1992.
Andrea Califano, et al., "FLASH: A Fast Look-up Algorithm for String Homology", Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, pp. 353-359, Bethesda, MD, Jul. 1983.
S. Chakravarthy, et al., "Composite Events for Active Databases: Semantics, Contexts, and Detection", Preceedings of the VLDS Conference, pp. 606-617, Santiago, Chile, Sep. 1994. (QA76.9D31559 1992).
J. T. Wang et al., "Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results", Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 115-125, Minneapolis, May 1994.
Sellis, et al., "The R+ Tree: A Dynamic Index for Multi-Dimensional Objects", 1987 Proceedings 13th International Conference on VLDB, pp. 507-518, England, 1987. (QA76.9.D3 1559).
S. Wu, et al., "Fast Text Searching", Communications of the ACM, pp. 83-91, vol. 35, No. 10, Oct. 1992.
(9 pages)
Cited by 13 patents
[ISI abstract]
Martin Vingron and Patrick Argos, "A Fast and Sensitive Multiple Sequence Alignment Algorithm", Computer Applications in the Biosciences, 5:115-122, 1989. (W1.C0528.BML 1st & 2nd Fl.).
(7 pages)
Cited by 4 patents
M.A. Roytberg, "A Search For Common Patterns in Many Sequences", Computer Applications in the Biosciences, 8(i):57-64, 1992.
(8 pages)
Cited by 6 patents
[ISI abstract]
S. Gatziu and K.R. Dittrich, "Detecting Composite Events in Active Databases Using Petri Nets", Proceedings of the 4th International Workshop on Research Issues in Data engineering: Active Database Systems, pp. 2-9, Feb. 1994. (QA76.9D3.1593 1993).
IBM Database 2 Application Programming Guide for Common Servers, Verson 2, pp. 275-304 (1995).
Montage User's Guide, pp. 8-1 through 8-5 (Mar. 1994).
|
|
 Nominate this for the Gallery...
|
|
