Моделирование пространственно-временных структур данных: достижения и проблемы

Размещено на http://www.allbest.ru/

УДК 004.422.63

Моделирование пространственно-временных структур данных: достижения и проблемы

В.К. Гулаков

Е.О. Трубаков

А.П. Болдырев

Б.Г. Кеглин

Аннотация

Рассмотрены общие принципы работы пространственно-временных структур данных по индексированию движения мобильных объектов. Описаны отличительные особенности различных структур данных, достижения и проблемы в их применении. Даны рекомендации по дальнейшему развитию этих структур.

Ключевые слова: пространственно-временные структуры данных, индексы, системы мониторинга, мобильные объекты, методы доступа.

Вступление

Последние годы работы в области пространственно-временных структур данных ведутся достаточно интенсивно. Количество публикаций различного уровня составляет более тысячи. Интерес к этим структурам определяется следующими факторами:

1. Большинство объектов реальной жизни существует в динамических системах, соответственно применение пространственно-временных структур здесь актуально.

2. Существует большое количество достаточно сложных задач, в которых необходимо применение пространственно-временных структур данных. Сюда можно отнести:

· системы реального времени;

· мониторинг динамических объектов в САПР, на транспорте, в медицине и т.д.

3. Возможность хранить и обрабатывать огромные объемы пространственно-временных данных и прогнозировать динамические параметры мобильных объектов (например, пространственное положение и др.).

Эффективность различных известных структур, как правило, определяется для конкретной задачи. В практическом применении существенное значение имеют скорость обработки пространственно-временных данных и память, требуемая для хранения информации.

Целью настоящей работы является системный анализ существующих пространственно-временных структур данных для решения различных задач, связанных с изменением положения динамических объектов, выявление специфических проблем, касающихся их практического применения, и выработка некоторых рекомендаций.

1. Общая классификация существующих пространственно-временных структур

Сегодня известно более сотни пространственно-временных структур данных. Но каждая из них разрабатывалась для решения конкретных задач, и применение этих же структур в других задачах невозможно или затруднительно. Для повышения эффективности работы систем с динамическими объектами структуры данных должны учитывать как можно больше особенностей их применения (например, отсутствие произвольного движения, т.е. движение в фиксированных сетях). Благодаря этому возникла некоторая их классификация.

Первым основным параметром пространственно-временных структур является наличие оси времени в данных. По временному параметру структуры данных и их назначение можно разделить на следующие группы:

· структуры, отражающие прошлые состояния объектов, т.е. изменения их траектории;

· структуры, отражающие текущее положение объектов с возможностью прогнозирования их ближайшего будущего;

· структуры, отражающие всю временную ось, т.е. изменения траектории, текущее положение и прогнозирование будущего.

Структуры первой группы могут использоваться для создания различных отчетов, статистик, долгосрочных прогнозов и для других целей. Ввиду данной специфики возникает проблема минимизации объемов данных, так как на сервер в каждый момент времени для обработки приходит огромное количество информации. Вторая проблема заключается в скорости сохранения истории. Если система не будет успевать сохранять данные, то они будут попросту утеряны.

Вторая группа не имеет возможности сохранять историю, но имеет инструментарий для оперативного обновления данных и построения прогнозов на ближайшее будущее. В этой группе структур проблема скорости обработки данных также остается. Это связано с тем, что в системе мониторинга может быть огромное количество объектов и они могут передавать свои данные с малым промежутком времени. Задержки в обработке данных могут приводить к катастрофическим последствиям (например, в системах мониторинга передвижения самолетов или поездов).

Структуры третьей группы включают в себя все плюсы и минусы первых двух групп, поэтому их разработка является наиболее затруднительной.

Вторым основным параметром пространственно-временных структур данных является пространство. По этому параметру все структуры делятся на индексы с поддержкой произвольного движения и индексы с поддержкой движения в фиксированных сетях [1-4]. По сути, структуры индексирования произвольного движения могут проводить обработку данных движения и в сетях, но учет факта ограничения движения повышает эффективность работы структуры в частности и системы в целом.

Структуры индексирования траектории перемещения объектов. Рассмотрим пространственно-временные структуры, входящие в группу, решающую только задачи хранения и обработки исторической информации, - структуры индексирования траектории перемещения объектов.

