Математическое и программное обеспечение представления и обработки данных о мобильных объектах в реляционных СУБД тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Альшаер, Джавдат Джамиль

• Альшаер, Джавдат Джамиль
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Альшаер, Джавдат Джамиль

ВВЕДЕНИЕ.

ГЛАВА 1. ОСОБЕННОСТИ ПРОСТРАНСТВЕННО-ВРЕМЕННЫХ СИСТЕМ.

1.1 Вводные замечания.

1.2. Система определения местоположения мобильных объектов

1.2.1. Принцип работы ГНС.

1.2.2. Точность определения координат.

1.3. Базы данных и системы управления ими.

1.4. Краткая характеристика мобильных объектов.

1.5. Поддержка пространственных объектов в современных РСУБД.

1.5.1. Хранение пространс твенных данных в БД и манипулирование ими.

1.5.2. Логическая структура БД, таблицы и индексы.

1.5.3. Физическая структура БД, файлы данных и индексов.

1.5.4. Обработка запросов, содержащих условия поиска записей, и методы ее оптимизации.

1.5.5. Индексирование пространственных данных для оптимизации операций над ними.

1.6. Анализ особенностей и проблем пространственно-временных систем.

1.6.1. Новые типы пространственно-временных запросов.

1.6.2. Нетрадиционные методы доступа и обработки: непрерывные запросы.

1.6.3. Неопределенности при обработке «неточных» данных.

1.7. Обзор существующих исследований об определении координат мобильных объектов.

3 1.7.1. Обзор существующих методов доступа к данным о мобильном объекте.

1.7.2. Существующая теоретическая модель представления мобильных объектов в БД.

1.7.3. Обзор существующих исследований по проблеме неточности определения координат МО.

1.8. Постановка задачи исследования.

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение представления и обработки данных о мобильных объектах в реляционных СУБД»

Актуальность темы. Любой существующий объект располагается где-нибудь и в какой-нибудь точке времени. В динамично развивающемся мире пространство является особенностью, которая изменяется с течением времени. За последние годы мобильность стала важным фактором человеческой жизни. Интернет, беспроводные сети, GPS технологии, мобильные телефоны и весь спектр услуг, предоставляемых с ними, совершенствуются с каждым днем. Все эти технологии стали доступны для разных слоев населения. Общей целью технологий и услуг является удовлетворение растущих ожиданий потребителей. Для достижения этой цели информация должна быть своевременно предоставлена в правильном месте. Сейчас предоставление услуг, соответствующих времени, стало очень важным и зависит от местонахождения потребителей мобильных устройств. Предоставление такого рода информации позволит потребителям устройств лучше ориентироваться в пространстве, чтобы получить необходимые услуги и определить возможные проблемы (например, дорожные пробки). Основной аспект в мобильности - объект, местоположение которого изменяется, т.е. мобильный объект (МО). В реальной жизни существует много приложений, которые используют этот аспект (городское движение, наблюдения миграций животных, анализ поведения покупателей (в торговых и городских центрах), местонахождение пациента в больнице, расположение таких услуг как туристические, рекламные, скорой помощи и т.д.). Несмотря на некоторый прорыв в удовлетворении спроса потребителей на информационное сопровождение таких услуг, при их создании все еще остается много нерешенных аспектов. Одним из таких аспектов является отсутствие стандартной базы данных (БД) для мобильных объектов и услуг. Универсальным средством для хранения структурированной информации являются базы данных, работающие под управлением систем управления базами данных (СУБД). Из них наибольшее распространение получили реляционные СУБД (РСУБД), которые обладают мощным декларативным языком описания запросов для поиска информации (SQL) и способны выполнять запросы, не предусмотренные изначально при создании структуры базы данных.

Для решения актуальных народнохозяйственных задач необходимо использование пространственных типов данных для описания расположения МО. Средства, применяемые для решения таких задач, должны предоставлять инструментарий для хранения пространственных данных и выполнения над ними поисковых и вычислительных операций. РСУБД, выбираемая в качестве универсального хранилища данных, требует серьезной доработки с целью поддержки работы с мобильной информацией и взаимодействия с другими информационными системами, обеспечивающими её визуальное представление.

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

Поэтому следует признать актуальными исследования в области решения задач наилучшего представления данных о МО в БД, создания для них СУБД для обработки сложных запросов, включающих запросы о местонахождении объектов в прошлые, настоящие или будущие интервалы времени, в том числе в условиях неточной информации о местоположении МО. Это и составляет предмет диссертационного исследования.

