R*-дерево

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

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

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

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

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

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

• Покращена евристика розщеплення виробляє блоки, що є ближчими до квадратних, і відтак кращими для багатьох застосувань.
• Метод повторного вставляння оптимізує наявне дерево, але підвищує складність.
• Дієво підтримує як точкові, так і просторові дані одночасно.

Дія різних евристик розщеплення на базі даних із поштовими округами Німеччини

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

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

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

Таким чином, складність запиту та вилучення у найгіршому випадку є ідентичними до R-дерева. Стратегія вставляння до R*-дерева з ${\displaystyle {\mathcal {O}}(M\log M)}$ є складнішою за стратегію лінійного розщеплення (${\displaystyle {\mathcal {O}}(M)}$) R-дерева, але менш складною, ніж стратегія квадратичного розщеплення (${\displaystyle {\mathcal {O}}(M^{2})}$) для розміру блока в ${\displaystyle M}$ об'єктів, і має незначний вплив на загальну складність. Загальна складність вставляння залишається порівня́нною з R-деревом: повторне вставлення зачіпає щонайбільше одну з гілок дерева, і відтак ${\displaystyle {\mathcal {O}}(\log n)}$ повторних вставлень, порівня́нно до виконання розщеплення на звичайному R-дереві. Отже, в цілому складність R*-дерева є такою ж, як і в звичайного R-дерева.

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

Примітки

1. 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 (PDF). с. 322. doi:10.1145/93597.98741. ISBN 0897913655. Архів оригіналу (PDF) за 17 квітня 2018. Процитовано 19 березня 2016. [Архівовано 17 квітня 2018 у Wayback Machine.] (англ.)
2. 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 (PDF). с. 47. doi:10.1145/602259.602266. ISBN 0897911288. Архів оригіналу (PDF) за 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*-дерева:

• Документація rtree Boost.Geometry (C++)
• Документація пакету R*-tree ELKI [Архівовано 19 квітня 2014 у Wayback Machine.] (Java)
• Бібліотека просторового індексування [Архівовано 14 серпня 2014 у Wayback Machine.] (C++)
• Модуль R*-tree SQLite [Архівовано 25 липня 2014 у Wayback Machine.] (C)
• Бібліотека TPIE [Архівовано 12 жовтня 2014 у Wayback Machine.] (C++)