Fast Parallel Similarity Search in Multimedia Databases.
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@inproceedings{DBLP:conf/sigmod/BerchtoldBBKK97,
author = {Stefan Berchtold and
Christian B{\"o}hm and
Bernhard Braunm{\"u}ller and
Daniel A. Keim and
Hans-Peter Kriegel},
editor = {Joan Peckham},
title = {Fast Parallel Similarity Search in Multimedia Databases},
booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
publisher = {ACM Press},
year = {1997},
pages = {1-12},
ee = {http://doi.acm.org/10.1145/253260.253263, db/conf/sigmod/BerchtoldBBKK97.html},
crossref = {DBLP:conf/sigmod/97},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Most similarity search techniques map the data objects into some
high-dimensional feature space. The similarity search then corresponds
to a nearest-neighbor search in the feature space which is
computationally very intensive. In this paper, we present a new parallel
method for fast nearest-neighbor search in high-dimensional
feature spaces. The core problem of designing a parallel nearest-neighbor
algorithm is to find an adequate distribution of the data
onto the disks. Unfortunately, the known declustering methods do
not perform well for high-dimensional nearest-neighbor search. In
contrast, our method has been optimized based on the special properties
of high-dimensional spaces and therefore provides a near-optimal
distribution of the data items among the disks. The basic idea
of our data declustering technique is to assign the buckets corresponding
to different quadrants of the data space to different disks.
We show that our technique - in contrast to other declustering methods
- guarantees that all buckets corresponding to neighboring
quadrants are assigned to different disks. We evaluate our method
using large amounts of real data (up to 40 MBytes) and compare it
with the best known data declustering method, the Hilbert curve.
Our experiments show that our method provides an almost linear
speed-up and a constant scale-up. Additionally, it outperforms
the Hilbert approach by a factor of up to 5.
Copyright © 1997 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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Joan Peckham (Ed.):
SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA.
ACM Press 1997 BibTeX
,
SIGMOD Record 26(2),
June 1997
Contents
[Index Terms]
[Full Text in PDF Format, 1269 KB]
References
- [AGMM90]
- ...
- [Ary95]
- ...
- [Big89]
- ...
- [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
- [BKK96]
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39 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
- [DS82]
- David Hung-Chang Du, J. S. Sobolewski:
Disk Allocation for Cartesian Product Files on Multiple-Disk Systems.
ACM Trans. Database Syst. 7(1): 82-101(1982) BibTeX
- [Fal94]
- 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
- [FB93]
- Christos Faloutsos, Pravin Bhagwat:
Declustering Using Fractals.
PDIS 1993: 18-25 BibTeX
- [FBF77]
- ...
- [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
- [Kuk92]
- Karen Kukich:
Techniques for Automatically Correcting Words in Text.
ACM Comput. Surv. 24(4): 377-439(1992) BibTeX
- [KP88]
- Myoung-Ho Kim, Sakti Pramanik:
Optimal File Distribution For Partial Match Retrieval.
SIGMOD Conference 1988: 173-182 BibTeX
- [LJF94]
- King-Ip Lin, H. V. Jagadish, Christos Faloutsos:
The TV-Tree: An Index Structure for High-Dimensional Data.
VLDB J. 3(4): 517-542(1994) BibTeX
- [MG93]
- Rajiv Mehrotra, James E. Gary:
Feature-Based Retrieval of Similar Shapes.
ICDE 1993: 108-115 BibTeX
- [MG95]
- Rajiv Mehrotra, James E. Gary:
Feature-Index-Based Similar Shape Retrieval.
VDB 1995: 46-65 BibTeX
- [PS85]
- ...
- [RKV95]
- Nick Roussopoulos, Stephen Kelley, Frédéic Vincent:
Nearest Neighbor Queries.
SIGMOD Conference 1995: 71-79 BibTeX
- [RP92]
- ...
- [SBK92]
- ...
- [SH94]
- ...
- [Wel71]
- ...
- [WW80]
- ...
Referenced by
- Rakesh K. Sinha, Randeep Bhatia, Chung-Min Chen:
Asymptotically Optimal Declustering Schemes for Range Queries.
ICDT 2001: 144-158
- Stefan Berchtold, Christian Böhm, Daniel A. Keim, Florian Krebs, Hans-Peter Kriegel:
On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces.
ICDT 2001: 435-449
- Mikhail J. Atallah, Sunil Prabhakar:
(Almost) Optimal Parallel Block Access for Range Queries.
PODS 2000: 205-215
- Roger Weber, Klemens Böhm:
Trading Quality for Time with Nearest Neighbor Search.
EDBT 2000: 21-35
- Kevin S. Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft:
When Is ''Nearest Neighbor'' Meaningful?
ICDT 1999: 217-235
- Hakan Ferhatosmanoglu, Divyakant Agrawal, Amr El Abbadi:
Concentric Hyperspaces and Disk Allocation for Fast Parallel Range Searching.
ICDE 1999: 608-615
- 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)
- King Lum Cheung, Ada Wai-Chee Fu:
Enhanced Nearest Neighbour Search on the R-tree.
SIGMOD Record 27(3): 16-21(1998)
- Roger Weber, Hans-Jörg Schek, Stephen Blott:
A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces.
VLDB 1998: 194-205
- 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
- Apostolos Papadopoulos, Yannis Manolopoulos:
Similarity Query Processing Using Disk Arrays.
SIGMOD Conference 1998: 225-236
- Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel:
The Pyramid-Technique: Towards Breaking the Curse of Dimensionality.
SIGMOD Conference 1998: 142-153
- Stefan Berchtold, Bernhard Ertl, Daniel A. Keim, Hans-Peter Kriegel, Thomas Seidl:
Fast Nearest Neighbor Search in High-Dimensional Space.
ICDE 1998: 209-218
- 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
- Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515
- Stefan Berchtold, Hans-Peter Kriegel:
S3: Similarity Search in CAD Database Systems.
SIGMOD Conference 1997: 564-567
- David A. White, Ramesh Jain:
Similarity Indexing with the SS-tree.
ICDE 1996: 516-523
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
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:40:35 2009