Первыми попытками индексирования истории пространственно-временной информации являлись многомерные индексы и их модификации, такие как RT-дерево [34], 3D R-дерево [32] и др. Достоинством применения данных структур является простота их реализации и наличие уже зарекомендовавших себя алгоритмов повышения эффективности работы как индекса, так и системы мониторинга в целом. В качестве примера можно привести алгоритмы уплотнения дерева или распараллеливания обработки запросов и другие. В данных структурах не предусмотрен специализированный пространственно-временной инструментарий, поэтому они применяются только в низко-нагруженных системах, таких как мультимедиа-приложения, небольшие системы проектирования и другие. Некоторые из подобных структур использовались и в системах мониторинга движения транспорта (например, STR-дерево [25]). Повышение нагрузки на систему привело к тому, что разработчики отказались от их использования и перешли к более эффективным структурам (MTSB-дерево [36], MON-дерево [8] и др.).

Ряд приложений (например, кадастровые службы) в основном обрабатывают пространственные запросы. Характерной для таких систем является длительность интервала времени с отсутствием изменения в объектах. Для подобных систем наиболее удобно использовать такие структуры, как MR-дерево [34], HR-дерево [21] и др. Основным достоинством подобного рода структур является использование пространственного индекса как основного. В этом случае временной параметр данных добавляется как ось и для каждого интервала строится отдельное пространственное дерево. Такой подход к индексированию данных удобен в системах с запросами по временному срезу (пространственными запросами в определенный момент времени). Однако эффективность обработки запросов интервалов времени достаточно низка. Для того чтобы обрабатывать преимущественно такие запросы, удобно использовать такие структуры, как MV3R-дерево [29] или GS-дерево [17].

С развитием навигационных технологий стали появляться системы с топологическими запросами (запросами, направленными на траекторию движения объекта). Для подобных систем были разработаны такие структуры, как TB-дерево [25], SETI [5] и др. Также разрабатывались и системы с особенным кругом практических задач. Например, Polar-дерево [23] решает вопросы, связанные с ориентацией движения и её изменением. Другим примером служит CSE-дерево [35], которое используется в web ГИС. Особенностью подобных систем является тот факт, что траектория загружается сразу вся целиком, а не по точкам, как это происходит при её построении.

Структуры индексирования текущего положения объектов. Часть систем мониторинга движения объектов осуществляют наблюдение за их текущим положением. Среди них есть те, которые применяются в приложениях, где данный аспект является критичным (например, авиационные системы мониторинга). Первоначально количество объектов было не таким высоким, как в последнее время, поэтому системы мониторинга текущего положения объектов создавались на основе пространственного индекса. В последнее время количество объектов в системах возросло, и как следствие возникла необходимость в более совершенных системах. Тогда были разработаны ленивые алгоритмы обработки запросов обновления данных. Подобные системы используют LUR-дерево [15], RUM-дерево[33], FUR-дерево[16] и др.

Кроме ленивых алгоритмов древовидных структур были разработаны и другие подходы к решению проблемы увеличения скорости обработки запросов текущего положения объектов. Примером может служить пространственно-временное хеширование [28]. Особенность данного подхода заключается в том, что в структуре данных хранится приближенное значение параметров. Точное же значение сохраняется в другой структуре и используется лишь для уточнения результатов обработки запросов.

С целью повышения эффективности работы индекса исследователи стараются учесть как можно больше особенностей применения. Например, при движении объектов в фиксированных сетях наиболее удобно разделить статическую (дорожную сеть) и динамическую (изменение положения объектов) части в различные структуры, тем самым сократив объемы информации для обработки. Такой подход применяется в структуре данных IMORS [13].

Индексирование текущего положения и прогнозирование будущего. При обработке запросов прогнозирования ближайшего будущего положения объектов исследователи усовершенствовали пространственный индекс PMR-квадродерево [31], добавив в него вектор скорости. Таким образом, было найдено решение вопроса о создании прогнозов.

С развитием компьютерных технологий появилась возможность размещать весь индекс целиком в оперативной памяти. Тогда была разработана структура данных MOVIES [10]. Но основной принцип обработки запросов прогнозирования остался прежним.

Так как для каждого из измерений необходимо создавать отдельный прогноз изменения параметра, то системы с большим количеством параметров обрабатывают подобные запросы дольше. Поэтому вскоре при разработке структур данных стали применять различные способы сокращения количества измерений (SFC-трансформация [26], двойственная трансформация [14] и др.). Примерами таких структур могут быть STRIPES [22], ST²B-дерево [7], группа индексов, основанных на B-дереве, и др.

