| dbo:abstract
|
- R-strom (anglicky R-tree) je stromová datová struktura podobná B-stromům, ale používaná pro prostorové přístupové metody, například pro indexovaní vícerozměrných struktur například v geografických informačních systémech. Mimo to, pomocí R-stromů je implementováno například datové úložiště MyISAM v MySQL. Datová struktura dělí místo na hierarchicky vkládané a potenciálně se překrývající, tzv. MBR (minimum bounding rectangles – minimální ohraničující obdélníky, též nazývané obdélníky nebo boxy – R z anglického výrazu pro obdélník (rectangle) tvoří část názvu R-stromů). Každý uzel R-stromu má proměnlivý počet záznamů (až do předdefinovaného maxima). Každý záznam uvnitř uzlu, který není listem, ukládá dvě další informace: způsob identifikace dceřiného uzlu a MBR všech záznamů uvnitř tohoto dceřiného uzlu. Algoritmy pro vložení nového a smazání stávajícího prvku používají MBR z uzlů ke kontrole, že prvky v geometrickém okolí jsou umístěny do stejných listových uzlů (konkrétně, nový prvek půjde do listového uzlu, který potřebuje nejmenší rozšíření svého MBR). Každý záznam uvnitř listového uzlu uloží dvě informace: identifikátor daného prvku (který může být alternativně umístěn přímo do uzlu) a MBR datového prvku. Podobně, vyhledávací algoritmy používají MBR k rozhodnutí, zdali hledat uvnitř daného uzlu. Tímto způsobem při hledání většina uzlů „netknutých“. Stejně jako B-stromy, jsou R-stromy vhodné pro databáze, kde se uzly podle potřeby mohou načítat do paměti. U R-stromů lze nastavit nejen maximální počet prvků v něm, ale i algoritmus, kdy se má daný list změnit v uzel další úrovně. Mezi tyto algoritmy patří:
* linear-cost algoritm
* quadratic-cost algoritm
* exhaustive algoritm R-stromy nezaručují dobrý výkon pro nejnepříznivější případ uložení dat, ale jejich implementace dosahují slušných výkonů při použití „reálných“ dat. V roce 2004 byl nicméně vyvinut nový algoritmus, Priority R-Tree, který má výkon vylepšovat právě pro nepříznivě uložená data. (cs)
- Ein R-Baum (englisch R-tree) ist eine in Datenbanksystemen verwendete mehrdimensionale räumliche dynamische Indexstruktur. Ähnlich wie bei einem eindimensionalen B-Baum handelt es sich hier um eine balancierte Indexstruktur. Er kann als eine Struktur angesehen werden, die die Eigenschaften des eindimensionalen B-Baums mit dem mehrdimensionalen k-d-Baum kombiniert. Die Knoten des Baums enthalten eine sortierte Menge von Koordinaten, die zum Beispiel mit Arrays oder Listen realisiert werden kann. Für die Verknüpfungen zwischen den Koordinaten können Zeiger verwendet werden. (de)
- 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 ; 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 almacena dos datos: una forma de identificar a un 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 (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 para el peor caso. (es)
- R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both theoretical and applied contexts. A common real-world usage for an R-tree might be to store spatial objects such as restaurant locations or the polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as "Find all museums within 2 km of my current location", "retrieve all road segments within 2 km of my location" (to display them in a navigation system) or "find the nearest gas station" (although not taking roads into account). The R-tree can also accelerate nearest neighbor search for various distance metrics, including great-circle distance. (en)
- Les R-arbres sont des structures de données sous forme d'arbre utilisées comme méthodes d'exploration spatiale. Elles servent à indexer des informations multidimensionnelles (coordonnées géographiques, rectangles ou polygones). Inventés par en 1984, les R-arbres sont utilisés aussi bien dans des contextes théoriques qu'appliqués. Un cas d'utilisation typique des R-arbres est le stockage d'informations géographiques : par exemple l'emplacement des restaurants dans une ville, ou les polygones constitutifs des dessins d'une carte (routes, bâtiments, côtes, etc.), et de pouvoir par la suite répondre à des requêtes du type de "trouver tous les musées dans un rayon de 2 kilomètres", "afficher toutes les routes situées à moins de 5 kilomètres" ou "trouver la station-service la plus proche de ma position", par exemple dans une application de navigation. Les R-arbres peuvent également êtres utilisés pour accélérer la recherche des K plus proches voisins, en particulier pour certaines métriques comme la distance du grand cercle. (fr)
- R 트리는 B 트리와 비슷한데 다차원의 공간 데이터를 저장하는 색인이다. 이를테면, 지리학에서 R 트리는 "현재 위치에서 200km 이내의 모든 도시를 찾아라"와 같은 에 대해 빠르게 답을 줄 수 있다. 이 자료 구조는 공간을 최소 경계 사각형(MBR, Minimum Bounding Rectangle) 들로 분할하여 저장한다. MBR끼리 겹칠 수도 있고, 상위 레벨의 MBR 은 하위 레벨의 MBR들을 포함하는 계층적인 트리 구조이다. 각 노드는 미리 정의된 범위내에서 유동적인 개수의 자식 노드들의 정보 (MBR과 포인터)를 가진다. R-트리의 저장과 삭제 알고리즘은 가까운 데이터들은 되도록 같은 (leaf)에 두려고 한다. 그럼으로써 R 트리는 굳건하게 MBR을 유지할 수 있고, 검색 성능이 좋아지게 된다. 검색 알고리즘들(intersection, containment, nearest neighbor)이 이러한 MBR 들을 사용하여, 하위 레벨의 자식 노드를 검색할 것인지를 결정하기 때문이다. (ko)
- R木（英: R-tree）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。 (ja)
- Gli R-tree o R-alberi sono un tipo di albero 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 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. (it)
- R-drzewo (ang. R-tree) – dynamiczna, zbalansowana struktura danych wspomagająca wyszukiwanie obiektów w przestrzeni wielowymiarowej. Stanowi rozwinięcie idei B-drzewa na większą liczbę wymiarów. Została zaproponowana przez Antonina Guttmana w 1984 roku. R-drzewa wykorzystuje się głównie w systemach baz danych. Do opisania obiektów wielowymiarowych wykorzystywane są minimalne regiony pokrywające (ang. MBR – minimal bounding rectangle) lub inaczej pudełka okalające (ang. AABB - axis aligned bounding box). Typowym przykładem użycia R-drzewa jest przechowanie punktów reprezentujących współrzędne geograficzne restauracji lub regionów reprezentujących powierzchnie ulic, budynków, jezior, itd., a następnie wyszukanie tych, które spełniają określone kryteria. Umożliwia to znalezienie odpowiedzi na zapytania typu „znajdź wszystkie muzea w promieniu 2 km”, „znajdź wszystkie drogi znajdujące się w obszarze” (w celu wyświetlenia ich na urządzeniu służącym do nawigacji) lub „znajdź najbliższą stację paliw”. (pl)
- Árvores R são árvores 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 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(por exemplo: intersecção, , mais próximo) 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. (pt)
- R-дерево (англ. R-trees) — деревоподібна структура даних, яка використовується для організації доступу до просторових даних, тобто для індексації багатовимірної інформації, такої, наприклад, як географічні координати, прямокутники або многокутники. R-дерево було запропоноване в 1984 році і знайшло значне застосування як у теоретичному, так і у прикладному аспектах. Типовим запитом з використанням R-дерев міг би бути такий: «Знайти всі музеї у радіусі 2 кілометрів від мого поточного місця розташування» або «знайти всі дороги в межах 2 кілометрів від мого поточного місця розташування» (для навігаційної системи). R-дерево також прискорює пошук найближчого сусіда для різних метрик відстані, включаючи відстань по сфері. У випадку двовимірного простору, ця структура даних розбиває простір на множину ієрархічно вкладених прямокутників, які можуть перетинатись. У разі тривимірного або багатовимірного простору це будуть прямокутні паралелепіпеди. Алгоритми вставки і видалення використовують ці обмежуючі прямокутники для забезпечення того, щоб «близько розташовані» об'єкти були поміщені в одну листову вершину. Зокрема, новий об'єкт потрапить у ту листову вершину, для якої потрібно найменше розширення її прямокутника. Кожен елемент листової вершини зберігає два поля даних: спосіб ідентифікації даних, що описують об'єкт, (або самі ці дані) і прямокутник, який обмежує цей об'єкт. Аналогічно, алгоритми пошуку (наприклад, перетин, включення, окіл) використовують обмежуючі прямокутники для прийняття рішення про необхідність пошуку в дочірній вершині. Таким чином, більшість вершин ніколи не використовуються при пошуку. Як і у випадку з B-деревами, ця властивість R-дерев обумовлює їх придатність для баз даних, де вершини можуть вивантажуватися на накопичувач в міру необхідності. Для розділення переповнених вершин можуть застосовуватися різні алгоритми, що породжує поділ R-дерев на підтипи: квадратичні та лінійні. Спочатку R-дерева не гарантували гарних характеристик для найгіршого випадку, хоча добре працювали на реальних даних. Однак, в 2004-му році був опублікований новий алгоритм, що визначає пріоритетні R-дерева. Стверджується, що цей алгоритм ефективний, як і найбільш ефективні сучасні методи, і в той же час є оптимальним для найгіршого випадку. (uk)
- R树是用来做的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。R树是由Antonin Guttman于1984年提出的。人们随后发现它在理论和应用方面都非常实用。 在现实生活中，R树可以用来存储地图上的空间信息，例如餐馆地址，或者地图上用来构造街道，建筑，湖泊边缘和海岸线的多边形。然后可以用它来回答“查找距离我2千米以内的博物馆”，“检索距离我2千米以内的所有路段”（然后显示在导航系统中）或者“查找（直线距离）最近的加油站”这类问题。R树还可以用来加速使用包括大圆距离在内的各种距离度量方式的最邻近搜索。 (zh)
- R-дерево (англ. R-trees) — древовидная структура данных (дерево), предложенная в 1984 году . Она подобна B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения». Эта структура данных разбивает многомерное пространство на множество иерархически вложенных и, возможно, пересекающихся, прямоугольников (для двумерного пространства). В случае трехмерного или многомерного пространства это будут прямоугольные параллелепипеды (кубоиды) или . Алгоритмы вставки и удаления используют эти ограничивающие прямоугольники для обеспечения того, чтобы «близкорасположенные» объекты были помещены в одну листовую вершину. В частности, новый объект попадёт в ту листовую вершину, для которой потребуется наименьшее расширение её ограничивающего прямоугольника. Каждый элемент листовой вершины хранит два поля данных: способ идентификации данных, описывающих объект, (либо сами эти данные) и ограничивающий прямоугольник этого объекта. Аналогично, алгоритмы (например, пересечение, включение, окрестности) используют ограничивающие прямоугольники для принятия решения о необходимости поиска в дочерней вершине. Таким образом, большинство вершин никогда не затрагиваются в ходе поиска. Как и в случае с B-деревьями, это свойство R-деревьев обусловливает их применимость для баз данных, где вершины могут выгружаться на диск по мере необходимости. Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: квадратичные и линейные. Изначально R-деревья не гарантировали хороших характеристик для наихудшего случая, хотя хорошо работали на реальных данных. Однако в 2004-м году был опубликован новый алгоритм, определяющий приоритетные R-деревья. Утверждается, что этот алгоритм эффективен, как и наиболее эффективные современные методы, и в то же время является оптимальным для наихудшего случая. (ru)
|
| rdfs:comment
|
- Ein R-Baum (englisch R-tree) ist eine in Datenbanksystemen verwendete mehrdimensionale räumliche dynamische Indexstruktur. Ähnlich wie bei einem eindimensionalen B-Baum handelt es sich hier um eine balancierte Indexstruktur. Er kann als eine Struktur angesehen werden, die die Eigenschaften des eindimensionalen B-Baums mit dem mehrdimensionalen k-d-Baum kombiniert. Die Knoten des Baums enthalten eine sortierte Menge von Koordinaten, die zum Beispiel mit Arrays oder Listen realisiert werden kann. Für die Verknüpfungen zwischen den Koordinaten können Zeiger verwendet werden. (de)
- R 트리는 B 트리와 비슷한데 다차원의 공간 데이터를 저장하는 색인이다. 이를테면, 지리학에서 R 트리는 "현재 위치에서 200km 이내의 모든 도시를 찾아라"와 같은 에 대해 빠르게 답을 줄 수 있다. 이 자료 구조는 공간을 최소 경계 사각형(MBR, Minimum Bounding Rectangle) 들로 분할하여 저장한다. MBR끼리 겹칠 수도 있고, 상위 레벨의 MBR 은 하위 레벨의 MBR들을 포함하는 계층적인 트리 구조이다. 각 노드는 미리 정의된 범위내에서 유동적인 개수의 자식 노드들의 정보 (MBR과 포인터)를 가진다. R-트리의 저장과 삭제 알고리즘은 가까운 데이터들은 되도록 같은 (leaf)에 두려고 한다. 그럼으로써 R 트리는 굳건하게 MBR을 유지할 수 있고, 검색 성능이 좋아지게 된다. 검색 알고리즘들(intersection, containment, nearest neighbor)이 이러한 MBR 들을 사용하여, 하위 레벨의 자식 노드를 검색할 것인지를 결정하기 때문이다. (ko)
- R木（英: R-tree）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。 (ja)
- R树是用来做的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。R树是由Antonin Guttman于1984年提出的。人们随后发现它在理论和应用方面都非常实用。 在现实生活中，R树可以用来存储地图上的空间信息，例如餐馆地址，或者地图上用来构造街道，建筑，湖泊边缘和海岸线的多边形。然后可以用它来回答“查找距离我2千米以内的博物馆”，“检索距离我2千米以内的所有路段”（然后显示在导航系统中）或者“查找（直线距离）最近的加油站”这类问题。R树还可以用来加速使用包括大圆距离在内的各种距离度量方式的最邻近搜索。 (zh)
- R-strom (anglicky R-tree) je stromová datová struktura podobná B-stromům, ale používaná pro prostorové přístupové metody, například pro indexovaní vícerozměrných struktur například v geografických informačních systémech. Mimo to, pomocí R-stromů je implementováno například datové úložiště MyISAM v MySQL. Datová struktura dělí místo na hierarchicky vkládané a potenciálně se překrývající, tzv. MBR (minimum bounding rectangles – minimální ohraničující obdélníky, též nazývané obdélníky nebo boxy – R z anglického výrazu pro obdélník (rectangle) tvoří část názvu R-stromů). (cs)
- 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 ; 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. (es)
- R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both theoretical and applied contexts. A common real-world usage for an R-tree might be to store spatial objects such as restaurant locations or the polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as "Find all museums within 2 km of my current location", "retrieve all road segments within 2 km of my location" (to display them in a navigation system) or "find the nearest gas station" (although not taking roads into account). The R-tree can also a (en)
- Les R-arbres sont des structures de données sous forme d'arbre utilisées comme méthodes d'exploration spatiale. Elles servent à indexer des informations multidimensionnelles (coordonnées géographiques, rectangles ou polygones). Inventés par en 1984, les R-arbres sont utilisés aussi bien dans des contextes théoriques qu'appliqués. Un cas d'utilisation typique des R-arbres est le stockage d'informations géographiques : par exemple l'emplacement des restaurants dans une ville, ou les polygones constitutifs des dessins d'une carte (routes, bâtiments, côtes, etc.), et de pouvoir par la suite répondre à des requêtes du type de "trouver tous les musées dans un rayon de 2 kilomètres", "afficher toutes les routes situées à moins de 5 kilomètres" ou "trouver la station-service la plus proche de ma (fr)
- Gli R-tree o R-alberi sono un tipo di albero 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 innestati gerarchicamente e quando possibile sovrapposti. (it)
- R-drzewo (ang. R-tree) – dynamiczna, zbalansowana struktura danych wspomagająca wyszukiwanie obiektów w przestrzeni wielowymiarowej. Stanowi rozwinięcie idei B-drzewa na większą liczbę wymiarów. Została zaproponowana przez Antonina Guttmana w 1984 roku. R-drzewa wykorzystuje się głównie w systemach baz danych. (pl)
- Árvores R são árvores 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). (pt)
- R-дерево (англ. R-trees) — деревоподібна структура даних, яка використовується для організації доступу до просторових даних, тобто для індексації багатовимірної інформації, такої, наприклад, як географічні координати, прямокутники або многокутники. R-дерево було запропоноване в 1984 році і знайшло значне застосування як у теоретичному, так і у прикладному аспектах. Типовим запитом з використанням R-дерев міг би бути такий: «Знайти всі музеї у радіусі 2 кілометрів від мого поточного місця розташування» або «знайти всі дороги в межах 2 кілометрів від мого поточного місця розташування» (для навігаційної системи). R-дерево також прискорює пошук найближчого сусіда для різних метрик відстані, включаючи відстань по сфері. (uk)
- R-дерево (англ. R-trees) — древовидная структура данных (дерево), предложенная в 1984 году . Она подобна B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения». Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: квадратичные и линейные. (ru)
|
