 |
|
|
Improving Adaptable Similarity Query Processing by Using Approximations |
Full Paper (PDF)
|
Similarity search and content-based retrieval are becoming more and more important for an increasing number of applications including multimedia, medical imaging, 3D molecular and CAD database systems.
As a general similarity model that is particularly adaptable to user preferences and, therefore, fits the subjective character of similarity, quadratic form distance functions have been successfully employed, e.g. for color histograms as well as for 2D and 3D shape histograms.
Although efficient algorithms for processing adaptable similarity queries using multidimensional index structures are available, the quadratic nature of the distance function strongly affects the CPU time which in turn represents a high percentage of the overall runtime.
The basic idea of our approach is to reduce the number of exact distance computations by adapting conservative approximation techniques to similarity range query processing and, in addition, to extend the concepts to k-nearest neighbor search.
As part of a detailed analysis, we show that our methods guarantee no false drops.
Experiments on synthetic data as well as on a large image database containing 112,000 color images demonstrate a significant performance gain, and the CPU time is improved by a factor of up to 6.
|
References, where available, link to the DBLP on the World Wide Web.
[AFS93]Rakesh Agrawal, Christos Faloutsos, Arun N. Swami:
Efficient Similarity Search In Sequence Databases.
FODO 1993: 69-84[AKS98]...
[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[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[Ber+97]Stefan Berchtold, Christian Böhm, Bernhard Braunmüller, Daniel A. Keim, Hans-Peter Kriegel:
Fast Similarity Search in Multimedia Databases.
SIGMOD Conference 1997: 1-12[BKK96]Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39[BK94]Thomas Brinkhoff, Hans-Peter Kriegel:
Approximations for a Multi-Step Processing of Spatial Joins.
IGIS 1994: 25-34[BK97]Stefan Berchtold, Hans-Peter Kriegel:
S3: Similarity Search in CAD Database Systems.
SIGMOD Conference 1997: 564-567[BKS93]Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider:
Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems.
ICDE 1993: 40-49[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[Bri94]...
[Fal+94]Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz:
Efficient and Effective Querying by Image Content.
JIIS 3(3/4): 231-262(1994)[FRM94]Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos:
Fast Subsequence Matching in Time-Series Databases.
SIGMOD Conference 1994: 419-429[GG97]Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
Computing Surveys 30(2): 170-231(1998)[GM93]James E. Gary, Rajiv Mehrotra:
Similar shape retrieval using a structural feature index.
IS 18(7): 525-537(1993)[Gut84]Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57[Haf+95]James L. Hafner, Harpreet S. Sawhney, William Equitz, Myron Flickner, Wayne Niblack:
Efficient Color Histogram Indexing for Quadratic Form Distance Functions.
TPAMI 17(7): 729-736(1995)[Hen94]...
[HS95]Gisli R. Hjaltason, Hanan Samet:
Ranking in Spatial Databases.
SSD 1995: 83-95[Jag91]H. V. Jagadish:
A Retrieval Technique for Similar Shapes.
SIGMOD Conference 1991: 208-217[Kor+96]Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas:
Fast Nearest Neighbor Search in Medical Image Databases.
VLDB 1996: 215-226[KS98]...
[KSB93]...
[KSS97]Hans-Peter Kriegel, Thomas Schmidt, Thomas Seidl:
3D Similarity Search by Shape Approximation.
SSD 1997: 11-28[PTVF92]William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery:
Numerical Recipes in C, 2nd Edition.
Cambridge University Press 1992
Contents[RKV95]Nick Roussopoulos, Stephen Kelley, Frédéic Vincent:
Nearest Neighbor Queries.
SIGMOD Conference 1995: 71-79[Sei90]...
[Sei97]...
[SK97]Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515[SK98]Thomas Seidl, Hans-Peter Kriegel:
Optimal Multi-Step k-Nearest Neighbor Search.
SIGMOD Conference 1998: 154-165[SRF87]Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518
|
@inproceedings{DBLP:conf/vldb/AnkerstBKS98,
author = {Mihael Ankerst and
Bernhard Braunm{\"u}ller and
Hans-Peter Kriegel and
Thomas Seidl},
editor = {Ashish Gupta and
Oded Shmueli and
Jennifer Widom},
title = {Improving Adaptable Similarity Query Processing by Using Approximations},
booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
Large Data Bases, August 24-27, 1998, New York City, New York,
USA},
publisher = {Morgan Kaufmann},
year = {1998},
isbn = {1-55860-566-5},
pages = {206-217},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