Цель и задачи исследования. Целью диссертационной работы является разработка и исследование модельного, алгоритмического и программного обеспечения для хранения и обработки данных о МО в реляционных СУБД.

Для достижения поставленной цели исследования необходимо решить следующие задачи:

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

2. Разработка и исследование методов, алгоритмов и моделей для представления данных и обработки запросов о непрерывных траекториях движения МО и нахождении объектов в заданных областях с помощью традиционных БД.

3. Разработка и исследование методов и средств для решения прогнозных задач вида: «Найти МО, которые возможно пересекут заданную область через определенный интервал времени».

4. Создание средств для имитационного исследования разработанного модельного и алгоритмического обеспечения и проведение такого исследования.

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

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

1. Алгоритм представления непрерывной траектории МО по дискретным точкам съёма координат, отличающийся минимизацией «мертвого (потерянного, не допускающего восстановления) пространства» путем уменьшения размеров параллелепипедов, аппроксимирующих отрезки траекторий МО, позволяющий с большей эффективностью осуществлять запись сведений о МО в БД.

2. Модель представления МО (МПМО) в БД, отличающаяся сочетанием векторного, статического, пространственного и динамического временного подходов. Оригинальность модели заключается в специальном разбиении координатного пространства на пространственную и временную составляющие, когда каждый МО имеет статическое и динамическое временное представление. МПМО состоит из: двухуровневого метода доступа, реализующего МПМО, отличающегося поддержкой всех типов запросов о прошлом и настоящем местонахождении МО и позволяющего уменьшить рост объема индексации путем избегания индексации повторяющихся траекторий МО и восстановления полной траектории МО. Это позволяет уменьшить объем требуемой для хранения данных об МО памяти до 30% и уменьшить время реализации запроса на 20-30 %; способа организации хранения сведений о мобильных объектах в БД, отличающегося использованием аппарата таблиц и индексов СУБД, элементами иерархической организации данных, существующими типами и операциями, и двухъярусной моделью обработки запроса в СУБД, что делает модель применимой с любыми СУБД.

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

4. Подсистема моделирования движения для обработки нетрадиционных запросов, включающая: метод обработки непрерывных запросов путем имитации положений МО с помощью модели синхронных клеточных автоматов. Это позволяет отслеживать перемещение МО на электронной карте местности в реальном времени; основанный на регрессионной модели метод предсказания будущих положений МО в условиях ограничения скорости движения, отличающийся отсутствием требования необходимости получения скоростей от объектов и учетом движения объектов относительно друг друга.

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

Практическая значимость результатов работы. Практическая значимость диссертационной работы заключается в обеспечении возможности использования дискретных реляционных СУБД для хранения и обработки информации о непрерывных траекториях мобильных объектов. Предложенная надстройка в типовых СУБД позволяет использовать их для решения разнообразных задач управления движением транспорта, отслеживать передвижения МО различного вида, контролировать состояние территорий. В предложенном подходе к построению индексов (И+-дерево для мобильных объектов, РПМО) достигнута более высокая эффективность реализации по сравнению с ранее применяемыми (Я+-дерево и Я-дерево). Например, размер индекса в рассмотренном примере составил 12Мб для РПМО-дерева против 51Мб для Я+-дерева и 38Мб для Я-дерева. При этом число опрашиваемых узлов при использовании предложенного РПМО-дерева примерно на 10-15% меньше чем при использовании К+-дерева и на 20-30% чем у Я-дерева. Отметим, что некоторые типы запросов ранее были невозможны в принципе. Предложенные алгоритмы реализованы в программном обеспечении «Система мониторинга мобильных объектов в транспортных сетях», переданном на госрегистрацию в Федеральный институт промышленной собственности (ФИПС).

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

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

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

Использование разработанного среднеквадратического регрессионного предсказания (СК-предсказания) дает больше достоверных результатов, чем кусочно-линейная модель в ТРБ1-дереве.

Разработанный автором комплекс вычислительных программ для обработки данных о мобильных объектах (КВПМО) является удобным инструментом при использовании поверх СУБД для обработки непрерывных запросов о МО и позволяет получать ответы на запросы в переносных устройствах пользователей.

Он может применяться для предсказания будущих местоположений объектов с использованием регрессии. Комплекс зарегистрирован в федеральном институте промышленной собственности (ФИПС), № 2009616597 от 27.11.09 г.

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