Другой принцип сокращения количества измерений данных - объединение объектов в группы по значению характеристик движения и использованию пространственного индекса с учетом параметра времени (параметризованные структуры данных). В качестве примеров подобных структур можно привести TPR-дерево [27], TPR*-дерево [30], ANR-дерево [6] и др.

Структуры обобщенного индексирования. При решении конкретных задач исследователи столкнулись с необходимостью обрабатывать всю временную ось. История перемещения обрабатывается для составления отчетов и анализа различного рода ситуаций. Мониторинг текущего состояния объектов сигнализирует об изменении положения или о возможных опасных ситуациях. Прогнозирование будущего положения объектов необходимо для предотвращения нежелательных последствий работы системы. В качестве примера систем с такими требованиями можно привести железнодорожные системы мониторинга движения поездов. Примером структуры, используемой в таких системах, является PPFI [11] и др.

Для систем мониторинга объектов с произвольным направлением движения (без ограничений) разработана структура PCFI+-индекс [20]. Для высоконагруженных систем (с большой частотой обновления данных или большим количеством объектов) предпочтительней использовать STCB+-дерево [19] и др.

Часть ранее разработанных структур получили новое применение благодаря их развитию. Такими структурами стали: UTR-дерево[9], основанное на MON-дереве [8], R^PPF-дерево [24], основанное на TPR-дереве, BB^x-индекс [18], основанный на B^x-дереве [12], и др.

2. Применение пространственно-временных структур данных

Приложений пространственно-временных систем мониторинга на данный момент очень много. Это связано с тем, что многие данные, которыми человек вынужден оперировать, имеют свойство изменяться с течением времени. Рассмотрим основные направления применения и выявим их наиболее актуальные проблемы.

Системы управления базами данных. Часто встречаются случаи использования баз данных для хранения пространственно-временных данных. Как правило, используются общие методы проектирования баз данных и разработки приложений. Если не учитывать специфику пространственно-временных данных, то система, как правило, работает неэффективно. Примером могут служить системы мониторинга движения товаров по складам и между ними: какой товар, откуда прибыл и где он сейчас находится. Сложность обработки подобного рода информации является достаточно высокой, поэтому возникает необходимость использования пространственно-временных структур.

Геоинформационные системы (ГИС). Данное приложение наиболее часто использует пространственно-временные структуры. В подобных системах могут возникать достаточно сложные запросы: поиск оптимального маршрута движения для машин экстренных служб с учетом текущей загруженности автодорог, управление графиком движения общественного транспорта, поиск ближайших соседей относительно мобильного объекта, поиск объектов в заданном регионе и интервале времени и многие другие запросы.

Системы проектирования (САПР). В системах проектирования необходимо проводить не только отображение сложных деталей, но и просчет изменения их параметров с учетом движения и взаимодействия с другими деталями. Для этих целей и нужны пространственно-временные структуры данных.

При использовании этих структур в системах проектирования возникают проблемы сохранения историй движения сложных объектов и прогнозирования их поведения с учетом огромного количества параметров (прогнозирование движения объектов, состоящих из множества деталей).

Мультимедийные системы. Одним из примеров являются охранные системы. Проблема работы подобных систем заключается в выявлении необходимого объекта в видеоряде и дальнейшем сохранении его траектории перемещения.

Искусственный интеллект. В данной области основной проблемой применения является прогнозирование протекания процессов и связь одних объектов с другими (интеллектуальные транспортные системы, управляющие потоком движения с помощью светофоров).

Службы сотой связи. В сотовых компаниях подобные структуры применяются с целью повышения качества обслуживания. Ввиду количества объектов, участвующих в системе мониторинга, основной проблемой становится объем информации для хранения и обработки.

Медицина. Многие медицинские параметры имеют свои оси и направления изменения. Таким образом, появляется возможность подменить привычное географическое понятие пространства пространством параметров. Тогда траектория является историей изменения некоторой характеристики. Поэтому анализ траекторий может быть полезным для наблюдения за пациентом.

Рассмотренные применения являются частью большого множества приложений пространственно-временных структур.

3. Анализ существующих проблем

Количество приложений, работающих с пространственно-временными данными, достаточно велико, но они являются узкоспециализированными. Универсальной пространственно-временной структуры данных нет. С появлением новых задач потребность в эффективных методах индексирования только возрастает. Рассмотрим наиболее общие проблемы, возникающие перед исследователями пространственно-временных структур данных.

Проблема чрезмерных объемов информации при индексировании исторических данных. Развитие спутниковых технологий, минимизация размеров устройств позиционирования и развитие сопутствующих направлений - всё это привело к тому, что количество объектов в системах мониторинга за последние годы резко возросло. Так, в настоящее время в системах мониторинга воздушного пространства отслеживаются одновременно десятки тысяч объектов. Другим примером могут быть системы мониторинга движения объектов железнодорожного транспорта. В этих системах количество объектов возрастает до сотен тысяч. Примером высоконагруженной системы является мобильная связь. Объекты, в свою очередь, постоянно изменяют пространственное положение, т.е. информация на сервере постоянно устаревает. Возникает потребность в её хранении с целью дальнейшего анализа и обработки. На текущий момент наблюдается удешевление аппаратной составляющей, но объемы данных так высоки, что возникает потребность в их минимизации на структурном уровне, т.е. на уровне пространственно-временных структур данных.

Как следствие возникает проблема обработки исторической информации за приемлемое время. Поэтому задача минимизации количества данных является более важной и сложной, чем проблема организации хранилищ.

Решения этой задачи на сегодняшний день нет, но можно выделить два основных приема, используемых разработчиками систем мониторинга движения объектов. Ключевым моментом одного из них является преобразование непрерывного потока времени в дискретный вид, т.е. разделение всей временной оси на интервалы. По истечении очередного интервала времени объект посылает на сервер данные о своих параметрах. Таким образом, сокращается объем непрерывного потока информации. Получаемые данные представляются в виде многомерных точек, которые в дальнейшем интерполируются. Точность полученной траектории изменения параметров зависит от выбранного размера временного интервала. При таком подходе точность и детализация данных снижается, но в ряде случаев это является допустимым.

Второй прием минимизации данных заключается в использовании законов движения объектов. Зная начальные параметры движения (пространственное положение и вектор скорости) и используя закон движения (например, прямолинейный), можно вычислить текущее положение объекта. Сохранение данных в системе необходимо лишь в том случае, если произошло их изменение. В связи с погрешностью данных необходимо выбирать некоторое пороговое значение для параметров, при превышении которого данные отправляются на сервер. От размера этого порога и зависит количество данных, т.е. их точность: чем меньше порог, тем чаще данные будут поступать в систему.

Минимизация исторической информации, её хранение и обработка является одной из самых существенных задач, стоящих перед исследователями структур данных и разработчиками систем мониторинга объектов. Как правило, именно вокруг этой проблемы и сосредоточены различные подходы к индексированию траектории перемещения объектов.

Проблема получения актуальной информации в высоконагруженных системах. Объектов, участвующих в системе мониторинга, может быть достаточно много. Интенсивность поступления данных также может быть высокой. Как следствие на сервер приходит огромное количество информации, которую необходимо обработать. Часть приложений также требуют её отображения и немедленного реагирования на критические изменения. В случае использования низкоэффективных структур данных в системах мониторинга может возникнуть ситуация задержки обновления текущих данных (информация будет неактуальной или же просто потеряется). Подобные случаи являются весьма критичными в некоторых сферах применения. Например, в системах мониторинга воздушного пространства объекты могут двигаться с очень большими скоростями, и любые задержки системы могут привести к катастрофам.

Для решения данной проблемы необходим глубокий анализ существующих узких мест и новые концептуальные подходы. Анализ существующих структур данных выявил, что наиболее дорогостоящей операцией является процедура обновления данных. Это связано с тем, что в структуре необходимо найти устаревшие данные, затем их удалить, после чего провести нормировку индекса и только потом вставить новые данные и повторить нормировку структуры. Шаг нормировки может привести к перестроению всего индекса, т. е. занять длительный промежуток времени. С учетом того, что в высоконагруженных системах большое количество запросов на обновление данных, становится понятно, почему эти сервисы сталкиваются с проблемой актуальности текущих пространственно-временных данных.

Для сокращения вычислительной сложности процедуры обновления данных разработано несколько подходов. Один из них заключается в разделении поступающих данных на статические и динамические. Например, в системах мониторинга движения объектов в фиксированных сетях можно выделить сеть, по которой происходит движение, и заранее её проиндексировать, тем самым снизив нагрузку на систему при обработке запроса на обновление данных. Данный принцип применяется в большинстве структур, где допускается движение только по фиксированным сетям (автомобили, железнодорожный транспорт, речной транспорт и т.д.). Из примера видно, что учет особенностей применения структуры повышает эффективность её работы. Поэтому разработчики систем мониторинга стараются учесть как можно больше особенностей работы системы.

