Querying Shapes of Histories.

Rakesh Agrawal, Giuseppe Psaila, Edward L. Wimmers, Mohamed Zaït: Querying Shapes of Histories. VLDB 1995: 502-514

@inproceedings{DBLP:conf/vldb/AgrawalPWZ95,
  author    = {Rakesh Agrawal and
               Giuseppe Psaila and
               Edward L. Wimmers and
               Mohamed Za\"{\i}t},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Querying Shapes of Histories},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {502-514},
  ee        = {db/conf/vldb/AgrawalPWZ95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a shape definition language, called SDL, for retrieving objects based on shapes contained in the histories associated with these objects. It is a small, yet powerful, language that allows a rich variety of queries about the shapes found in historical time sequences. An interesting feature of SDL is its ability to perform blurry matching. A "blurry" match is one where the user cares about the overall shape but does not care about specific details. Another important feature of SDL is its efficient implementability. The SDL operators are designed to be greedy to reduce non-determinism, which in turn substantially reduces the amount of back-tracking in theimplementation. We give transformation rules for rewriting an SDL expression into amore efficient form as well as an index structure for speeding up the execution of SDL queries.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents

References

[1]: ...
[2]: Donald J. Berndt, James Clifford: Using Dynamic Time Warping to Find Patterns in Time Series. KDD Workshop 1994: 359-370
[3]: Sharma Chakravarthy, V. Krishnaprasad, Eman Anwar, S.-K. Kim: Composite Events for Active Databases: Semantics, Contexts and Detection. VLDB 1994: 606-617
[4]: ...
[5]: Stella Gatziu, Klaus R. Dittrich: Detecting Composite Events in Active Database Systems Using Petri Nets. RIDE-ADS 1994: 2-9
[6]: Narain H. Gehani, H. V. Jagadish, Oded Shmueli: Composite Event Specification in Active Databases: Model & Implementation. VLDB 1992: 327-338
[7]: John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
[8]: Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: SEQ: A Model for Sequence Databases. ICDE 1995: 232-239
[9]: Sun Wu, Udi Manber: Fast Text Searching Allowing Errors. Commun. ACM 35(10): 83-91(1992)