Publikation:

On Optimizing Nearest Neighbor Queries in High-Dimensional Spaces

Lade...
Vorschaubild

Dateien

icdt01query.pdf
icdt01query.pdfGröße: 240.48 KBDownloads: 639

Datum

2001

Autor:innen

Berchtold, Stefan
Böhm, Christian
Krebs, Florian
Kriegel, Hans-Peter

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

VAN DEN BUSSCHE, Jan, ed., Victor VIANU, ed.. Database Theory — ICDT 2001. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 435-449. Lecture Notes in Computer Science. 1973. ISBN 978-3-540-41456-8. Available under: doi: 10.1007/3-540-44503-X_28

Zusammenfassung

Nearest-neighbor queries in high-dimensional space are of high importance in various applications, especially in content-based indexing of multimedia data. For an optimization of the query processing, accurate models for estimating the query processing costs are needed. In this paper, we propose a new cost model for nearest neighbor queries in high-dimensional space, which we apply to enhance the performance of high-dimensional index structures. The model is based on new insights into effects occurring in high-dimensional space and provides a closed formula for the processing costs of nearest neighbor queries depending on the dimensionality, the block size and the database size. From the wide range of possible applications of our model, we select two interesting samples: First, we use the model to prove the known linear complexity of the nearest neighbor search problem in high-dimensional space, and second, we provide a technique for optimizing the block size. For data of medium dimensionality, the optimized block size allows significant speed-ups of the query processing time when compared to traditional block sizes and to the linear scan.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BERCHTOLD, Stefan, Christian BÖHM, Daniel A. KEIM, Florian KREBS, Hans-Peter KRIEGEL, 2001. On Optimizing Nearest Neighbor Queries in High-Dimensional Spaces. In: VAN DEN BUSSCHE, Jan, ed., Victor VIANU, ed.. Database Theory — ICDT 2001. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 435-449. Lecture Notes in Computer Science. 1973. ISBN 978-3-540-41456-8. Available under: doi: 10.1007/3-540-44503-X_28
BibTex
@inproceedings{Berchtold2001-10-12Optim-5710,
  year={2001},
  doi={10.1007/3-540-44503-X_28},
  title={On Optimizing Nearest Neighbor Queries in High-Dimensional Spaces},
  number={1973},
  isbn={978-3-540-41456-8},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Database Theory — ICDT 2001},
  pages={435--449},
  editor={Van den Bussche, Jan and Vianu, Victor},
  author={Berchtold, Stefan and Böhm, Christian and Keim, Daniel A. and Krebs, Florian 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/5710">
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:31Z</dc:date>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5710"/>
    <dc:creator>Krebs, Florian</dc:creator>
    <dc:creator>Berchtold, Stefan</dc:creator>
    <dc:contributor>Böhm, Christian</dc:contributor>
    <dc:contributor>Keim, Daniel A.</dc:contributor>
    <dc:contributor>Krebs, Florian</dc:contributor>
    <dc:language>eng</dc:language>
    <dc:contributor>Berchtold, Stefan</dc:contributor>
    <dcterms:bibliographicCitation>First publ. in: Proceedings of the 8th International Conference on Database Theory, 2001, pp. 435-449</dcterms:bibliographicCitation>
    <dc:creator>Keim, Daniel A.</dc:creator>
    <dc:format>application/pdf</dc:format>
    <dcterms:title>On Optimizing Nearest Neighbor Queries in High-Dimensional Spaces</dcterms:title>
    <dcterms:abstract xml:lang="eng">Nearest-neighbor queries in high-dimensional space are of high importance in various applications, especially in content-based indexing of multimedia data. For an optimization of the query processing, accurate models for estimating the query processing costs are needed. In this paper, we propose a new cost model for nearest neighbor queries in high-dimensional space, which we apply to enhance the performance of high-dimensional index structures. The model is based on new insights into effects occurring in high-dimensional space and provides a closed formula for the processing costs of nearest neighbor queries depending on the dimensionality, the block size and the database size. From the wide range of possible applications of our model, we select two interesting samples: First, we use the model to prove the known linear complexity of the nearest neighbor search problem in high-dimensional space, and second, we provide a technique for optimizing the block size. For data of medium dimensionality, the optimized block size allows significant speed-ups of the query processing time when compared to traditional block sizes and to the linear scan.</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dc:contributor>Kriegel, Hans-Peter</dc:contributor>
    <dcterms:issued>2001-10-12</dcterms:issued>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Böhm, Christian</dc:creator>
    <dc:creator>Kriegel, Hans-Peter</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:31Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5710/1/icdt01query.pdf"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5710/1/icdt01query.pdf"/>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen