ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Similarity-Based Queries.

H. V. Jagadish, Alberto O. Mendelzon, Tova Milo: Similarity-Based Queries. PODS 1995: 36-45
@inproceedings{DBLP:conf/pods/JagadishMM95,
  author    = {H. V. Jagadish and
               Alberto O. Mendelzon and
               Tova Milo},
  title     = {Similarity-Based Queries},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {36-45},
  ee        = {http://doi.acm.org/10.1145/212433.212444, db/conf/pods/JagadishMM95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We develop a domain-independent framework for defining queries in terms of similarity of objects. Our framework has three components: a pattern language, a transformation rule language, and a query language. The pattern language specifies classes of objects, the transformation rule language defines similarity by specifying the similarity-preserving transformations, and the whole package is wrapped in a general query language. The framework can be "tuned" to the needs of a specific application domain, such as time sequences, molecules, text strings or images, by the choice of these languages.

We demonstrate the framework by presenting a specific instance on a specific domain - the domain of sequences. We start with sequences over a finite alphabet, and then consider sequences over infinite ordered domains. The basic pattern language we use is regular expressions, and the query language is calculus-based. We show that even when the pattern/query languages chosen are not too powerful, the approximation framework obtained is very strong. We study the properties of the framework, and in particular present expressive power and complexity results.

Copyright © 1995 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 Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 954 KB]

References

[AB87]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AFS93]
Rakesh Agrawal, Christos Faloutsos, Arun N. Swami: Efficient Similarity Search In Sequence Databases. FODO 1993: 69-84 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AGMML90]
...
[BM92]
Catriel Beeri, Tova Milo: Functional and Predicative Programming in OODB's. PODS 1992: 176-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CRSV94]
Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FRM94]
Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos: Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994: 419-429 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GCB92]
...
[GM95]
Stéphane Grumbach, Tova Milo: An Algebra for Pomsets. ICDT 1995: 191-207 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GNU94]
Gösta Grahne, Matti Nykänen, Esko Ukkonen: Reasoning about Strings in Databases. PODS 1994: 303-312 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GW92]
Seymour Ginsburg, Xiaoyang Sean Wang: Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data. PODS 1992: 293-300 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[J91]
H. V. Jagadish: A Retrieval Technique for Similar Shapes. SIGMOD Conference 1991: 208-217 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ric92]
Joel E. Richardson: Supporting Lists in a Data Model (A Timely Approach). VLDB 1992: 127-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SLR94]
Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[U88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:57 2010 by Michael Ley (ley@uni-trier.de)