| dbpedia-owl:abstract
|
- Ein R-Baum ist eine in Datenbanksystemen verwendete mehrdimensionale (räumliche) dynamische Indexstruktur. Ähnlich zu einem B-Baum handelt es sich hier um eine balancierte Indexstruktur.
- R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods, i.e. , for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 km of my current location". The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (MBRs, otherwise known as bounding boxes, i.e. "rectangle", what the "R" in R-tree stands for). Each node of an R-tree has a variable number of entries (up to some pre-defined maximum). Each entry within a non-leaf node stores two pieces of data: a way of identifying a child node, and the bounding box of all entries within this child node. The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that "nearby" elements are placed in the same leaf node (in particular, a new element will go into the leaf node that requires the least enlargement in its bounding box). Each entry within a leaf node stores two pieces of information; a way of identifying the actual data element (which, alternatively, may be placed directly in the node), and the bounding box of the data element. Similarly, the searching algorithms (e.g. , intersection, containment, nearest) use the bounding boxes to decide whether or not to search inside a child node. In this way, most of the nodes in the tree are never "touched" during a search. Like B-trees, this makes R-trees suitable for databases, where nodes can be paged to memory when needed. Different algorithms can be used to split nodes when they become too full, resulting in the quadratic and linear R-tree sub-types. R-trees do not historically guarantee good worst-case performance, but generally perform well with real-world data. However, a new algorithm was published in 2004 that defines the Priority R-Tree, which claims to be as efficient as the most efficient methods of 2004 and is at the same time worst-case optimal. When data is organized in an R-Tree, the k nearest neighbors of all points can efficiently be computed using a spatial join. This is beneficial for many algorithms based on the k nearest neighbors, for example the Local Outlier Factor.
- Los árboles-R o R-árboles son estructuras de datos de tipo árbol similares a los árboles-B, con la diferencia de que se utilizan para métodos de acceso espacial, es decir, para indexar información multidimensional; por ejemplo, las coordenadas (x, y) de un lugar geográfico. Un problema con aplicación práctica en el mundo real podría ser: "Encontrar todos los museos en un radio de dos kilómetros alrededor de la posición actual". La estructura de datos divide el espacio de forma jerárquica en conjuntos, posiblemente superpuestos. Cada nodo de un árbol-R tiene un número variable de entradas (hasta un máximo predefinido). Cada entrada de un nodo interno almacena dos datos: una forma de identificar a un nodo hijo y el conjunto límite de todas las entradas de ese nodo hijo. Los algoritmos de inserción y borrado utilizan los conjuntos límite de los nodos para asegurar que elementos cercanos están localizados en la misma hoja (en particular, un nuevo elemento será insertado en la hoja que requiera el menor aumento del conjunto límite). Cada entrada de una hoja contiene dos datos: una forma de identificar el elemento actual (que, alternativamente, podría estar directamente en el nodo) y el conjunto límite de ese elemento. De forma similar, los algoritmos de búsqueda utilizan los conjuntos límite para decidir en qué nodo buscar. De este modo, la mayoría de los nodos del árbol nunca son examinados durante una búsqueda. Esto hace que este tipo de árboles (como los árboles-B) sean idóneos para el trabajo con bases de datos. Se pueden utilizar distintos algoritmos para dividir nodos cuando estos crecen demasiado, resultando subtipos de árbol-R cuadráticos y lineales. Los árboles-R no garantizan un buen rendimiento en el peor caso, pero en general se comportan bien con datos del mundo real. Sin embargo, recientemente, en 2004, se publicó un nuevo algoritmo que define el árbol R-de prioridad, que parece ser tan eficiente como los métodos actuales más eficientes y, al mismo tiempo, óptimo en el caso peor.
- Gli R-tree o R-alberi sono un tipo di albero (grafo) simile al B-Albero, ma sono usati per indicizzare spazi multidimensionali, ad esempio le coordinate spaziali (X, Y) per dati geografici. Una richiesta di esempio che usi un R-tree potrebbe essere "Trova tutti i musei entro 2 km dalla mia posizione attuale". La struttura dati divide lo spazio in MBR (minimum bounding rectangles, infatti R-tree deriva proprio da Rectangle) innestati gerarchicamente e quando possibile sovrapposti. Ogni nodo dell'R-tree ha un numero variabile di entry (fino ad un massimo predeterminato). Ogni entry che non sia un nodo foglia contiene due entità: una identifica il nodo figlio, l'altra l'MBR che contiene tutte le entry del nodo figlio. L'algoritmo di inserimento e cancellazione di entry dagli MBR assicura che elementi "vicini" siano posizionati nello stesso posto (nodo foglia): un nuovo elemento andrà nel nodo foglia che richiede il minor numero di estensioni delle dimensioni dell'MBR). Gli algoritmi di ricerca usano gli MBR per decidere se cercare o meno nel nodo figlio del nodo corrente. In questo modo la maggior parte dei nodi non viene esplorata dagli algoritmi. Per questo motivo, come per i B-tree, ciò rende gli R-tree adatti ai database, dove i nodi possono essere copiati in memoria solo quando necessario. Diversi algoritmi possono essere usati per dividere i nodi quando diventano troppo estesi, ovvero quando vengono aggiunti in un nodo un numero di elementi che supera il limite prestabiito. Gli R-tree non garantiscono una performance ottima di caso peggiore, ma in generale si comportano molto bene con dati reali. Per questo nel 2004 è stato sviluppato un nuovo algoritmo (Priority R-tree), che cerca di essere efficiente ed allo stesso tempo ottimo rispetto al caso peggiore.
- R木（Template:Lang-en-short）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。
- R-drzewo – dynamiczna struktura danych wspomagająca wyszukiwanie obiektów w przestrzeni wielowymiarowej. R-drzewa wykorzystuje się głównie w systemach baz danych. W przeciwieństwie do drzew kd, kdB-drzew oraz hdB-drzew R-drzewa umożliwiają wyszukiwanie obiektów niepunktowych. Do opisania obiektów wielowymiarowych wykorzystują minimalne regiony pokrywające (ang. MBR - minimal bounding rectangle).
- Àrvores R são ávores de estruturas de dados que são similares as árvores B, mas que são usadas para métodos de acesso no espaço com o fim de indexar informação multi-dimensional, por exemplo, as coordenadas (X, Y) de uma posição geográfica. Um exemplo de uso comum das árvores R seria: "Encontre todos os museus que estão até no máximo 1,5 km da minha posição geográfica atual". A estrutura de dados divide o espaço com aninhamento hierarquico, e possivelmente sobreposição de retangulos de limite mínimos (também chamados de caixas limitantes - bounding boxes). Cada nodo de uma árvore R tem um número variável de entradas(até um limite máximo pré-definido). Cada entrada dentro de um nodo. que não é folha, armazena dois tipos de dados: uma maneira de identificar um nodo filho, e a caixa limitante de todas as entradas dentro deste nodo filho. Os algoritmos de inserção e remoção usam caixas limitantes a partir dos nodos para assegurar que todos os elementos próximos estão localizados no mesmo nodo folha (Em particular, um novo elemento será adicionado ao nodo folha que requer o menor aumento espacial na sua caixa limitante). Cada entrada dentro de um nodo folha armazena também dois pedaços de informação: uma maneira de identificar o elemento de dados real(o que, alternadamente, pode ser colocado diretamente no nodo), e a caixa limitante do elemento de dados. Analogamente, os algoritmos de busca usam caixas limitantes para decidir se irão buscar ou não dentro de um nodo filho. Desta forma, a maioria dos nodos na árvore jamais são alcançados durante uma busca. Como árvores B, isto torna as árvores R mais indicadas para banco de dados, aonde nodos podem ser paginados na memória do computador quando preciso. Algoritmos diferentes podem ser usados para dividir os nodos quando ele se tornam cheios demais, resultando em subtipos de árvores R: quadricas e lineares. Árvores R não garantem historicamente boa performance no pior caso, mas geralmente demonstram boa performance na aplicação prática com dados reais. Contudo, um novo algoritmo foi publicado em 2004 que definiu a prioridade de uma árvore R, e que assume ser tão eficiente quanto os mais eficientes métodos atuais e assume-se ter ótima performance nos testes de pior caso.
- R-дерево — древовидная структура данных, предложенная в 1984 году Антонином Гуттманом. Оно подобно B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами. Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения». Эта структура данных разбивает пространство на множество иерархически вложенных и, возможно, пересекающихся, прямоугольников (для двумерного пространства). В случае трехмерного или многомерного пространства это будут прямоугольные параллелепипеды или параллелотопы. Алгоритмы вставки и удаления используют эти ограничивающие прямоугольники для обеспечения того, чтобы «близкорасположенные» объекты были помещены в одну листовую вершину. В частности, новый объект попадёт в ту листовую вершину, для которой потребуется наименьшее расширение ее ограничивающего прямоугольника. Каждый элемент листовой вершины хранит два поля данных: способ идентификации данных, описывающих объект, (либо сами эти данные) и ограничивающий прямоугольник этого объекта. Аналогично, алгоритмы поиска (например, пересечение, включение, окрестности) используют ограничивающие прямоугольники для принятия решения о необходимости поиска в дочерней вершине. Таким образом, большинство вершин никогда не затрагиваются в ходе поиска. Как и в случае с B-деревьями, это свойство R-деревьев обусловливает их применимость для баз данных, где вершины могут выгружаться на диск по мере необходимости. Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: квадратичные и линейные. Изначально R-деревья не гарантировали хороших характеристик для наихудшего случая, хотя хорошо работали на реальных данных. Однако, в 2004-м году был опубликован новый алгоритм, определяющий приоритетные R-деревья. Утверждается, что этот алгоритм эффективен, как и наиболее эффективные современные методы, и в то же время является оптимальным для наихудшего случая.
|
| rdfs:comment
|
- Ein R-Baum ist eine in Datenbanksystemen verwendete mehrdimensionale (räumliche) dynamische Indexstruktur. Ähnlich zu einem B-Baum handelt es sich hier um eine balancierte Indexstruktur.
- R木（Template:Lang-en-short）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。
- R-drzewo – dynamiczna struktura danych wspomagająca wyszukiwanie obiektów w przestrzeni wielowymiarowej. R-drzewa wykorzystuje się głównie w systemach baz danych. W przeciwieństwie do drzew kd, kdB-drzew oraz hdB-drzew R-drzewa umożliwiają wyszukiwanie obiektów niepunktowych. Do opisania obiektów wielowymiarowych wykorzystują minimalne regiony pokrywające (ang. MBR - minimal bounding rectangle).
- R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods, i.e. , for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 km of my current location". The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (MBRs, otherwise known as bounding boxes, i.e.
- Los árboles-R o R-árboles son estructuras de datos de tipo árbol similares a los árboles-B, con la diferencia de que se utilizan para métodos de acceso espacial, es decir, para indexar información multidimensional; por ejemplo, las coordenadas (x, y) de un lugar geográfico. Un problema con aplicación práctica en el mundo real podría ser: "Encontrar todos los museos en un radio de dos kilómetros alrededor de la posición actual".
- Gli R-tree o R-alberi sono un tipo di albero (grafo) simile al B-Albero, ma sono usati per indicizzare spazi multidimensionali, ad esempio le coordinate spaziali (X, Y) per dati geografici. Una richiesta di esempio che usi un R-tree potrebbe essere "Trova tutti i musei entro 2 km dalla mia posizione attuale". La struttura dati divide lo spazio in MBR (minimum bounding rectangles, infatti R-tree deriva proprio da Rectangle) innestati gerarchicamente e quando possibile sovrapposti.
- Àrvores R são ávores de estruturas de dados que são similares as árvores B, mas que são usadas para métodos de acesso no espaço com o fim de indexar informação multi-dimensional, por exemplo, as coordenadas (X, Y) de uma posição geográfica. Um exemplo de uso comum das árvores R seria: "Encontre todos os museus que estão até no máximo 1,5 km da minha posição geográfica atual".
- R-дерево — древовидная структура данных, предложенная в 1984 году Антонином Гуттманом. Оно подобно B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами. Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения».
|
