Гімадеев Сергей Вікторович

Тема: Методи та алгоритми оптимізації доступу до просторових даних в СУБД HBase

Содержание:

1. Мета та завдання
2. Актуальність
3. Наукова новизна
4. Плановані практичні результати
5. Огляд геоінформаційних систем
6. Системи розподіленого зберігання і обробки даних
7. Математичні методи розв'язання задачі
8. Висновок
9. Література

Мета та завдання

Типові завдання інтелектуального аналізу просторових даних включають кластеризацію, класифікацію та визначення трендів. Основна відмінність між отриманням знань в звичайних базах даних і в просторових – це те, що атрибути сусідів певного просторового об’єкта мають вплив на сам цей об’єкт. Тому алгоритми вилучення знань з просторових даних сильно залежать від ефективності процесу визначення ставлення сусідства для будь-якого просторового об’єкта. Операція визначення ставлення сусідства між просторовими об’єктами вимагає багато обчислювального часу. Простий алгоритм пошуку сусідніх об’єктів має обчислювальну складність, так як необхідно переглядати всі пари об’єктів. Таким чином, метою роботи є аналіз проблеми актуальності даних генеруються в ГІС, а також виявлення методів і алгоритмів, за допомогою яких можна ефективно індексувати просторові дані [1].

Актуальність

Останнім часом з’являється велика кількість інформаційних систем генеруючих просторові дані. Такі системи зазвичай називають геоінформаційними системами (ГІС). Це такі системи як сенсорні мережі, системи дистанційного зондування Землі, супутниковий моніторинг транспорту. Все це говорить про те, що кількість та обсяги просторових баз даних будуть продовжувати швидко рости. Інтелектуальний аналіз цих даних може дати багато корисної інформації про реальний фізичний світ і допомогти у вирішенні своїх завдань експертам таких предметних областей як екологія, землеустрій, муніципальне управління, транспорт, економіка і багатьох інших.

Наукова новизна

Наукова новизна полягає у використанні кодів Мортона і деревоподібної структури даних такий, як дерево квадрантів, які дозволять індексувати просторові об’єкти для їх подальшої обробки. Такий підхід повинен забезпечити високу продуктивність в розподілених системах використовують СУБД HBase.

Заплановані практичні результати

За допомогою даної роботи передбачається отримати рішення проблеми індексації просторових даних одержуваних з геоінформаційних систем.

Огляд геоінформаційних систем

Істотною відмінністю ГІС від інших інформаційних систем з просторовою локалізацією даних є включення в опис просторових об'єктів топологічних характеристик і класифікація на цій основі просторових об’єктів на: точкові, лінійні і майданні (ареальні). Тимчасової аспект, як правило, включає три фактори довготривалий, середньо тимчасовий і оперативний. З цим аспектом пов’язана характеристика якості інформації – актуальність і процедура актуалізації даних. За тимчасової характеристики інформація, що зберігається і ДПС, звичайно підрозділяється на:
• довгострокову (десятки років зберігання);
• середньострокову (роки);
• річну та сезонну;
• оперативну.
Однак тимчасової аспект даних в ГІС визначається і класом вирішуваних завдань. Наприклад, в більшості ГІС оперативне і визначається від одного тижня до двох-трьох тижнів. У спеціальних ГІС (військова розвідка, аналіз надзвичайних ситуацій) оперативність може становити хвилини. Тематична інформація в ГІС не обмежена. Саме це створює можливість використання ГІС як універсальної інформаційної системи для вирішення різноманітних завдань. Мало того, саме тематична інформація є основною, в той час як просторова інформація служить сполучною ланкою для об’єднання, зіставлення, пошуку та інтерпретації різноманітної тематичної інформації. У більшості технологій ГІС для визначення місця використовують два класи даних: один клас – позиційні (координатні) дані, другий клас – атрибутивні дані для визначення параметрів часу і тематичної спрямованості.

Системи розподіленого зберігання і обробки даних

