www.wikidata.uk-ua.nina.az

R дерево R дере ва англ R trees один з варіантів R дерев що застосовується для індексування просторової інформації R дер

R*-дерево

R*-дере́ва (англ. R*-trees) — один з варіантів R-дерев, що застосовується для індексування просторової інформації. R*-дерева мають дещо вищу конструктивну витратність, ніж стандартні R-дерева, оскільки дані можуть потребувати повторного вставляння; але отримуване в результаті дерево зазвичай матиме кращу продуктивність запитів. Як і стандартне R-дерево, воно може зберігати як точкові, так і просторові дані. Його було запропоновано Норбертом Бекманом, Гансом-Петером Крігелем[en], Ральфом Шнайдером та Бернардом Сіґером 1990 року.

Різниця між R*-деревами та R-деревами ред.

R*-дерево, побудоване повторюваними вставленнями (в ELKI[en]). В цьому дереві є невеличке перекриття, яке дає в результаті добру продуктивність запитів. Червоні та сині описані прямокутники є індексними блоками, зелені описані прямокутники є листковими вузлами.

Для продуктивності R-дерев вирішальне значення має мінімізація як покриття, так і перекриття. Перекриття означає, що при запиті або вставлянні даних розкриття потребує більш ніж одна гілка дерева (через те, що дані розщеплюються на області, які перекриваються). Мінімізоване покриття покращує продуктивність обрізання, дозволяючи частіше виключати з пошуку цілі блоки, зокрема для заперечних запитів за областями. R*-дерево намагається зменшувати і те, і те, застосовуючи поєднання переглянутого алгоритму розщеплення вузлів, та поняття примусового повторного вставляння при переповненні вузлів. Це ґрунтується на тому спостереженні, що структури R-дерев є дуже чутливими до порядку, в якому вставляються їхні записи, так що структура, побудована вставлянням (а не одночасним завантаженням) є ймовірно не зовсім оптимальною. Вилучення та повторне вставлення записів дозволяє їм «знаходити» місце в дереві, що може бути більш підхожим, ніж їхнє первинне місце.

При переповненні вузла частина записів вилучається з нього, і вставляється до дерева повторно. (Для того, щоби уникнути невизначеного каскаду повторних вставлень, спричиненого наступним переповненням вузла, процедура повторного вставлення може викликатися лише по одному разу на кожному рівні дерева при вставленні будь-якого одного нового запису.) Це дає ефект вироблення краще кластеризованих груп записів у вузлах, що зменшує покриття вузлів. Крім того, фактичні розщеплення вузлів часто відкладаються, в результаті чого середня заповненість вузла зростає. Повторне вставлення можна розглядати як метод поступової оптимізації дерева, що спрацьовує при переповненні вузла.

Продуктивність ред.

  • Покращена евристика розщеплення виробляє блоки, що є ближчими до квадратних, і відтак кращими для багатьох застосувань.
  • Метод повторного вставляння оптимізує наявне дерево, але підвищує складність.
  • Дієво підтримує як точкові, так і просторові дані одночасно.
Дія різних евристик розщеплення на базі даних із поштовими округами Німеччини
R-дерево із квадратичним розщепленням Гуттмана.
Є багато блоків, які простягаються зі сходу на захід по всій Німеччині, і блоків, які сильно перекриваються. Це не корисно для більшості застосувань, що часто потребують лише невеличкої прямокутної області, яка перетинається з багатьма смугами.
R-дерево із квадратичним розщепленням Гуттмана.
Є багато блоків, які простягаються зі сходу на захід по всій Німеччині, і блоків, які сильно перекриваються. Це не корисно для більшості застосувань, що часто потребують лише невеличкої прямокутної області, яка перетинається з багатьма смугами. 
R-дерево з лінійним розщепленням Ана-Тана.
Хоча смуги й не простягаються настільки далеко, як в Гуттмана, проблема смуг зачіпає майже кожен листковий блок. Листкові блоки перекриваються лише трохи, але каталогові блоки перекриваються.
R-дерево з лінійним розщепленням Ана-Тана.
Хоча смуги й не простягаються настільки далеко, як в Гуттмана, проблема смуг зачіпає майже кожен листковий блок. Листкові блоки перекриваються лише трохи, але каталогові блоки перекриваються. 
Топологічне розщеплення R*-дерева.
Блоки перекриваються дуже мало, оскільки R*-дерево намагається мінімізувати перекриття блоків, а повторне вставлення додатково оптимізує це дерево. Також стратегія розщеплення не віддає перевагу смугам, отримувані в результаті блоки є набагато кориснішими для поширених картографічних застосувань.
Топологічне розщеплення R*-дерева.
Блоки перекриваються дуже мало, оскільки R*-дерево намагається мінімізувати перекриття блоків, а повторне вставлення додатково оптимізує це дерево. Також стратегія розщеплення не віддає перевагу смугам, отримувані в результаті блоки є набагато кориснішими для поширених картографічних застосувань. 

