Testing Complex Temporal Relationships Involving Multiple Granularities and Its Application to Data Mining.
Claudio Bettini, Xiaoyang Sean Wang, Sushil Jajodia:
Testing Complex Temporal Relationships Involving Multiple Granularities and Its Application to Data Mining.
PODS 1996: 68-78@inproceedings{DBLP:conf/pods/BettiniWJ96,
author = {Claudio Bettini and
Xiaoyang Sean Wang and
Sushil Jajodia},
title = {Testing Complex Temporal Relationships Involving Multiple Granularities
and Its Application to Data Mining},
booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 3-5, 1996, Montreal,
Canada},
publisher = {ACM Press},
year = {1996},
isbn = {0-89791-781-2},
pages = {68-78},
ee = {http://doi.acm.org/10.1145/237661.237680, db/conf/pods/BettiniWJ96.html},
crossref = {DBLP:conf/pods/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
An important usage of time sequences is for discovering temporal patterns
of events (a special type of data mining).
This process usually starts with the specification by the user of an
event structure which consists of a number of variables
representing events and temporal constraints among these variables.
The goal of the data mining is to find temporal patterns, i.e.,
instantiations of the variables in the structure, which frequently appear in
the time sequence.
This paper introduces event structures that have temporal constraints with
multiple granularities (TCGs). Testing the consistency of such structures
is shown to be NP-hard. An approximate algorithm in then presented.
The paper also introduces the concept of a timed automaton with
granularities (TAGs) that can be used to find in a time sequence occurences
of a particular TCG with instantiated variables.
The TCGs, the approximate algorithm and the TAGs are shown to be useful
for obtaining effective data mining procedures.
Copyright © 1996 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
Printed Edition
Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada.
ACM Press 1996, ISBN 0-89791-781-2
Contents 
[Index Terms]
[Full Text in PDF Format, 1264 KB]
References
- [AD94]
- Rajeev Alur, David L. Dill:
A Theory of Timed Automata.
Theor. Comput. Sci. 126(2): 183-235(1994)
- [AHU74]
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
The Design and Analysis of Computer Algorithms.
Addison-Wesley 1974, ISBN 0-201-00029-6
- [AIS90]
- Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami:
Database Mining: A Performance Perspective.
IEEE Trans. Knowl. Data Eng. 5(6): 914-925(1993)
- [BWJ95]
- ...
- [CSS94]
- Rakesh Chandra, Arie Segev, Michael Stonebraker:
Implementing Calendars and Temporal Rules in Next Generation Databases.
ICDE 1994: 264-273
- [DMP91]
- Rina Dechter, Itay Meiri, Judea Pearl:
Temporal Constraint Networks.
Artif. Intell. 49(1-3): 61-95(1991)
- [GJ79]
- M. R. Garey, David S. Johnson:
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman 1979, ISBN 0-7167-1044-7
- [Lai93]
- ...
- [LMF86]
- Bruce Leban, David McDonald, David Forster:
A Representation for Collections of Temporal Intervals.
AAAI 1986: 367-371
- [MTV95]
- Heikki Mannila, Hannu Toivonen, A. Inkeri Verkamo:
Discovering Frequent Episodes in Sequences.
KDD 1995: 210-215
- [NS92]
- ...
- [Soo93]
- ...
- [WBBJ]
- Xiaoyang Sean Wang, Claudio Bettini, Alexander Brodsky, Sushil Jajodia:
Logical Design for Temporal Databases with Multiple Granularities.
ACM Trans. Database Syst. 22(2): 115-170(1997)
Copyright © Sun Mar 14 23:21:18 2010
by Michael Ley (ley@uni-trier.de)