Реализация и результаты внедрения. Основные теоретические и практические результаты работы приняты к использованию в управлении пассажирских перевозок мэрии г. Новосибирска, сервисном центре Samsung г. Новосибирска, Jordan Telecom Group (Orange) г. Амман, Иордания, в учебном и научном процессе Новосибирского государственного технического университета (НГТУ) и Новосибирского государственного университета (НГУ).

Апробация результатов. Результаты, полученные в диссертационной работе, докладывались на научных конференциях:

Третьем международном форуме по стратегическим технологиям «IFOST» (Новосибирск, 23-29 июня, 2008 г.);

Десятом рабочем международном симпозиуме по информатике и информационным технологиям «CSIT2008» (Турция, Анталия, 15-17 сентября, 2008 г.);

Третьей всероссийской конференции «Винеровские чтения» (Иркутск: ГОУ ВПО ИрГТУ, 11-16 марта, 2009 г.);

Седьмой всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии» (Томск, ТПУ, 25-27 февраля, 2009 г.);

Пятнадцатой ежегодной международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, Электротехника и Энергетика» (Москва, МЭИ, 26-27 февраля, 2009 г.);

Восьмой международной сибирской конференции ШЕЕ по управлению и связи (81ВС01Ч-2009) (Томск, ТПУ, 27-28 марта, 2009 г.);

Всероссийской научной конференции молодых ученых (Новосибирск, НГТУ, 4-7 декабря, 2008 г.);

Всероссийских научно-практических конференциях «Научная инициатива иностранных студентов и аспирантов российских вузов» II и Ш (Томск, ТПУ, 27-28 апреля, 2008 г. и май 2009 г.), результаты диссертации отмечены дипломами на этих конференциях;

Четвертом международном форуме по стратегическим технологиям «ШОБТ» (г. Хошимин, Вьетнам, 21-23 октября, 2009 г.).

Публикации. По теме диссертации опубликовано 16 научных работ, в том числе: 2 - в изданиях, входящих в перечень рекомендуемый ВАК РФ, 3 - в рецензируемых журналах, 10 - в сборниках трудов конференций и зарегистрирована 1 программа.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, списка использованных источников и приложения. Полный объем составляет 148 страницы, включая 5 таблиц и 40 рисунков. Список использованных источников содержит 85 наименований. Кратко изложим основное содержание работы.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Альшаер, Джавдат Джамиль

4.4.2. Результаты исследования по размеру дерева и стоимости добавления

Чтобы решить первую задачу: сравнение размера РПМО-дерева, которое индексирует различные числа МО для г. Oldenbourg с размером 3-мерного R и Я+-деревьев, были генерированы различные размеры МО (0-2000) на основе цифрового представления реальной дорожной сети Oldenbourg. При этом использовался генератор мобильного объекта, как уже упоминалось в пункте 4.2.1. С использованием программного обеспечения имитации основных алгоритмов РПМО-дерева, R-дерева и R+дерева реализованного на Visual Basic, как уже упоминалось в пункте 4.21., были проиндексированы все траектории сети, затем каждая из трех созданных индексных структур сохранялась в файле в упакованном виде, и после чего вычислялся размер каждой структуры для различного числа МО.

Размер созданных индексных структур показан в табл. 4.2.

Заключение

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

1. Разработан новый алгоритм представления непрерывной траектории МО по дискретным точкам съёма координат.

2. Предложена модель представления МО (МПМО) в БД, обеспечивающая при ее реализации уменьшение объема требуемой для хранения данных об МО памяти до 30% и времени реализации запросов на 20-30 % по сравнению с ранее используемыми средствами.

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

4. Разработана подсистема моделирования движения для обработки нетрадиционных запросов, включающая реализацию метода обработки непрерывных запросов путем имитации положений МО с помощью модели синхронных клеточных автоматов и основанный на регрессионной модели метод предсказания будущих положений МО в условиях ограничения скорости движения.

5. Создан программный комплекс обработки данных о мобильных объектах (КВПМО) и специальные программные средства имитационного моделирования, с помощью которых проведена проверка работоспособности и оценена эффективность предложенных алгоритмов.

Список литературы диссертационного исследования кандидат технических наук Альшаер, Джавдат Джамиль, 2010 год

1. Андрианов В. Ю. Англо-русский толковый словарь по геоинформатике / В. Ю. Андрианов -М.: ДАТА+, 2001.-122 с.