Другим подходом к оптимизации работы индекса является использование ленивых алгоритмов. Идея работы алгоритма ленивого обновления данных состоит в следующем. Пусть в систему пришли данные о новом положении объекта. Эти данные запоминаются, но их обновления в индексе не происходит. И только при следующем обращении к этим данным происходит их обновление.

Другим вариантом ленивого обновления является пакетное обновление. В данном случае происходит сбор данных в некоторый так называемый пакет (блок, соответствующий участку памяти или узлу структуры). В дальнейшем обновление данных происходит путем вставки всего пакета за одно обращение к структуре.

Кроме шага вставки данных в индекс, шаг удаления данных может приводить к перестроению индекса. Поэтому и для этой операции существуют ленивые алгоритмы - «сборщики мусора». При использовании данного алгоритма в структуре данные помечаются как устаревшие, но самого удаления не происходит. В дальнейшем при снижении интенсивности использования индекса или с определенной периодичностью происходит запуск процедуры непосредственного удаления устаревших записей. Благодаря данному подходу снижается нагрузка на систему в момент её интенсивного использования.

Проблема прогнозирования пространственного положения мобильных объектов. В ряде приложений имеется задача по составлению прогнозов положения объектов в ближайшем будущем. Примерами таких приложений могут быть авиационные или железнодорожные системы мониторинга.

Для составления прогнозов будущего положения объекта необходимо сохранять его текущее положение и вектор изменения параметров. Увеличиваются объемы хранимой информации, но основная проблема состоит не в этом. Вся сложность составления прогнозов заключается в качестве данных о самом объекте и местности, по которой происходит движение. При составлении прогноза необходимо учитывать большое количество параметров, например характер движения объектов и внешние факторы, влияющие на него (автомобиль попал в пробку; человеческий фактор). Также стоит учитывать топологические факторы местности, например повороты дорог, светофоры, различного рода знаки дорожного движения и многое другое.

Ввиду многообразия и сложности факторов, влияющих на качество прогноза, унифицировать подходы к его составлению достаточно сложно. Поэтому при разработке системы мониторинга необходимо в первую очередь исследовать область применения и выявлять наиболее важные факторы, после чего создавать такой инструмент, который позволит наиболее полно учитывать особенности работы системы.

Поддержка специализированных запросов. При разработке пространственно-временной системы мониторинга движения мобильных объектов кроме основных задач, перечисленных выше, необходимо решать круг задач, специфичных для той или иной области. Например, в сфере составления прогноза погоды объекты имеют размеры, поэтому структуры данных, взаимодействующие с точечными объектами, в этом случае не могут быть использованы.

Также стоит учитывать временные интервалы обновления данных и интервалы, на которые направлена основная часть запросов. Например, в кадастровой службе планы застройки местности изменяются не столь быстро, как в системах мониторинга движения автотранспорта. Другим примером могут служить системы, направленные на обработку топологических запросов (запросов, связанных с траекторией движения).

Так или иначе, для решения всех проблем невозможно выработать единый подход. Каждая задача требует индивидуального анализа и поиска методов решения.

4. Перспективы развития

Все объекты реального мира находятся в некотором пространстве. Также с течением времени объекты склонны изменяться. Следует учитывать интервал времени изменения - для одних объектов это годы, а для других секунды. В зависимости от решаемой задачи эти изменения могут быть более или менее важны, т.е. ими можно или нельзя пренебречь. Если они значимы, то встаёт вопрос о мере их значимости в определённых интервалах пространства и времени.

Второй аспект задач с пространственно-временными данными - объём хранимых и обрабатываемых данных и структура их хранения, т.е. эффективность обработки этих данных в больших задачах.

Несмотря на огромное количество приложений пространственно-временных структур данных и интенсивное развитие этого направления исследований, в информационных технологиях по-прежнему остаются проблемы, требующие решения. Также следует учитывать, что с развитием информационного общества изменяются и требования к системам. Например, количество объектов в системах мониторинга может резко увеличиться буквально за несколько лет (так произошло в службах сотой связи). Другим аспектом, требующим разработки новых структур данных, может быть изменение требований к решаемым задачам (повышение надежности системы или добавление нового круга задач, которые снижают эффективность работы текущей структуры данных). Необходимо учитывать тот факт, что из-за особенностей сфер применения почти для каждой задачи разработчики вынуждены предлагать новый метод доступа к пространственно-временным данным. Таким образом, решение проблем научного направления исследований пространственно-временных структур данных по-прежнему остается актуальным.