Алгоритм та складність ред.

  • Для операцій здійснення запитів та вилучення R*-дерево використовує той же самий алгоритм, що й звичайне R-дерево.
  • При вставлянні R*-дерево застосовує комбіновану стратегію. Для листкових вузлів мінімізується перекриття, тоді як для внутрішніх вузлів мінімізуються поширення та площа.
  • При розщепленні R*-дерево застосовує топологічне розщеплення, яке обирає вісь розщеплення на основі периметру, а потім мінімізує перекриття.
  • На додачу до вдосконаленої стратегії розщеплення, R*-дерево також намагається уникати розщеплень, повторно вставляючи об'єкти та піддерева до дерева, під натхненням ідеї балансування B-дерева.

Таким чином, складність запиту та вилучення у найгіршому випадку є ідентичними до R-дерева. Стратегія вставляння до R*-дерева з є складнішою за стратегію лінійного розщеплення () R-дерева, але менш складною, ніж стратегія квадратичного розщеплення () для розміру блока в об'єктів, і має незначний вплив на загальну складність. Загальна складність вставляння залишається порівня́нною з R-деревом: повторне вставлення зачіпає щонайбільше одну з гілок дерева, і відтак повторних вставлень, порівня́нно до виконання розщеплення на звичайному R-дереві. Отже, в цілому складність R*-дерева є такою ж, як і в звичайного R-дерева.

Реалізація повного алгоритму мусить враховувати багато межових випадків та вузьких ситуацій, не обговорених тут.

Примітки ред.

  1. ↑ Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). . Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90. с. 322. ISBN 0897913655. doi:10.1145/93597.98741. Архів оригіналу за 17 квітня 2018. Процитовано 19 березня 2016.  (англ.)
  2. Guttman, A. (1984). . Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. с. 47. ISBN 0897911288. doi:10.1145/602259.602266. Архів оригіналу за 9 березня 2016. Процитовано 19 березня 2016.  (англ.)
  3. Ang, C. H.; Tan, T. C. (1997). New linear node splitting algorithm for R-trees. У Scholl, Michel; Voisard, Agnès. Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997. Lecture Notes in Computer Science 1262. Springer. с. 337–349. doi:10.1007/3-540-63238-7_38.  (англ.)

Посилання ред.

Вікісховище має мультимедійні дані за темою: R*-дерево


