Aufgrund von Vorbereitungen auf eine neue Version von KOPS, können kommenden Montag und Dienstag keine Publikationen eingereicht werden. (Due to preparations for a new version of KOPS, no publications can be submitted next Monday and Tuesday.)

The X-Tree : An Index Structure for High-Dimensional Data

Cite This

Files in this item

Checksum: MD5:6fc6cd2814b563362f339acbf32071e9

BERCHTOLD, Stefan, Daniel A. KEIM, Hans-Peter KRIEGEL, 1996. The X-Tree : An Index Structure for High-Dimensional Data. Very Large Data-Bases. Mumbai (Bombay), India, Sep 3, 1996 - Sep 6, 1996. In: VIJAYARAMAN, T. M., ed. and others. Proceedings of the Twenty-second International Conference on Very Large Data-Bases ; Mumbai (Bombay), India 3 - 6 September, 1996. San Francisco:Morgan Kaufmann, pp. 28-39

@inproceedings{Berchtold1996XTree-5734, title={The X-Tree : An Index Structure for High-Dimensional Data}, year={1996}, address={San Francisco}, publisher={Morgan Kaufmann}, booktitle={Proceedings of the Twenty-second International Conference on Very Large Data-Bases ; Mumbai (Bombay), India 3 - 6 September, 1996}, pages={28--39}, editor={Vijayaraman, T. M.}, author={Berchtold, Stefan and Keim, Daniel A. and Kriegel, Hans-Peter} }

<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/rdf/resource/123456789/5734"> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5734/1/The_X_Tree.pdf"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:abstract xml:lang="eng">In this paper, we propose a new method for indexing large amounts of point and spatial data in highdimensional space. An analysis shows that index structures such as the R*-tree are not adequate for indexing high-dimensional data sets. The major problem of R-tree-based index structures is the overlap of the bounding boxes in the directory, which increases with growing dimension. To avoid this problem, we introduce a new organization of the directory which uses a split algorithm minimizing overlap and additionally utilizes the concept of supernodes. The basic idea of overlap-minimizing split and supernodes is to keep the directory as hierarchical as possible, and at the same time to avoid splits in the directory that would result in high overlap. Our experiments show that for high-dimensional data, the X-tree outperforms the well-known R*-tree and the TV-tree by up to two orders of magnitude.</dcterms:abstract> <dc:language>eng</dc:language> <dcterms:title>The X-Tree : An Index Structure for High-Dimensional Data</dcterms:title> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <dc:creator>Berchtold, Stefan</dc:creator> <dc:format>application/pdf</dc:format> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:41Z</dc:date> <dcterms:bibliographicCitation>First publ. in: Proceedings of the Twenty-second International Conference on Very Large Data-Bases ; Mumbai (Bombay), India 3 - 6 September, 1996. / Ed. T. M. Vijayaraman ... San Francisco : Morgan Kaufmann, 1996, pp. 28-39</dcterms:bibliographicCitation> <dcterms:issued>1996</dcterms:issued> <dc:creator>Keim, Daniel A.</dc:creator> <dc:creator>Kriegel, Hans-Peter</dc:creator> <dc:contributor>Keim, Daniel A.</dc:contributor> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:41Z</dcterms:available> <dc:contributor>Kriegel, Hans-Peter</dc:contributor> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5734"/> <dc:contributor>Berchtold, Stefan</dc:contributor> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5734/1/The_X_Tree.pdf"/> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

The_X_Tree.pdf 2058

This item appears in the following Collection(s)

Attribution-NonCommercial-NoDerivs 2.0 Generic Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 2.0 Generic

Search KOPS


Browse

My Account