Итак, нами проведена систематизация структур хранения и обработки пространственно-временных данных. Показано, что область применения таких данных достаточно обширна и постоянно растет. Системный подход позволит разработчикам различных систем, работающих с пространственно-временными данными, осознанно выбирать эффективные структуры. Тщательный анализ выявил не только существующие проблемы, но и те, которые могут возникнуть в перспективе.

временной мобильный индексирование

Список литературы

1. Гулаков, В.К. Использование многомерных деревьев для обработки многомерной информации / В.К. Гулаков, А.О. Трубаков, Е.О. Трубаков // Вестн. БГТУ.-2007. - №3. - С. 46-54.

2. Гулаков, В.К. Пространственно-временные модели данных для геоинформационных систем позиционирования движущихся объектов в ограниченных сетях / В.К. Гулаков, Е.О. Трубаков // Энергетика, информатика, инновации-2011: сб. тр. Междунар. науч.-техн. конф. - Смоленск: РИО филиала ГОУ ВПО «МЭИ(ТУ)» в г. Смоленске, 2011. - Т.2. - С.226-229.

3. Трубаков, Е.О. Разработка пространственно-временной модели данных и программного обеспечения для систем мониторинга движения железнодорожных объектов / Е.О. Трубаков // Материалы III Региональной научно-практической конференции молодых исследователей и специалистов «Проведение исследования по приоритетным направлениям современной науки для создания инновационных технологий» / под ред. И.А. Лагерева. - Брянск: БГТУ, 2011. - С.36-38.

4. Трубаков, Е.О. Применение темпоральных структур данных в системах мониторинга и планирования движения железнодорожных объектов / Е.О. Трубаков // Материалы III Международной научно-практической конференции «Достижения молодых ученых в развитии инновационных процессов в экономике, науке, образовании» / под ред. И.А. Лагерева. - Брянск: БГТУ, 2011. - Ч. 1. - С.210-212.

5. Chakka, V. Indexing Large Trajectory Data Sets with SETI / V. Chakka, A. Everspaugh, J. M. Patel // In Conference on Innovative Data Systems Research. - 2003.

6. Chen, J.-D. Indexing future trajectories of moving objects in a constrained network / J.-D. Chen, X.-F. Meng // J. Comput. Sci. Technol. - 2007.-№22(2). - P.245-251.

7. Chen, S. ST2B-tree: A self-tunable spatio-temporal B+-tree index for moving objects / S. Chen, B. Ooi, K. Tan, M. Nascimento // In SIGMOD. - 2008. - P.29-42.

8. De Almeida, V.T. Indexing the trajectories of moving objects in networks / V. T. De Almeida, R. H. Guting // Geoinformatica. - 2005. - №9(1). - P.33-60.

9. Ding, Z. UTR-tree: An index structure for the full uncertain trajectories of network-constrained moving objects / Z. Ding // In MDM. - 2008. - P.33-40.

10. Dittrich, J. Indexing moving objects using short-lived throwaway indexes / J. Dittrich, L. Blunschi, M. A. Vaz Salles // In SSTD. - 2009. - P.189-207.

11. Fang, Y. Indexing the past, present and future positions of moving objects on fixed networks / Y. Fang, J. Cao, Y. Peng, L. Wang // In CSSE. - 2008. - P.524-527.

12. Jensen, C. Query and update efficient B+-tree based indexing of moving objects / C. Jensen, D. Lin, B. Ooi // In VLDB. - 2004. - P.768-779.

13. Kim, K.-S. Fast indexing and updating method for moving objects on road networks / K.-S. Kim, S.-W. Kim, T.-W. Kim, K.-J. Li // Web Information Systems Engineering Workshops. - 2003. - P.34-42.

14. Kollios, G. On Indexing Mobile Objects / G. Kollios, D. Gunopulos, V. J. Tsotras // In Proc. of the ACM Symp. on Principles of Database Systems, PODS. - 1999. - P.261-272.

15. Kwon, D. Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree / D. Kwon, S. Lee, S. Lee // In Mobile Data Management, MDM. - 2002. - P.113-120.