Для роботи з великими обсягами даних останнім часом все активніше використовується розподілене зберігання і обробка. Причому спостерігається перехід від використання високопродуктивних мейнфреймів до кластерним системам, що складається з великого числа недорогих серверів з архітектурою x86-64 [2]. Після опублікування фірмою Google статей розкриває принципи зберігання та обробки даних, реалізовані їй для своїх сервісів [3, 4], з’явилися відкриті проекти, які реалізують ці принципи. Найбільш успішним з них на сьогоднішній день є проект Hadoop. Hadoop є вільним Java фреймворком, що підтримує виконання розподілених додатків, що працюють на великих кластерах, що об’єднують звичайні сервера під управлінням відкритої операційної системи Linux. Для розподіленого зберігання даних використовується файлова система Hadoop Distributed File System (HDFS), яка є відкритим аналогом Google File System (GFS). Поверх цієї файлової системи працює СУБД HBase, яка є аналогом СУБД BigTable від Google [3]. В Hadoop реалізована обчислювальна парадигма, відома як MapReduce [4]. Згідно цій парадигмі додаток поділяється на велику кількість невеликих завдань, кожне з яких може бути виконано на будь-якому з вузлів кластера. Всі ці технології дозволяють досягти дуже високої агрегованої пропускної здатності кластера. Ця система дозволяє додаткам легко масштабуватися до рівня тисяч вузлів і петабайт даних. Тому розробку просторових індексів ми будемо виконувати для СУБД HBase.

Математичні методи розв’язання задачі

Для побудови просторового індексу пропонується використовувати структуру даних дерево квадрантів (quadtree). Дерево квадрантів – це деревовидна структура даних, в якій кореневої і кожен внутрішній вузол має чотири дочірніх вузла [4]. Ця структура даних була розроблена спеціально для розбивки двовимірного простору за допомогою рекурсивного поділу його на чотири квадранта (рис. 1).

Рисунок 1 – Принцип використання дерева квадрантів

Рисунок 2 – Індексація просторових об’єктів, розбивка на блоки

Корінь дерева ділить область на 4 квадранта СВ, СЗ, Пд, Пд (відповідно до карти). Кожен рівень дерева квадрантів вимагає два біти коду Мортона. Для кодування географічних координат ми пропонуємо використовувати код довжиною 64 біта. Так як географічні координати Землі варіюються від -90° до 90° по широті і від -180° до 180° по довготі 64-х бітний код Мортона дозволить ставити координати з точністю аж до сьомого знака після коми в десятковому поданні градусів. Коди Мортона були обрані завдяки простоті розрахунку номера осередку по геометричних координатах. Просторові бази даних оперують такими двовимірними геометричними об’єктами як точка, ламана лінія і багатокутник. Точка в двовимірному просторі представляється двома географічними координатами: довготою і широтою. Розглянемо алгоритм визначення коду Мортона для координат точки в двовимірному просторі: Для того, щоб отримати код Мортона для вузла містить точку, досить перевести індекси x і y в бінарне подання, після чого побудувати нове число, по черзі беручи по одному розряду з двійкового подання кожного числа [5, 6]. Розглянемо тепер більш складний випадок, коли індексується просторовий об’єкт, представлений ламаної або багатокутником. Будь двовимірний об’єкт може бути замінений описаним прямокутником (bounding box) [7, 8] з деякою втратою точності. Це дозволяє спростити розрахунки і значно збільшити швидкість обробки просторових запитів. Використання цього підходу є звичайною практикою при побудові індексів просторових даних. Таким чином, довільний двовимірний об’єкт при індексації представляється у вигляді описаного прямокутника. Дерево квадрантів має властивість адаптивності. Це означає. Що просторові об’єкти можуть індексуватися вузлами різного рівня. Все залежить від площі індексуємого об’єкта. Якщо індексується точка, то використовується вузол нижнього рівня (рис. 2, рис. 3). Якщо ж індексується об’єкт представлений прямокутником, то посилання на нього записується у вузол, розмір якого мінімально перевищує розмір цього прямокутника [1].

