KOPS - Das Institutionelle Repositorium der Universität Konstanz

Improving the Query Performance of High-Dimensional Index Structures Using Bulk-Load Operations

Improving the Query Performance of High-Dimensional Index Structures Using Bulk-Load Operations


Dateien zu dieser Ressource

Prüfsumme: MD5:a6f6ad6f07db87554381ddbd94c6eb9f

BERCHTOLD, Stefan, Christian BÖHM, Hans-Peter KRIEGEL, 2006. Improving the Query Performance of High-Dimensional Index Structures Using Bulk-Load Operations. In: SCHEK, Hans-Jörg, ed., Gustavo ALONSO, ed., Felix SALTOR, ed., Isidro RAMOS, ed.. Advances in Database Technology — EDBT'98. Berlin, Heidelberg:Springer Berlin Heidelberg, pp. 216-230. ISBN 978-3-540-64264-0

@inproceedings{Berchtold2006-11-22Impro-5780, title={Improving the Query Performance of High-Dimensional Index Structures Using Bulk-Load Operations}, year={2006}, doi={10.1007/BFb0100987}, number={1377}, isbn={978-3-540-64264-0}, address={Berlin, Heidelberg}, publisher={Springer Berlin Heidelberg}, series={Lecture Notes in Computer Science}, booktitle={Advances in Database Technology — EDBT'98}, pages={216--230}, editor={Schek, Hans-Jörg and Alonso, Gustavo and Saltor, Felix and Ramos, Isidro}, author={Berchtold, Stefan and Böhm, Christian 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/5780"> <dcterms:bibliographicCitation>First publ. in: Advances in Database Technology EDBT'98. Berlin: Springer, 1998, pp. 216-230</dcterms:bibliographicCitation> <dcterms:issued>2006-11-22</dcterms:issued> <dc:contributor>Böhm, Christian</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:04Z</dcterms:available> <dc:format>application/pdf</dc:format> <dc:creator>Böhm, Christian</dc:creator> <dcterms:abstract xml:lang="eng">In this paper, we propose a new bulk-loading technique for high-dimensional indexes which represent an important component of multimedia database systems. Since it is very inefficient to construct an index for a large amount of data by dynamic insertion of single objects, there is an increasing interest in bulk-loading techniques. In contrast to previous approaches, our technique exploits a priori knowledge of the complete data set to improve both construction time and query performance. Our algorithm operates in a mannar similar to the Quicksort algorithm and has an average runtime complexity of O(n log n). We additionally improve the query performance by optimizing the shape of the bounding boxes, by completely avoiding overlap, and by clustering the pages on disk. As we analytically show, the split strategy typically used in dynamic index structures, splitting the data space at the 50%-quantile, results in a bad query performance in high-dimensional spaces. Therefore, we use a sophisticated unbalanced split strategy, which leads to a much better space partitioning. An exhaustive experimental evaluation shows that our technique clearly outperforms both classic index construction and competitive bulk loading techniques. In comparison with dynamic index construction we achieve a speed-up factor of up to 588 for the construction time. The constructed index causes up to 16.88 times fewer page accesses and is up to 198 times faster (real time) in query processing.</dcterms:abstract> <dc:contributor>Berchtold, Stefan</dc:contributor> <dc:rights>deposit-license</dc:rights> <dcterms:title>Improving the Query Performance of High-Dimensional Index Structures Using Bulk-Load Operations</dcterms:title> <dc:creator>Kriegel, Hans-Peter</dc:creator> <dcterms:rights rdf:resource="https://creativecommons.org/licenses/by-nc-nd/2.0/legalcode"/> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5780"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:04Z</dc:date> <dc:contributor>Kriegel, Hans-Peter</dc:contributor> <dc:creator>Berchtold, Stefan</dc:creator> <dc:language>eng</dc:language> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

edt98.pdf 139

Das Dokument erscheint in:

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

KOPS Suche


Mein Benutzerkonto