Бібліотеки, що містять R*-дерева:

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
R dere va angl R trees odin z variantiv R derev sho zastosovuyetsya dlya indeksuvannya prostorovoyi informaciyi R dereva mayut desho vishu konstruktivnu vitratnist nizh standartni R dereva oskilki dani mozhut potrebuvati povtornogo vstavlyannya ale otrimuvane v rezultati derevo zazvichaj matime krashu produktivnist zapitiv Yak i standartne R derevo vono mozhe zberigati yak tochkovi tak i prostorovi dani Jogo bulo zaproponovano Norbertom Bekmanom Gansom Peterom Krigelem en Ralfom Shnajderom ta Bernardom Sigerom 1990 roku 1 Zmist 1 Riznicya mizh R derevami ta R derevami 2 Produktivnist 3 Algoritm ta skladnist 4 Primitki 5 PosilannyaRiznicya mizh R derevami ta R derevami red nbsp R derevo pobudovane povtoryuvanimi vstavlennyami v ELKI en V comu derevi ye nevelichke perekrittya yake daye v rezultati dobru produktivnist zapitiv Chervoni ta sini opisani pryamokutniki ye indeksnimi blokami zeleni opisani pryamokutniki ye listkovimi vuzlami Dlya produktivnosti R derev virishalne znachennya maye minimizaciya yak pokrittya tak i perekrittya Perekrittya oznachaye sho pri zapiti abo vstavlyanni danih rozkrittya potrebuye bilsh nizh odna gilka dereva cherez te sho dani rozsheplyuyutsya na oblasti yaki perekrivayutsya Minimizovane pokrittya pokrashuye produktivnist obrizannya dozvolyayuchi chastishe viklyuchati z poshuku cili bloki zokrema dlya zaperechnih zapitiv za oblastyami R derevo namagayetsya zmenshuvati i te i te zastosovuyuchi poyednannya pereglyanutogo algoritmu rozsheplennya vuzliv ta ponyattya primusovogo povtornogo vstavlyannya pri perepovnenni vuzliv Ce gruntuyetsya na tomu sposterezhenni sho strukturi R derev ye duzhe chutlivimi do poryadku v yakomu vstavlyayutsya yihni zapisi tak sho struktura pobudovana vstavlyannyam a ne odnochasnim zavantazhennyam ye jmovirno ne zovsim optimalnoyu Viluchennya ta povtorne vstavlennya zapisiv dozvolyaye yim znahoditi misce v derevi sho mozhe buti bilsh pidhozhim nizh yihnye pervinne misce Pri perepovnenni vuzla chastina zapisiv viluchayetsya z nogo i vstavlyayetsya do dereva povtorno Dlya togo shobi uniknuti neviznachenogo kaskadu povtornih vstavlen sprichinenogo nastupnim perepovnennyam vuzla procedura povtornogo vstavlennya mozhe viklikatisya lishe po odnomu razu na kozhnomu rivni dereva pri vstavlenni bud yakogo odnogo novogo zapisu Ce daye efekt viroblennya krashe klasterizovanih grup zapisiv u vuzlah sho zmenshuye pokrittya vuzliv Krim togo faktichni rozsheplennya vuzliv chasto vidkladayutsya v rezultati chogo serednya zapovnenist vuzla zrostaye Povtorne vstavlennya mozhna rozglyadati yak metod postupovoyi optimizaciyi dereva sho spracovuye pri perepovnenni vuzla Produktivnist red Pokrashena evristika rozsheplennya viroblyaye bloki sho ye blizhchimi do kvadratnih i vidtak krashimi dlya bagatoh zastosuvan Metod povtornogo vstavlyannya optimizuye nayavne derevo ale pidvishuye skladnist Diyevo pidtrimuye yak tochkovi tak i prostorovi dani odnochasno Diya riznih evristik rozsheplennya na bazi danih iz poshtovimi okrugami Nimechchini nbsp R derevo iz kvadratichnim rozsheplennyam Guttmana 2 Ye bagato blokiv yaki prostyagayutsya zi shodu na zahid po vsij Nimechchini i blokiv yaki silno perekrivayutsya Ce ne korisno dlya bilshosti zastosuvan sho chasto potrebuyut lishe nevelichkoyi pryamokutnoyi oblasti yaka peretinayetsya z bagatma smugami R derevo iz kvadratichnim rozsheplennyam Guttmana 2 Ye bagato blokiv yaki prostyagayutsya zi shodu na zahid po vsij Nimechchini i blokiv yaki silno perekrivayutsya Ce ne korisno dlya bilshosti zastosuvan sho chasto potrebuyut lishe nevelichkoyi pryamokutnoyi oblasti yaka peretinayetsya z bagatma smugami nbsp R derevo z linijnim rozsheplennyam Ana Tana 3 Hocha smugi j ne prostyagayutsya nastilki daleko yak v Guttmana problema smug zachipaye majzhe kozhen listkovij blok Listkovi bloki perekrivayutsya lishe trohi ale katalogovi bloki perekrivayutsya R derevo z linijnim rozsheplennyam Ana Tana 3 Hocha smugi j ne prostyagayutsya nastilki daleko yak v Guttmana problema smug zachipaye majzhe kozhen listkovij blok Listkovi bloki perekrivayutsya lishe trohi ale katalogovi bloki perekrivayutsya nbsp Topologichne rozsheplennya R dereva 1 Bloki perekrivayutsya duzhe malo oskilki R derevo namagayetsya minimizuvati perekrittya blokiv a povtorne vstavlennya dodatkovo optimizuye ce derevo Takozh strategiya rozsheplennya ne viddaye perevagu smugam otrimuvani v rezultati bloki ye nabagato korisnishimi dlya poshirenih kartografichnih zastosuvan Topologichne rozsheplennya R dereva 1 Bloki perekrivayutsya duzhe malo oskilki R derevo namagayetsya minimizuvati perekrittya blokiv a povtorne vstavlennya dodatkovo optimizuye ce derevo Takozh strategiya rozsheplennya ne viddaye perevagu smugam otrimuvani v rezultati bloki ye nabagato korisnishimi dlya poshirenih kartografichnih zastosuvan Algoritm ta skladnist red Dlya operacij zdijsnennya zapitiv ta viluchennya R derevo vikoristovuye toj zhe samij algoritm sho j zvichajne R derevo Pri vstavlyanni R derevo zastosovuye kombinovanu strategiyu Dlya listkovih vuzliv minimizuyetsya perekrittya todi yak dlya vnutrishnih vuzliv minimizuyutsya poshirennya ta plosha Pri rozsheplenni R derevo zastosovuye topologichne rozsheplennya yake obiraye vis rozsheplennya na osnovi perimetru a potim minimizuye perekrittya Na dodachu do vdoskonalenoyi strategiyi rozsheplennya R derevo takozh namagayetsya unikati rozsheplen povtorno vstavlyayuchi ob yekti ta piddereva do dereva pid nathnennyam ideyi balansuvannya B dereva Takim chinom skladnist zapitu ta viluchennya u najgirshomu vipadku ye identichnimi do R dereva Strategiya vstavlyannya do R dereva z O M log M displaystyle mathcal O M log M nbsp ye skladnishoyu za strategiyu linijnogo rozsheplennya O M displaystyle mathcal O M nbsp R dereva ale mensh skladnoyu nizh strategiya kvadratichnogo rozsheplennya O M 2 displaystyle mathcal O M 2 nbsp dlya rozmiru bloka v M displaystyle M nbsp ob yektiv i maye neznachnij vpliv na zagalnu skladnist Zagalna skladnist vstavlyannya zalishayetsya porivnya nnoyu z R derevom povtorne vstavlennya zachipaye shonajbilshe odnu z gilok dereva i vidtak O log n displaystyle mathcal O log n nbsp povtornih vstavlen porivnya nno do vikonannya rozsheplennya na zvichajnomu R derevi Otzhe v cilomu skladnist R dereva ye takoyu zh yak i v zvichajnogo R dereva Realizaciya povnogo algoritmu musit vrahovuvati bagato mezhovih vipadkiv ta vuzkih situacij ne obgovorenih tut Primitki red a b Beckmann N Kriegel H P Schneider R Seeger B 1990 The R tree an efficient and robust access method for points and rectangles Proceedings of the 1990 ACM SIGMOD international conference on Management of data SIGMOD 90 s 322 ISBN 0897913655 doi 10 1145 93597 98741 Arhiv originalu za 17 kvitnya 2018 Procitovano 19 bereznya 2016 angl Guttman A 1984 R Trees A Dynamic Index Structure for Spatial Searching Proceedings of the 1984 ACM SIGMOD international conference on Management of data SIGMOD 84 s 47 ISBN 0897911288 doi 10 1145 602259 602266 Arhiv originalu za 9 bereznya 2016 Procitovano 19 bereznya 2016 angl Ang C H Tan T C 1997 New linear node splitting algorithm for R trees U Scholl Michel Voisard Agnes Proceedings of the 5th International Symposium on Advances in Spatial Databases SSD 97 Berlin Germany July 15 18 1997 Lecture Notes in Computer Science 1262 Springer s 337 349 doi 10 1007 3 540 63238 7 38 angl Posilannya red Vikishovishe maye multimedijni dani za temoyu R derevoBiblioteki sho mistyat R dereva Dokumentaciya rtree Boost Geometry C Dokumentaciya paketu R tree ELKI Arhivovano 19 kvitnya 2014 u Wayback Machine Java Biblioteka prostorovogo indeksuvannya Arhivovano 14 serpnya 2014 u Wayback Machine C Modul R tree SQLite Arhivovano 25 lipnya 2014 u Wayback Machine C Biblioteka TPIE Arhivovano 12 zhovtnya 2014 u Wayback Machine C Otrimano z https uk wikipedia org w index php title R derevo amp oldid 35711721