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

Lade...
Vorschaubild
Dateien
edt98.pdf
edt98.pdfGröße: 183.69 KBDownloads: 361
Datum
2006
Autor:innen
Berchtold, Stefan
Böhm, Christian
Kriegel, Hans-Peter
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
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
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen 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, 2006, pp. 216-230. Lecture Notes in Computer Science. 1377. ISBN 978-3-540-64264-0. Available under: doi: 10.1007/BFb0100987
Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BERCHTOLD, 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, 2006, pp. 216-230. Lecture Notes in Computer Science. 1377. ISBN 978-3-540-64264-0. Available under: doi: 10.1007/BFb0100987
BibTex
@inproceedings{Berchtold2006-11-22Impro-5780,
  year={2006},
  doi={10.1007/BFb0100987},
  title={Improving the Query Performance of High-Dimensional Index Structures Using Bulk-Load Operations},
  number={1377},
  isbn={978-3-540-64264-0},
  publisher={Springer Berlin Heidelberg},
  address={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: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/5780">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:bibliographicCitation>First publ. in: Advances in Database Technology   EDBT'98. Berlin: Springer, 1998, pp. 216-230</dcterms:bibliographicCitation>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:04Z</dc:date>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5780"/>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:creator>Böhm, Christian</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <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>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Böhm, Christian</dc:contributor>
    <dc:contributor>Berchtold, Stefan</dc:contributor>
    <dcterms:issued>2006-11-22</dcterms:issued>
    <dcterms:title>Improving the Query Performance of High-Dimensional Index Structures Using Bulk-Load Operations</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Berchtold, Stefan</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5780/1/edt98.pdf"/>
    <dc:contributor>Kriegel, Hans-Peter</dc:contributor>
    <dc:language>eng</dc:language>
    <dc:creator>Kriegel, Hans-Peter</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:04Z</dcterms:available>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5780/1/edt98.pdf"/>
    <dc:format>application/pdf</dc:format>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
  </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
Begutachtet
Diese Publikation teilen