16. Lee, M. Supporting Frequent Updates in R-Trees: A Bottom-Up Approach / M. Lee, W. Hsu, C. Jensen, B. Cui, K. Teo // In Proc. of the Intl. Conf. on Very Large Data Bases, VLDB. - 2003. - P.608-619.

17. Le, T. T. T. Efficient search of moving objects on a planar graph / T. T. T. Le, B. G. Nickerson // In GIS. - 2008. - P.1-4.

18. Lin, D. Efficient indexing of the historical, present, and future positions of moving objects / D. Lin, C. Jensen, B. Ooi, S. ЎSaltenis // In MDM. - 2005. - P.59-66.

19. Lin, H. Indexing the trajectories of moving objects / H. Lin // In Intl. MultiConf. of Engrs. and Computer Scientists. - 2009. - P.732-737.

20. Liu, Z.-H. Indexing large moving objects from past to future with PCFI+-index / Z.-H. Liu, X.-L. Liu, J.-W. Ge, and H.-Y. Bae // In COMAD. - 2005. - P.131-137.

21. Nascimento, M.A. Towards historical R-trees / M. A. Nascimento, J. R. O. Silva // In Proc. of the ACM Symp. on Applied Computing, SAC. - 1998. - P.235-240.

22. Patel, J. STRIPES: An efficient index for predicted trajectories / J. Patel, Y. Chen, V. Chakka // SIGMOD. - 2004. - P.635-646.

23. Patroumpas, K. Monitoring orientation of moving objects around focal points / K. Patroumpas, T. Sellis // SSTD. - 2009. - P.228-246.

24. Pelanis, M. Indexing the past, present, and anticipated future positions of moving objects / M. Pelanis, S. ЎSaltenis, C. Jensen // TODS. - 2006. - №31(1). - P.255-298.

25. Pfoser, D. Novel Approaches in Query Processing for Moving Object Trajectories / D. Pfoser, C. S. Jensen, Y. Theodoridis // In Proc. of the Intl. Conf. on Very Large Data Bases, VLDB. - 2000. - P.395-406.

26. Sagan, H. Space-Filling Curves / H. Sagan. - Berlin;Heidelberg;New York: Springer-Verlag, 1994. - 17p.

27. Saltenis, S. Indexing the Positions of Continuously Moving Objects / S. Saltenis, C. S. Jensen, S. T. Leutenegger, M. A. Lopez. // In Proc. of the ACM Intl. Conf. on Management of Data, SIGMOD. - 2000. - P.331-342.

28. Song, Z. Hashing moving objects / Z. Song, N. Roussopoulos // In Proceedings of 2nd International Conference of Mobile Data Management. - 2001. - P.161-172.

29. Tao, Y. MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. / Y. Tao, D. Papadias // In Proc. of the Intl. Conf. on Very Large Data Bases, VLDB. - 2001. - P.431-440.

30. Tao, Y. The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries / Y. Tao, D. Papadias, J. Sun // In Proc. of the Intl. Conf. on Very Large Data Bases, VLDB. - 2003. - P.790-801.

31. Tayeb, J. A Quadtree-Based Dynamic Attribute Indexing Method / J. Tayeb, O. Ulusoy, and O.Wolfson // The Computer Journal. - 1998. - №41(3). - P.185-200.

32. Theodoridis, Y. Spatio-Temporal Indexing for Large Multimedia Applications / Y. Theodoridis, M. Vazirgiannis, T. Sellis // In Proc. of the IEEE Conference on Multimedia Computing and Systems, ICMCS. - 1996. - P.441-448

33. Xiong, X. R-trees with update memos / X. Xiong, W. G. Aref // In ICDE. - 2006. - 22p.

34. Xu, X. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases / X. Xu, J. Han, W. Lu // In Proc. of the Intl. Symp. on Spatial Data Handling, SDH. - 1990. - P.1040-1049.

35. Wang, L. A flexible spatio-temporal indexing scheme for large-scale GPS track retrieval / L. Wang, Y. Zheng, X. Xie, W.-Y. Ma // In MDM. - 2008. - P.1-8.

36. Zhou, P. Close pair queries in moving object databases / P. Zhou, D. Zhang, B. Salzberg, G. Cooperman, G. Kollios // In GIS. - 2005. - P.2-11.

Материал поступил в редколлегию 24.06.13.

Размещено на Allbest.ru