The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - UB-Baum (de)
- UB-tree (en)
- UB-дерево (ru)
|
| rdfs:comment
| - Der UB-Baum („Universal B-Tree“) wurde von Rudolf Bayer und vorgeschlagen und isteine Datenstruktur für mehrdimensionale Datenbanksysteme. Es ist ein B+-Baum, bei dem die Daten nach der Z-Kurve (Berechnen der Z-Werte durch bitweise Verschränkung der Schlüssel) sortiert abgelegt werden. Die Kernidee dieses Verfahrens wurde schon sehr viel früher (für Suchbäume im Allgemeinen von Tropf und Herzog sowie für B-Bäume von Orenstein und Merrett) vorgeschlagen. (de)
- The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys. (en)
- UB-дерево— сбалансированное дерево для хранения и эффективного извлечения . Предложено Рудольфом Байером и ; является B⁺-деревом с записями, хранящимися в соответствии с Z-порядком, также называемым порядком Мортона. Z-порядок вычисляется путём побитового чередования ключей. Вставка, удаление и точечный запрос выполняются как с обычными B⁺-деревьями. Однако для выполнения поиска по диапазону в многомерных точечных данных должен быть предусмотрен алгоритм для вычисления из точки, обнаруженной в базе данных, следующего Z-значения, которое находится в диапазоне многомерного поиска. (ru)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Der UB-Baum („Universal B-Tree“) wurde von Rudolf Bayer und vorgeschlagen und isteine Datenstruktur für mehrdimensionale Datenbanksysteme. Es ist ein B+-Baum, bei dem die Daten nach der Z-Kurve (Berechnen der Z-Werte durch bitweise Verschränkung der Schlüssel) sortiert abgelegt werden. Die Kernidee dieses Verfahrens wurde schon sehr viel früher (für Suchbäume im Allgemeinen von Tropf und Herzog sowie für B-Bäume von Orenstein und Merrett) vorgeschlagen. Einfügen, Löschen und exakte Anfragen werden behandelt wie bei normalen B+ Bäumen. Für mehrdimensionale Bereichsanfragen benötigt man ein Verfahren, um, ausgehend von einem in der Datenstruktur angetroffenen Z-Wert, den nächsten zu finden, der innerhalb des mehrdimensionalen Suchbereichs liegt. Das hierfür ursprünglich von Rudolf Bayer angegebene Verfahren war im Aufwand exponentiell mit der Anzahl der Dimensionen und somit für mehr als 4 Dimensionen nicht praktisch verwendbar. Eine Lösung für das Problem („crucial part of the UB-tree range query“), linear mit der Bitlänge der Z-Werte, wurde später beschrieben („GetNextZ-address“); diese Methode war bereits beschrieben worden in („BIGMIN“-Berechnung). (de)
- The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys. Insertion, deletion, and point query are done as with ordinary B+ trees. To perform range searches in multidimensional point data, however, an algorithm must be provided for calculating, from a point encountered in the data base, the next Z-value which is in the multidimensional search range. The original algorithm to solve this key problem was exponential with the dimensionality and thus not feasible ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" linear with the z-address bit length has been described later. This method has already been described in an older paper where using Z-order with search trees has first been proposed. (en)
- UB-дерево— сбалансированное дерево для хранения и эффективного извлечения . Предложено Рудольфом Байером и ; является B⁺-деревом с записями, хранящимися в соответствии с Z-порядком, также называемым порядком Мортона. Z-порядок вычисляется путём побитового чередования ключей. Вставка, удаление и точечный запрос выполняются как с обычными B⁺-деревьями. Однако для выполнения поиска по диапазону в многомерных точечных данных должен быть предусмотрен алгоритм для вычисления из точки, обнаруженной в базе данных, следующего Z-значения, которое находится в диапазоне многомерного поиска. Первоначальный алгоритм решения этой ключевой проблемы был экспоненциально зависим от размерности и, следовательно, неосуществим («ПолучитьДальшеZ-адрес»[уточнить]). Решение этой важной части запроса диапазона UB-дерева[уточнить], линейного с длиной в битах z-адреса, было описано позже. Этот метод уже был описан в более старой статье. (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is known for
of | |
| is known for
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
