Fast Parallel Similarity Search in Multimedia Databases

Thumbnail Image
Date
1997
Authors
Berchtold, Stefan
Böhm, Christian
Braunmüller, Bernhard
Kriegel, Hans-Peter
Editors
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
DOI (citable link)
ArXiv-ID
International patent number
EU project number
Project
Open Access publication
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
Publication type
Contribution to a conference collection
Publication status
Published in
Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97. - New York, New York, USA : ACM Press, 1997. - pp. 1-12. - ISBN 0-89791-911-4
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 nearestneighbor 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.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
Conference
the 1997 ACM SIGMOD international conference, May 11, 1997 - May 15, 1997, Tucson, Arizona, United States
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690BERCHTOLD, Stefan, Christian BÖHM, Bernhard BRAUNMÜLLER, Daniel A. KEIM, Hans-Peter KRIEGEL, 1997. Fast Parallel Similarity Search in Multimedia Databases. the 1997 ACM SIGMOD international conference. Tucson, Arizona, United States, May 11, 1997 - May 15, 1997. In: Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97. New York, New York, USA:ACM Press, pp. 1-12. ISBN 0-89791-911-4. Available under: doi: 10.1145/253260.253263
BibTex
@inproceedings{Berchtold1997Paral-5776,
  year={1997},
  doi={10.1145/253260.253263},
  title={Fast Parallel Similarity Search in Multimedia Databases},
  isbn={0-89791-911-4},
  publisher={ACM Press},
  address={New York, New York, USA},
  booktitle={Proceedings of the 1997 ACM SIGMOD international conference on Management of data  - SIGMOD '97},
  pages={1--12},
  author={Berchtold, Stefan and Böhm, Christian and Braunmüller, Bernhard and Keim, Daniel A. and Kriegel, Hans-Peter}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/5776">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Keim, Daniel A.</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Braunmüller, Bernhard</dc:contributor>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5776/1/sigmod97_para_final_web.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:02Z</dc:date>
    <dcterms:abstract xml:lang="eng">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 nearestneighbor 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.</dcterms:abstract>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5776/1/sigmod97_para_final_web.pdf"/>
    <dc:contributor>Böhm, Christian</dc:contributor>
    <dc:contributor>Keim, Daniel A.</dc:contributor>
    <dcterms:bibliographicCitation>First publ. in: Proceedings of the 1997 ACM SIGMOD international conference on Management of data, 1997, pp. 1-12</dcterms:bibliographicCitation>
    <dc:creator>Kriegel, Hans-Peter</dc:creator>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:creator>Braunmüller, Bernhard</dc:creator>
    <dc:format>application/pdf</dc:format>
    <dc:contributor>Kriegel, Hans-Peter</dc:contributor>
    <dc:creator>Böhm, Christian</dc:creator>
    <dc:contributor>Berchtold, Stefan</dc:contributor>
    <dcterms:title>Fast Parallel Similarity Search in Multimedia Databases</dcterms:title>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5776"/>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dcterms:issued>1997</dcterms:issued>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:02Z</dcterms:available>
    <dc:creator>Berchtold, Stefan</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
URL of original publication
Test date of URL
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
No
Refereed