On Optimizing Nearest Neighbor Queries in High-Dimensional Spaces

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:5c758c9c22e9ea177007996b15a7d4fb

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, pp. 435-449. ISBN 978-3-540-41456-8

@inproceedings{Berchtold2001-10-12Optim-5710, title={On Optimizing Nearest Neighbor Queries in High-Dimensional Spaces}, year={2001}, doi={10.1007/3-540-44503-X_28}, number={1973}, isbn={978-3-540-41456-8}, address={Berlin, Heidelberg}, publisher={Springer 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 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/5710"> <dc:language>eng</dc:language> <dc:contributor>Böhm, Christian</dc:contributor> <dc:creator>Krebs, Florian</dc:creator> <dc:contributor>Keim, Daniel A.</dc:contributor> <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:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:31Z</dcterms:available> <dc:rights>deposit-license</dc:rights> <dc:format>application/pdf</dc:format> <dc:creator>Böhm, Christian</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:31Z</dc:date> <dcterms:bibliographicCitation>First publ. in: Proceedings of the 8th International Conference on Database Theory, 2001, pp. 435-449</dcterms:bibliographicCitation> <dc:contributor>Kriegel, Hans-Peter</dc:contributor> <dc:creator>Kriegel, Hans-Peter</dc:creator> <dc:creator>Keim, Daniel A.</dc:creator> <dcterms:issued>2001-10-12</dcterms:issued> <dcterms:rights rdf:resource="https://creativecommons.org/licenses/by-nc-nd/2.0/legalcode"/> <dc:creator>Berchtold, Stefan</dc:creator> <dc:contributor>Krebs, Florian</dc:contributor> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5710"/> <dc:contributor>Berchtold, Stefan</dc:contributor> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

icdt01query.pdf 185

Das Dokument erscheint in:

deposit-license Solange nicht anders angezeigt, wird die Lizenz wie folgt beschrieben: deposit-license

KOPS Suche


Stöbern

Mein Benutzerkonto