Обо мне
Практика в Німеччині: Про IPVS Постановка задачі Про роботу
Ефективні індексні структури для аналізу просторових подій
У майбутньому в програмах надання інформації про навколишній стан бути потребувати точної інформації про позиції величезного числа мобільних об'єктів. Це вимагає створення систем локаційного керування, здатних справитися з великою кількістю таких понад динамічних даних. Для ефективного одержання актуальної інформації, наприклад, всіх об'єктів, що знаходяться в деякій визначеній області, ці системи повинні володіти адекватними індексними структурами. У минулому такі структури були вивчені тільки для геометричного представлення локаційної інформації. Однак, особливо в приміщенні, багато систем позиціювання базуються лише на символьних ідентифікаторах. Для здійснення можливості запитів в області, що базується на символьних ідентифікаторах, повинні моделюватися відносини просторового включення на базі деякої локаційної моделі. У сутності модель, що описує відносини включення між областями, може бути представлена як орієнтований ациклічний граф. Кожен вузол його представляє деяку область і кожне ребро - факт, що дочірня область просторово включена в батьківську область. У локаційній моделі, представленої таким чином, вузли самого нижнього рівня являють собою найбільший рівень розбивки областей. Це означає, що всі мобільні об'єкти, зареєстровані в моделі, розташовуються на цьому рівні.
Рисунок 1.
Тобіас Дроздол в своїй статьї "Ефективне індексування символічної локаційної інформації" представляє два підходи для ефективного індексування, що відображає дві головні операції - відновлення інформації про позицію/запит позиції і запит області. Наступна робота розглядає обробку просторових подій та базується на дослідженні, проведеному в статьї Тобиаса Дроздола.
Подія, що регіструється в моделі, повинна надавати наступну інформацію: тип події (заВходом - onEnter чи заВиходом - onLeave), область (її символічне представлення) і ідентифікатор слухача, що повинний одержувати повідомлення про подію. Два різних типи події приводять до створення двох карт інформації для їхнього збереження. Це збереження може бути реалізовано різними способами. З одного боку, при прив'язці події до області було б логічно зберігати подію безпосередньо у вузлі, що представляє дану область (далі - версія 2). З іншого боку, як було сказано раніше, усі мобільні об'єкти розташовуються на самому нижньому рівні, отже, можливі події також повинні відбутися на цьому рівні, що дає привід зберегти події в листах (далі - версія 1).
Версія 1
Збереження події у вузлах припускає прохід по дереву вниз до самого нижнього рівня для знаходження всіх дочірніх вузлів заданої області.
Рисунок 2.
Т.ч. ту саму подію доводиться зберігати кілька разів. Більш істотний недолік - це додатковий час, необхідний для перегляду дерева в пошуках необхідних листів. Однак такий підхід істотно полегшує відновлення інформації. Для виявлення події ми повинні порівняти стару і нову позиції мобільного об'єкта. Т.к. об'єкт рухається тільки на нижньому рівні і відповідні позиції також зберігаються тільки на нижньому рівні, для їхнього порівняння нам не потрібний прохід по дереву нагору. Якщо взяти до уваги факт, що відновлення інформації відбувається досить часто, розглянутий підхід значно заощаджує час. Тут важливо також пам'ятати про аналіз просторового включення областей.
Рисунок 3.
Рисунок 4.
Версія 2
Т.к. кожна подія асоціюється з деякою областю, було б логічним його збереження безпосередньо при цій області, виключаючи пошук нащадків.
Рисунок 5.
У цьому випадку ми виключаємо проблеми, що виникають при додаванні події в першому варіанті (збереження тієї самої події в декількох вузлах і прохід дерева в пошуках нащадків). Однак, ми одержуємо нові недоліки при відновленні інформації, а отже і при реєстрації подій.
Рисунок 6.
Розглянемо рисунок 6. Мобільний об'єкт переміщається з області J в область K. Червоними колами обведені вузли з зареєстрованими подіями. Можливі події заВходом можуть відбутися у вузлі K або в одному з його батьків, а заВиходом - у вузлі J або одному з його батьків. Т.ч. необхідний прохід по дереву для знаходження батьків обох вузлів. Пошук надає наступні результати: Батьки(J) = {J, E, B, A}, Батьки(K) = {K, G, C, A}. На цьому етапі варто врахувати просторові включення. Присутність вузла А в обох масивах насправді означає, що об'єкт не залишав і не входив у цю область, тобто події не могло відбутися. Т.ч. ми можемо виключити з розгляду вузол А, що залишає вузли J, E, B для аналізу події заВиходом і вузли K, G, C для події заВходом. Остаточний аналіз фіксує подію заВиходом у вузлі Е та заВходом у вузлі С.
Розглянутий приклад показує, що друга версія ускладнює відновлення інформації. Якщо врахувати факт, що такі відновлення відбуваються набагато частіше, ніж початкова реєстрації подій у моделі, то при рідких запитах області розглянутий підхід може стати занадто дорогим.
Інша можливість - комбінація обох варіантів, тобто використання деякої границі, що поділяє модель на дві частини, одна з яких буде розглядатися як перша версія, а робота з іншою буде проходити за другою версією.