 |
|
|
|
|
|
 Title: |
US5878413:
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; Campbell, 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-03-02
/ 1997-10-08
|
| Application Number: |
US1997000947227
|
| 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;
708/607;
Original:
707/006;
382/181;
382/187;
382/188;
382/189;
707/006;
707/007;
|
| Field of Search: |
707/006,516,7
382/181,187,188,189
704/002
|
| Priority Number: |
|
| 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: |
Gray Cary Ware Freidenrich ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Corrielus, Jean M.
|
| INPADOC Legal Status: |
None
Family Legal Status Report
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
Berndt, et al., "Using Dynamic Time warping to Find Patterns in Time Series", KDD-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 Perspective", 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-Madison, WI 52706, U.S.A., no date.
Praveen Seshadri, et al., "Sequence Query Processing", Computer Sciences Department, pp. 1-12, University of Wisconsin-Madison, WI 53706, U.S.A., no date.
Rakesh Agrawal, et al., "An Interval Classifier for Database Mining Applications", Proceedings 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. 1993.
S. Chakravarthy, et al., "Composite Events for Active Databases: Semantics, Contexts, and Detection", Preceedings of the VLDB Conference, pp. 606-617, Santiago, Chile, Sep. 1994. (QA76.9D3.I559 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 I559).
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.I593 1993).
IBM Database 2 Application Programming Guide for Common Servers, Version 2, pp. 275-304 (1995).
Montage User's Guide, pp. 8-1 through 8-5 (Mar. 1994).
|
|
 Nominate this for the Gallery...
|
|