2. Берлянт A.M. Геоинформационное картографирование. / А. М. Берлянт -М.: Астрея, 1997. 64 с.

3. Борисенков Д. В. Специальное математическое и программное обеспечение манипулирования распределенными объектами в реляционной СУБД на основе полигамических представлений : дис. . канд. тех. наук : 05.13.11 / Д.

4. В. Борисенков ; Воронежская государственная лесотехническая академия; науч. рук. В. Н. Харин. Воронеж, 2007. - 136 с.

5. Борисенков Д. В. Краткий обзор стандартов поддержки ГИС в реляционных СУБД и вариантов их реализации / Д. В. Борисенков, В. Н. Харин // Технология клиент-сервер. 2005. - №3. - С. 40^-5.

6. Боуман Дж., Эмерсон С., Дарновски М. Практическое руководство по SQL / Дж. Боуман, С. Эмерсон, М. Дарновски. М. : Издательский дом "Вильяме", 2001.-336 с.

7. Вахрамеева JI. А. Математическая картография : учебник / JI. А. Вахрамее-ва, JI. М. Бугаевский, 3. JI. Казакова. М. : Недра, 1986. - 285 с.

8. Геоинформатика : Толковый словарь основных терминов / Под ред. А. М. Берлянта, А. В. Кошкаревой. М. : ГИС-Ассоциация, 1999. - 204 с.

9. Грабер М. Справочное руководство по SQL / М. Грабер / Пер. с англ. М. : Лори, 1998.-291 с.

10. Дейт К.Дж. Введение в системы баз данных / К.Дж Дейт . 8-е изд. - М. : Вильяме, 2006. - 1328 с.

11. ДеМерс М. Географические информационные системы. Основы / М. Де-Мерс / Пер. с англ. М. : Дата+, 1999. - 491 с.

12. Дюбуа П. MySQL / П. Дюбуа / Пер. с англ. М. : Издательский дом "Вильяме", 2004.-1088 с.

13. Зикопулос П. DB2 версии 8: официальное руководство / П. Зикопулос, Дж. Бакларц, Д. Де Рус, Р. Мельник / Пер. с англ. М. : КУДИЦ -Образ, 2004. -380 с.

14. Кайт Т. Oracle для профессионалов. Архитектура, методики программирования и основные особенности версий 9i и 10g / Т. Кайт / Пер. с англ. М.: Издательский дом Вильяме, 2007. - 848 с.

15. Кимельман М. JI. Исследование и разработка языковой подсистемы SQL сервера : дис. .канд. физ.-мат. наук : 05.13.11 / М. J1. Киммельман ; Российская Академия Наук. Институт Системного Программирования; науч. рук. С С. Гайсарян. М., 1996. - 210 с.

16. Когаловский М. Р. Энциклопедия технологий баз данных / М. Р. Когалов ский. М. : Финансы и статистика, 2002. - 800 с.

17. Кодд Э. Ф. Реляционная модель для больших совместно используемых банков данных / Э. Ф. Кодд // Журнал СУБД. 1995 - №1. - С. 145-160.

18. Костенко Б. Б. История и актуальные проблемы темпоральных баз данных / Б. Б. Костенко, С. Д. Кузнецов // Труды Института системного программирования. М.: ИСП РАН, 2007. - Т.13, 4.2. - С. 77-114.

19. Мартин Дж. Организация баз данных в вычислительных системах / Дж. Мартин М.: Мир, 1980. - 211с.

20. Мобильная реляционная СУБД Линтер. Версия 6.1.: Справочник по SQL. -Воронеж : НПП Релэкс, 2007.- 190 с.

21. Нейл М. PostgreSQL. Основы / М. Нейл, Р. Стоунз / Пер. с англ. М. : Символ-плюс, 2003. - 400 с.

22. Норенков И. П. Основы автоматизированного проектирования / И.П. Но-ренков. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. - 336 с.

23. Селко Дж. SQL для профессионалов: программирование / Дж. Селко / Пер. англ. М. : Лори, 2004. - 456 с.

24. Цикритзис Д. Модели данных / Д. Цикритзис , Ф. Лоховски / Пер. с англ. -М.: Финансы и статистика, 1985. 344 с.

25. Шекхар Ш. Основы пространственных баз данных / Ш. Шекхар, С. Чаула / Пер. с англ. М.: КУДИЦ-Образ, 2004. - 336 с.

