ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Improving Adaptable Similarity Query Processing by Using Approximations.

Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl: Improving Adaptable Similarity Query Processing by Using Approximations. VLDB 1998: 206-217
@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},
  ee        = {db/conf/vldb/AnkerstBKS98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

Copyright © 1998 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

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKK96]
Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BK94]
Thomas Brinkhoff, Hans-Peter Kriegel: Approximations for a Multi-Step Processing of Spatial Joins. IGIS 1994: 25-34 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BK97]
Stefan Berchtold, Hans-Peter Kriegel: S3: Similarity Search in CAD Database Systems. SIGMOD Conference 1997: 564-567 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bri94]
...
[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) 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
[GG97]
Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GM93]
James E. Gary, Rajiv Mehrotra: Similar shape retrieval using a structural feature index. Inf. Syst. 18(7): 525-537(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hen94]
...
[HS95]
Gísli R. Hjaltason, Hanan Samet: Ranking in Spatial Databases. SSD 1995: 83-95 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jag91]
H. V. Jagadish: A Retrieval Technique for Similar Shapes. SIGMOD Conference 1991: 208-217 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kor+96]
Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996: 215-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS98]
...
[KSB93]
...
[KSS97]
Hans-Peter Kriegel, Thomas Schmidt, Thomas Seidl: 3D Similarity Search by Shape Approximation. SSD 1997: 11-28 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PTVF92]
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery: Numerical Recipes in C, 2nd Edition. Cambridge University Press 1992
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RKV95]
Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sei90]
...
[Sei97]
...
[SK97]
Thomas Seidl, Hans-Peter Kriegel: Efficient User-Adaptable Similarity Search in Large Multimedia Databases. VLDB 1997: 506-515 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SK98]
Thomas Seidl, Hans-Peter Kriegel: Optimal Multi-Step k-Nearest Neighbor Search. SIGMOD Conference 1998: 154-165 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:07 2010 by Michael Ley (ley@uni-trier.de)