A Multi-Similarity Algebra
Sibel Adali, Piero A. Bonatti, Maria Luisa Sapino, V. S. Subrahmanian
Full Paper (PDF)

Slides (HTML)

Abstract
The need to automatically extract and classify the contents of multimedia data archives such as images, video, and text documents has led to significant work on similarity based retrieval of data. To date, most work in this area has focused on the creation of index structures for similarity based retrieval. There is very little work on developing formalisms for querying multimedia databases that support similarity based computations and optimizing such queries, even though it is well known that feature extraction and identification algorithms in media data are very expensive. We introduce a similarity algebra that brings together relational operators and results of multiple similarity implementations in a uniform language. The algebra can be used to specify complex queries that combine different interpretations of similarity values and multiple algorithms for computing these values. We prove equivalence and containment relationships between similarity algebra expressions and develop query rewriting methods based on these results. We then provide a generic cost model for evaluating cost of query plans in the similarity algebra and query optimization methods based on this model. We supplement the paper with experimental results that illustrate the use of the algebra and the effectiveness of query optimization methods using the Integrated Search Engine (I.SEE) as the testbed.

References

References, where available, link to the DBLP on the World Wide Web.

[1]
...
[2]
Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conf. 1996: 137-148
[3]
...
[4]
Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39
[5]
...
[6]
Eric W. Brown, James P. Callan, W. Bruce Croft: Fast Incremental Indexing for Full-Text Information Retrieval. VLDB 1994: 192-202
[7]
Michael J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference 1997: 219-230
[8]
Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. SIGMOD Conf. 1996: 91-102
[9]
...
[10]
Luis Gravano, Chen-Chuan K. Chang, Hector Garcia-Molina, Andreas Paepcke: STARTS: Stanford Proposal for Internet Meta-Searching (Experience Paper). SIGMOD Conference 1997: 207-218
[11]
Venkat N. Gudivada, Vijay V. Raghavan: Design and Evaluation of Algorithms for Image Retrieval by Spatial Similarity. TOIS 13(2): 115-144(1995)
[12]
H. V. Jagadish, Alberto O. Mendelzon, Tova Milo: Similarity-Based Queries. PODS 1995: 36-45
[13]
King-Ip Lin, H. V. Jagadish, Christos Faloutsos: The TV-Tree: An Index Structure for High-Dimensional Data. VLDB Journal 3(4): 517-542(1994)
[14]
...
[15]
...
[16]
Xiaolei Qian: Query Folding. ICDE 1996: 48-55
[17]
Anthony Tomasic, Hector Garcia-Molina, Kurt A. Shoens: Incremental Updates of Inverted Lists for Text Document Retrieval. SIGMOD Conference 1994: 289-300
BIBTEX

@inproceedings{DBLP:conf/sigmod/AdaliBSS98,
author = {Sibel Adali and
Piero A. Bonatti and
Maria Luisa Sapino and
V. S. Subrahmanian},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {A Multi-Similarity Algebra},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {402-413},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).