26. Adler D. W. IBM DB2 Spatial Extender Spatial Data within the RDBMS/ D. W. Adler // Proceedings of the 27th VLDB Conference, Roma, Italy : Morgan Kaufmann, 2001.- P.- 687-690.

27. Pagel B. U. Towards an analysis of range query performance in spatial datastructures / B. U. Pagel, H. W. Siax, H. Toben, P. Widmayer // The twelfth ACM

28. SIGACT-SIGMOD-SIGART symposium on Principles of database systems,

29. Washington, US : proceeding. ACM, 1993. - P. 214-221.

30. Basch J. Algorithms for reporting and counting geometric intersections / J.

31. Basch, L. J. Guibas, G. D. Ramkumar // IEEE Transactions on Computing.

32. Redwood City : CA, 1979. Vol. 28. - P. 643-647.

33. Bentley J. L. Data structures for range searching / J. L. Bentley , J. H. Friedman

34. Computing Surveys (CSUR).- US, New York : ACM, 1979. P. 397^09.

35. Brinkoff T. Generating Network-Based Moving Objects / T. Brinkoff // The12th Int'l Conference on Scientific and Statistical Database Management, Washington, USA, DC : IEEE Computer Society, 2000. P. 253-255.

36. Chen J. Modeling and Predicting Future Trajectories of Moving Objects in a

37. Constrained Network / J. Chen, X. Meng, Y. Guo, S. Grumbach, H. Sun // Proceedings of the 7th International Conference on Mobile Data Management

38. MDM 2006), Nara, Japan : IEEE Computer Society, 2006. P. 156.

39. Draper A. Applied Regression Analysis /A. Draper, R. Norman, V. Smith .

40. New York : John Wiley and Sons, Inc., 1998. P. 7-20.

41. Environmental Systems Research Institute, Inc. ESRI Shapefile Technical Description, 1997.

42. Erwig M. Spatio-temporal data types / M. Erwig, R. H. Guting, M. Schneider,

43. M. Vazirgiannis // An approach to modeling and querying moving objects in databases. Lisbon, Portugal : Geolnformatica, 1999. - Vol. 14. - P. 269-296.

44. Frentzos E. Indexing objects moving on fixed networks / E. Frentzos // Proc.8th Scientific and Statistical Database Management (SSDBM'00), Berlin, Germany : ACM, 2003. P. 289-305.128

45. Gaede V., Gunther О. Multidimensional access methods. Computing Surveys /

46. V. Gaede, 0. Gunther. New York : ACM, 1998. - P. 170-231.

47. Gruber M. SQL Instant Reference / M. Gruber. Alameda, Sybex: CA, 1993.352 p.

48. Guttman A. R-Trees: a Dynamic Index Structure for Spatial Searching / A.

49. Guttman // The ACM-SIGMOD Conference on the Management of Data, Boston, Massachusetts, US : proceeding. ACM Press, 1984. - P. 47-57.

50. Hadjieleftheriou M. Efficient indexing of spatiotemporal objects / M. G. Hadjieleftheriou, V. J. Kollios, D. Gunopulos // The 8th International Conference on

51. Extending Database Technology, London, UK : proceeding. Springer-Verlag,2002.-P. 251-268.59. http: // msdn.microsoft.com/library/(flaTa обращения: 20.10.2008).60. http://www.cnord.ru/0wa обращения: 20.08.2008).

52. International Business Machines Corp., Armonk, NY, USA. IBM DB2 Spatial

53. Extender and Geodetic Extender User's Guide and Reference, Version 8.2,2004.

54. International Business Machines, Corp. DB2 Spatial Extender. User's Guide and

55. Reference, Version 8.1, 2002.

56. Jensen D. Indexing of network constrained moving objects / D. Jensen, C. S.

57. Pfoser // Proceedings of the 11th ACM international symposium on Advances ingeographic information systems, Louisiana, New Orleans, USA : ACM, 2003. 1. P. 25-32.

58. Kollios G. On indexing mobile objects / G. Kollios , D. Gunopulos // Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Pennsylvania, Philadelphia, USA : ACM, 1999. P.261.272.

59. MySQL AB, Uppsala, Sweden. MySQL 5.0 Reference Manual, 2005.129

60. Nagel K. A cellular automaton model for freeway traffic / K. Nagel, M.

61. Schreckenberg // Journal Physique. 1992. -1 2.- P. 2221-2229.

62. Open Geospatial Consortium. Open GIS Geography Markup Language (GML)

63. Encoding Specification Implementation Specification, Revision 3.1.1, 2004.

