Hilbert R-tree (original) (raw)
Hilbert R-tree, an R-tree variant, is an index for multidimensional objects such as lines, regions, 3-D objects, or high-dimensional feature-based parametric objects. It can be thought of as an extension to B+-tree for multidimensional objects. The performance of R-trees depends on the quality of the algorithm that clusters the data rectangles on a node. Hilbert R-trees use space-filling curves, and specifically the Hilbert curve, to impose a linear ordering on the data rectangles.
| Property | Value |
|---|---|
| dbo:abstract | Hilbert R-tree, an R-tree variant, is an index for multidimensional objects such as lines, regions, 3-D objects, or high-dimensional feature-based parametric objects. It can be thought of as an extension to B+-tree for multidimensional objects. The performance of R-trees depends on the quality of the algorithm that clusters the data rectangles on a node. Hilbert R-trees use space-filling curves, and specifically the Hilbert curve, to impose a linear ordering on the data rectangles. There are two types of Hilbert R-trees: one for static databases, and one for dynamic databases. In both cases Hilbert space-filling curves are used to achieve better ordering of multidimensional objects in the node. This ordering has to be "good", in the sense that it should group "similar" data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Packed Hilbert R-trees are suitable for static databases in which updates are very rare or in which there are no updates at all. The dynamic Hilbert R-tree is suitable for dynamic databases where insertions, deletions, or updates may occur in real time. Moreover, dynamic Hilbert R-trees employ flexible deferred splitting mechanism to increase the space utilization. Every node has a well defined set of sibling nodes. This is done by proposing an ordering on the R-tree nodes. The Hilbert R-tree sorts rectangles according to the of the center of the rectangles (i.e., MBR). (The Hilbert value of a point is the length of the Hilbert curve from the origin to the point.) Given the ordering, every node has a well-defined set of sibling nodes; thus, deferred splitting can be used. By adjusting the split policy, the Hilbert R-tree can achieve a degree of space utilization as high as desired. To the contrary, other R-tree variants have no control over the space utilization. (en) R-дерево Гильберта, вариант R-дерева — это индексация многомерных объектов, таких как прямые, двумерные области, трёхмерные объекты или снабжённые параметрами объекты более высоких размерностей. Их можно понимать как расширение B+-деревьев на многомерные объекты. Производительность R-деревьев зависит от качества алгоритма, группирующего данные в прямоугольники. R-деревья используют заполняющие пространство кривые, точнее, кривые Гильберта, для линейного упорядочивания объектов в прямоугольники. Существует два типа R-деревьев Гильберта, одно для статических данных, другое для динамических. В обоих случаях для получения лучшего упорядочения многомерных объектов используются заполняющие пространство кривые Гильберта. Это упорядочение «хорошее» в смысле, что оно должно бы группировать «похожие» данные в прямоугольники, минимизируя площадь и периметр этих (Minimum Bounding Rectangle, MBR). Упакованные R-деревья Гильберта пригодны для статических данных, обновляемых очень редко или не обновляемых вообще. Динамичные R-деревья Гильберта пригодны для изменяемых данных, где вставки, удаления или обновления происходят в режиме реального времени. Более того, динамичные R-деревья Гильберта используют гибкий отложенный механизм расщепления, что улучшает обработку пространства.Каждый узел имеет чётко определённое множество родственных (с одним родителем) узлов. Регулируя политику расщепления, с помощью R-деревьев Гильберта можно получить степень обработки пространства на желаемом уровне. R-деревья Гильберта сортируют прямоугольники согласно гильбертовым расстояниям центров прямоугольников (MBR). (Гильбертово расстояние точки равно длине кривой Гильберта от начала кривой до точки.). В противоположность этому другие варианты R-деревьев не имеют механизмов контроля над обработкой пространства. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Figure1_left.gif?width=300 |
| dbo:wikiPageID | 12039643 (xsd:integer) |
| dbo:wikiPageLength | 18323 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1081452791 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:R-tree dbc:R-tree dbr:Database dbr:Hilbert_curve dbr:Minimum_bounding_rectangle dbr:Space-filling_curve dbr:B+-tree dbr:Z-order_(curve) dbr:File:Figure1_left.gif dbr:File:Figure1_right.gif dbr:File:Figure2_Hilbert.gif dbr:File:Figure3_data_rects.gif dbr:File:Figure4_file_structure.gif dbr:Hilbert_value |
| dbp:wikiPageUsesTemplate | dbt:Commons_category dbt:Reflist dbt:Data_structures dbt:CS_trees |
| dcterms:subject | dbc:R-tree |
| gold:hypernym | dbr:Index |
| rdf:type | dbo:Work |
| rdfs:comment | Hilbert R-tree, an R-tree variant, is an index for multidimensional objects such as lines, regions, 3-D objects, or high-dimensional feature-based parametric objects. It can be thought of as an extension to B+-tree for multidimensional objects. The performance of R-trees depends on the quality of the algorithm that clusters the data rectangles on a node. Hilbert R-trees use space-filling curves, and specifically the Hilbert curve, to impose a linear ordering on the data rectangles. (en) R-дерево Гильберта, вариант R-дерева — это индексация многомерных объектов, таких как прямые, двумерные области, трёхмерные объекты или снабжённые параметрами объекты более высоких размерностей. Их можно понимать как расширение B+-деревьев на многомерные объекты. Производительность R-деревьев зависит от качества алгоритма, группирующего данные в прямоугольники. R-деревья используют заполняющие пространство кривые, точнее, кривые Гильберта, для линейного упорядочивания объектов в прямоугольники. (ru) |
| rdfs:label | Hilbert R-tree (en) R-дерево Гильберта (ru) |
| owl:sameAs | freebase:Hilbert R-tree wikidata:Hilbert R-tree dbpedia-ru:Hilbert R-tree dbpedia-sr:Hilbert R-tree https://global.dbpedia.org/id/4mkPS |
| prov:wasDerivedFrom | wikipedia-en:Hilbert_R-tree?oldid=1081452791&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Figure1_left.gif wiki-commons:Special:FilePath/Figure1_right.gif wiki-commons:Special:FilePath/Figure2_Hilbert.gif wiki-commons:Special:FilePath/Figure3_data_rects.gif wiki-commons:Special:FilePath/Figure4_file_structure.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Hilbert_R-tree |
| is dbo:wikiPageWikiLink of | dbr:List_of_data_structures dbr:R-tree dbr:Hilbert_curve dbr:Htree_(disambiguation) dbr:Space-filling_curve dbr:Z-order_curve dbr:List_of_things_named_after_David_Hilbert dbr:Spatial_database |
| is foaf:primaryTopic of | wikipedia-en:Hilbert_R-tree |