Рисунок 3 – Індексація просторових об’єктів, деревоподібна структура

Взаємний вплив між просторовими об’єктами визначається топологічним ставленням, відстанню та напрямком між об’єктами. Для визначення топологічних відносин між двома просторовими об’єктами A і B зазвичай використовуються такі предикати [9, 10]:
• equals – об’єкт A збігається з об’єктом B;
• disjoint – об’єкт A просторово розділений з об’єктом B;
• intersects – об’єкт A перетинається з об’єктом B;
• touches – об’єкт A стикається з об’єктом B;
• crosses – об’єкт A просторово схрещується з об’єктом B;
• within – об’єкт A знаходиться всередині об’єкта B;
• contains – об’єкт A містить об’єкт B;
• overlaps – об’єкт A частково просторово перекриває об’єкт B.
Детальний опис цих предикатів можна знайти в стандарті Open Geospatial Consortium (OGC) [10]. Крім топологічних відносин, між просторовими об’єктами існують відносини напряму (наприклад, об’єкт A знаходиться на північ від об’єкта B). Для завдання відносини напрямки при розробці індексів ми використовували англомовні вирази: south, southwest, west, northwest, north, northeast, east, southeast і any_direction. Відстань між двома просторовими об’єктами задається речовим числом. Об’єкти вважаються сусідніми, якщо відстань між ними не перевищує деякий заданий значення. В індексних таблицях разом з топологічним ставленням і відношенням напрямку ми будемо зберігати відстань між об’єктами [11]. Для зменшення розміру індексного таблиці необхідно забезпечити можливість завдання максимальної відстані між об’єктами, при якому вони будуть вважатися сусідніми. Ця відстань може бути константою, або залежати від площ індексованих об’єктів [1].

Висновок

В результаті роботи був проведений аналіз геоінформаційних систем, виявлено основні їх недоліки у плані індексування та вилучення просторових даних. Для вирішення даної проблеми був розроблений метод індексації просторовий даних в СУБД HBase.

Література

1. А. Телятников, С. Гімадеев, Індексація просторових даних для прискорення їх інтелектуального аналізу, ISDMCI ′2011 / Матеріали міжнародної наукової конференції. Євпаторія, ХНТУ, 2011, с. 317–321.
2. Gartner. Gartner Predicts Video Telepresence Will Replace 2.1 Million Airline Seats Per Year by 2012. http://www.gartner.com/it/page.jsp?id=876512.
3. Chang F., Dean J., Ghemawat S., et al. Bigtable: a distributed storage system for structured data. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation – Volume 7 (OSDI '06), Vol. 7. USENIX Association, Berkeley, CA, USA, 15.
4. Dean J., Ghemawat, S. Mapreduce: simplified data processing on large clusters. Commun. ACM, January 2008, 51:107–113 pp.
5. Morton G.M. A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM Ltd., Ottawa, Ontario, Mar. 1966.
6. Larsson, Thomas, and Tomas Akenine-Moller, Collision Detection for Continuously Deforming Bodies, Eurographics 2001.
7. Samet H. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990.
8. Finkel R., Bentley J.L. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica 4 (1): 1–9 pp., 1974.
9. Ester M., Kriegel H.-P., Sander J. Knowledge Discovery in Spatial Databases, invited paper at 23rd German Conf. on Artificial Intelligence (KI '99), Bonn, Germany, 1999.
10. Cormen, T.H., C.E. Leiserson, and R. Rivest, Introduction to Algorithms, MIT Press, Inc., Cambridge, Massachusetts, 1990.
11. Yiwei Wu, Yingshu Li, Distributed Indexing and Data Dissemination in Large Scale Wireless Sensor Networks, http://www.cs.gsu.edu/yli/papers/icccn09.pdf.