64. Open Geospatial Consortium. OpenGIS Simple Features Specification for SQL,1. Revision 1.1,1999.

65. Oracle Spatial User's Guide and Reference: Oracle Corp., Redwood City :

66. CA, 2005. lOg Release 2 (10.2).

67. Oracle Spatial User's Guide and Reference: Oracle Corp., Redwood City : CA,2001.-Release 9.0.1.

68. Pfoser D. Novel approaches to the indexing of moving object trajectories / D.

69. Pfoser, C. S. Jensen, Y. Theodoridis // The 26th International Conference on

70. Very Large Databases, Egypt, Cairo : proceeding.- Morgan Kaufmann, 2000.1. P. 395^106.

71. Prasad S. Modeling and Querying Moving Objects / S. Prasad, W. Ouri, D. Son

72. Proc. of the 11th ACM international symposium on Advances in geographicinformation systems, New Orleans, Louisiana, USA: ACM, 2003. -P 118 125.

73. Saltenis S. Indexing the Positions of Continuously Moving Objects / S. Saltenis,

74. C. S. Jensen, S. T. Leutenegger, M. A. Lopez // Proc. 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas, USA :

75. SIGMOND, 2000. P. 331-342.

76. Sellis T. The R+ Tree: A Dynamic Index for Multi- Dimensional Objects / T.

77. Sellis, N. Roussopoulos, C. Faloutsos // Proc. 13rd International Conference on

78. Very Large Data Bases, Brighton, England: Morgsn Kaufmann, 1987. P.507518.130

79. Sistla A. P. Querying the uncertain position of moving objects / A. P. Sistla, O.

80. Wolfson, S. Chamberlain, S. Dao // In Temporal Databases: Research and Practice = LNCS, Redwood City : CA, 1998. Vol. 1399. - P. 310-337.

81. Slobodan R. A Trajectory Splitting Model for Efficient Spatio-temporal Indexing / R. Slobodan, S. Jarg, J. Elding, A. Nascimento // Proceedings of the 31st

82. VLDB Conference, Norway : VLDB Endowment, 2005. P. 934-945.

83. Szalay, A., Kunszt P., Thakar A., Gray J., Slutz D., and Brunner R. Designingand Mining Multi-terabyte Astronomy Archives : The Sloan Digital Sky Survey

84. Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas TX : ACM, 2000. P. 451-462.

85. Tao Y. The TPR*-tree: An optimized spatial-temporal access method for predictive queries / Y. Tao, D. S. Papadia, J. Sun // Proc. Int. Conf. on Very Large

86. Data Bases, Berlin, Germany: Morgan Kaufmann, 2003. P. 790-801.

87. The PostgreSQL Global Development Group. PostgreSQL 8.1.0 Documentation, 2005.

88. Theodoridis Y. Spatial Temporal Indexing for Large Multimedia Applications

89. Y. Theodoridis, M. Vazirgiannis, T. Sellis // The 3rd IEEE Int'l Conference on

90. Multimedia Computing and Systems, Hiroshima, Japan: IEEE Computer Society, 1996. P. 441^48.

91. Trajcevski G. Managing uncertainty in moving objects databases / G. Trajcevski, O. Wolfson, K. Hinrichs, S. Chamberlain // Database Syst., New York, USA :

92. ACM, 2004. Vol. 3. - P. 463-507.

93. Trajcevski G. The Geometry of Uncertaintyin Moving Objects Databases / G.

94. Trajcevski, O. Wolfson, F. Zhang, S. Chamberlain // London, UK : Springer1. Verlag, 2002. P. 233-250.

95. Tzouramanis T. Overlapping Linear Quad Trees for Spatio-temporal Data / T.

96. Tzouramanis, M. Vassilakopoulos, Y. Manolopoulos // In Proc. 4th East

97. European Conf. on Advanced Databases and Information Systems(ADBIS-DASFAA2000), Prague, Czech Republic : Springer-Verlag, 2000. P.279-292.

98. Teixeira D. A. Supporting Uncertainty in Moving Objects in Network Databases / D. A. Teixeira, R.H. Guting // International Workshop on Geographie Information Systems, Bremen, Germany : ACM, 2005. P. 31-40.

99. Wolfson O. Updating and querying databases that track mobile units / O. Wolf-son , A. P. Sistla, S. Chamberlain, Y. Yesha // Distributed and Parallel Databases, Netherlands : Kluwer Academic Publishers, 1999. Vol. 3. - P. 257-387.