Обо мне
Практика в Германии: О 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 для события поВходу. Окончательный анализ фиксирует событие поВыходу в узле Е и поВходу в узле С.
Рассмотренный пример показывает, что вторая версия усложняет обновление информации. Если учесть факт, что такие обновления происходят гораздо чаще, что начальная регистрации событий в модели, то при редких запросах области рассмотренный подход может стать слишком дорогостоящим.
Другая возможность - комбинация обоих вариантов, т.е. использование некоторой границы, делящей модель на две части, одна из которых будет рассматриваться как первая версия, а работа со второй будет проходить по второй версии.