Publikation: On Optimizing Nearest Neighbor Queries in High-Dimensional Spaces
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
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)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BERCHTOLD, 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_28BibTex
@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>