|
|
|
@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}
}
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.
