Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515@inproceedings{DBLP:conf/vldb/SeidlK97,
author = {Thomas Seidl and
Hans-Peter Kriegel},
editor = {Matthias Jarke and
Michael J. Carey and
Klaus R. Dittrich and
Frederick H. Lochovsky and
Pericles Loucopoulos and
Manfred A. Jeusfeld},
title = {Efficient User-Adaptable Similarity Search in Large Multimedia
Databases},
booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
Large Data Bases, August 25-29, 1997, Athens, Greece},
publisher = {Morgan Kaufmann},
year = {1997},
isbn = {1-55860-470-7},
pages = {506-515},
ee = {db/conf/vldb/SeidlK97.html},
crossref = {DBLP:conf/vldb/97},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Efficient user-adaptable similarity search more and more increases in
its importance for multimedia and spatial database systems. As a
general similarity model for multi-dimensional vectors that is
adaptable to application requirements and user preferences, we use
quadratic form distance functions dA^2(x,y)=(x-y)*A*(x-y)^T which have
been successfully applied to color histograms in image databases
[Faloutsos et al. 1994]. The components aij of the matrix A denote
similarity of the components i and j of the vectors. Beyond the
Euclidean distance which produces spherical query ranges, the
similarity distance defines a new query type, the ellipsoid query. We
present new algorithms to efficiently support ellipsoid query
processing for various user-defined similarity matrices on existing
precomputed indexes. By adapting techniques for reducing the
dimensionality and employing a multi-step query processing
architecture, the method is extended to high-dimensional data spaces.
In particular, from our algorithm to reduce the similarity matrix, we
obtain the greatest lower-bounding similarity function thus
guaranteeing no false drops. We implemented our algorithms in C++ and
tested them on an image database containing 12,000 color
histograms. The experiments demonstrate the flexibility of our
method in conjunction with a high selectivity and efficiency.
Copyright © 1997 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
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.):
VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece.
Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents BibTeX
Electronic Edition
From CS Dept.,
University Trier (Germany)
References
- [AFS93]
- Rakesh Agrawal, Christos Faloutsos, Arun N. Swami:
Efficient Similarity Search In Sequence Databases.
FODO 1993: 69-84 BibTeX
- [ALSS95]
- Rakesh Agrawal, King-Ip Lin, Harpreet S. Sawhney, Kyuseok Shim:
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases.
VLDB 1995: 490-501 BibTeX
- [BBKK97]
- Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel:
A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space.
PODS 1997: 78-86 BibTeX
- [Ber+97]
- Stefan Berchtold, Christian Böhm, Bernhard Braunmüller, Daniel A. Keim, Hans-Peter Kriegel:
Fast Parallel Similarity Search in Multimedia Databases.
SIGMOD Conference 1997: 1-12 BibTeX
- [BHKS93]
- Thomas Brinkhoff, Holger Horn, Hans-Peter Kriegel, Ralf Schneider:
A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems.
SSD 1993: 357-376 BibTeX
- [BKK96]
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39 BibTeX
- [BKK97]
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
Using Extended Feature Objects for Partial Similarity Retrieval.
VLDB J. 6(4): 333-348(1997) BibTeX
- [BK97]
- Stefan Berchtold, Hans-Peter Kriegel:
S3: Similarity Search in CAD Database Systems.
SIGMOD Conference 1997: 564-567 BibTeX
- [BKSS90]
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331 BibTeX
- [BKSS94]
- Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
Multi-Step Processing of Spatial Joins.
SIGMOD Conference 1994: 197-208 BibTeX
- [BR85]
- Michael J. Best, Klaus Ritter:
Linear Programming: Active Set Analysis and Computer Programs.
Prentice-Hall 1985, ISBN 0-13-536996-7
BibTeX
- [Fal+94]
- Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz:
Efficient and Effective Querying by Image Content.
J. Intell. Inf. Syst. 3(3/4): 231-262(1994) BibTeX
- [FRM94]
- Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos:
Fast Subsequence Matching in Time-Series Databases.
SIGMOD Conference 1994: 419-429 BibTeX
- [GM93]
- James E. Gary, Rajiv Mehrotra:
Similar shape retrieval using a structural feature index.
Inf. Syst. 18(7): 525-537(1993) BibTeX
- [Gut84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [Haf+95]
- James L. Hafner, Harpreet S. Sawhney, William Equitz, Myron Flickner, Wayne Niblack:
Efficient Color Histogram Indexing for Quadratic Form Distance Functions.
IEEE Trans. Pattern Anal. Mach. Intell. 17(7): 729-736(1995) BibTeX
- [HS95]
- Gísli R. Hjaltason, Hanan Samet:
Ranking in Spatial Databases.
SSD 1995: 83-95 BibTeX
- [Jag91]
- H. V. Jagadish:
A Retrieval Technique for Similar Shapes.
SIGMOD Conference 1991: 208-217 BibTeX
- [Kor+96]
- Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas:
Fast Nearest Neighbor Search in Medical Image Databases.
VLDB 1996: 215-226 BibTeX
- [OM88]
- Jack A. Orenstein, Frank Manola:
PROBE Spatial Data Modeling and Query Processing in an Image Database Application.
IEEE Trans. Software Eng. 14(5): 611-629(1988) BibTeX
- [PTVF92]
- William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery:
Numerical Recipes in C, 2nd Edition.
Cambridge University Press 1992
Contents BibTeX
- [RKV95]
- Nick Roussopoulos, Stephen Kelley, Frédéic Vincent:
Nearest Neighbor Queries.
SIGMOD Conference 1995: 71-79 BibTeX
- [SRF87]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518 BibTeX
Referenced by
- Christian Böhm, Hans-Peter Kriegel:
Dynamically Optimizing High-Dimensional Index Structures.
EDBT 2000: 36-50
- Charu C. Aggarwal, Joel L. Wolf, Philip S. Yu:
A New Method for Similarity Indexing of Market Basket Data.
SIGMOD Conference 1999: 407-418
- Pavel Zezula, Pasquale Savino, Giuseppe Amato, Fausto Rabitti:
Approximate Similarity Retrieval with M-Trees.
VLDB J. 7(4): 275-293(1998)
- Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas:
Fast and Effective Retrieval of Medical Tumor Shapes.
IEEE Trans. Knowl. Data Eng. 10(6): 889-904(1998)
- Mihael Ankerst, Hans-Peter Kriegel, Thomas Seidl:
A Multistep Approach for Shape Similarity Search in Image Databases.
IEEE Trans. Knowl. Data Eng. 10(6): 996-1004(1998)
- Yoshiharu Ishikawa, Ravishankar Subramanya, Christos Faloutsos:
MindReader: Querying Databases Through Multiple Examples.
VLDB 1998: 218-227
- Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl:
Improving Adaptable Similarity Query Processing by Using Approximations.
VLDB 1998: 206-217
- Thomas Seidl, Hans-Peter Kriegel:
Optimal Multi-Step k-Nearest Neighbor Search.
SIGMOD Conference 1998: 154-165
- Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel:
The Pyramid-Technique: Towards Breaking the Curse of Dimensionality.
SIGMOD Conference 1998: 142-153
- Paolo Ciaccia, Marco Patella, Pavel Zezula:
Processing Complex Similarity Queries with Distance-Based Access Methods.
EDBT 1998: 9-23
- Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel:
Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations.
EDBT 1998: 216-230
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:18 2009
