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



страница1/10
Дата13.06.2018
Размер5,07 Mb.
  1   2   3   4   5   6   7   8   9   10
Федеральное государственное автономное образовательное учреждение
высшего образования


КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

ВЫСШАЯ ШКОЛА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И
ИНФОРМАЦИОННЫХ СИСТЕМ

Направление подготовки: 09.03.03 Прикладная информатика

Профиль: Прикладная информатика в экономике

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

ОПТИМИЗАЦИЯ ПОИСКА ПРОСТРАНСТВЕННЫХ ДАННЫХ В СИСТЕМЕ УЧЕТА РЕЗУЛЬТАТОВ АРХЕОЛОГИЧЕСКИХ ИССЛЕДОВАНИЙ

Работа завершена:

«___»_____________2017 г.

Студент группы 11-307 ___________________А. М. Хасанова

Работа допущена к защите:

Научный руководитель

Старший преподаватель Высшей школы ИТИС

«___»_____________2017 г. __________________В. В. Кугуракова

Директор Высшей школы ИТИС

«___»_____________2017 г. ___________________А. Ф. Хасьянов

Казань – 2017 г.

СОДЕРЖАНИЕ


ВВЕДЕНИЕ 3

1 СИСТЕМА ХРАНЕНИЯ ДАННЫХ В ARCHGIS 6

1.1 О системе ArcGIS 6

1.2 Модель данных ArchGIS 8

1.3 Neo4j 10

1.4 Ограничения системы хранения в ArchGIS 12

2 ОПТИМИЗАЦИЯ ПОИСКА ПРОСТРАНСТВЕННЫХ ДАННЫХ 13

2.1 Пространственный индекс 13

2.1 Типы структур для индексирования пространственных данных 14

2.3 R-tree 18

2.4 Построение пространственного индекса на основе R-tree 20

3 РЕАЛИЗАЦИЯ 21

3.1 Настройка работы Neo4j 21

3.2 Реализация с Neo4j Spatial 24

3.2.1 Настройка работы Neo4j Spatial 24

3.2.2 Создание слоя геометрических данных 25

3.2.3 Добавление узлов к слою геометрических данных 26

3.3 Результаты оптимизации 28

ЗАКЛЮЧЕНИЕ 31

ЛИТЕРАТУРА 34




ВВЕДЕНИЕ


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

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

Система учета результатов археологических исследований ArchGIS (http://185.147.81.8:8080/index) хранит данные о пространственных объектах. Сервис осуществляет поиск по расположению среди памятников, исследований, вскрытий, артефактов и объектов культурного наследия (ОКН) по их географическим координатам. Все хранящиеся в системе объекты – цифровые представления реального объекта – имеют пространственную привязку с указанием степени точности: точная субметровая, точная метровая, по крупномасштабной карте или снимку, по мелкомасштабной карте или абрису, по словесному описанию.

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

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

Проблема

Для дальнейшего развития и использования системы необходима оптимизация возможностей для пространственного анализа, а именно оптимизация алгоритма поиска среди объектов с пространственной привязкой.

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


  • Большое количество обращений к базе данных при выполнении запроса;

  • Превышение возможных объемов кэша при обработке данных;

  • Долгий отклик сервера;

  • Так называемые «подвисания» сервера и многочисленные ошибки;

  • Неудовлетворительная скорость выполнения запроса пользователя в целом.

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

Целью дипломной работы является решение проблемы неэффективного и неоптимального поиска по расположению на исходном наборе данных.



Задачи

Ставятся следующие задачи по решению проблемы:



  • Проанализировать особенности системы хранения данных в ArchGIS и выявить их «узкие» места;

  • Исследовать методы оптимизации поиска пространственных данных и выбрать наиболее оптимальное и эффективное решение для внедрения в исходную систему;

  • Внедрить решение.


1 СИСТЕМА ХРАНЕНИЯ ДАННЫХ В ARCHGIS

1.1 О системе ArcGIS


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

Система хранит и обрабатывает данные о следующих сущностях:



  • Объекты культурного наследия;

  • Археологические памятники (культурные слои);

  • Археологические комплексы (сооружения, погребения и пр.);

  • Артефакты;

  • Радиоуглеродные даты.

А также данные о полевых и аналитических исследованиях в области археологии и смежных наук, в том числе:

  • Данные о раскопах;

  • Отчеты о полевых исследованиях;

  • Опубликованные результаты исследований;

  • Архивные документы.

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

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

Имеющиеся в системе интерфейсы позволяют осуществлять:


  • Внесение, изменение и отображение хранящихся в ней данных;

  • Осуществление выборки данных из всей совокупности на основе атрибутов сущностей и связей между ними;

  • Картографическая визуализация любого выбранного массива данных, имеющих пространственную привязку;

  • Простейший статистический анализ.


1.2 Модель данных ArchGIS


Данные об объектах, представленных в ArchGIS имеют пространственную привязку и состоят в многоуровневых связях. Граф является наиболее оптимальной структурой для представления таких данных. Вершиной графа является пространственный объект или данные о нем, а ребром – отношение между ними. Граф дает визуальное представление, которое наиболее понятно описывает объекты реального мира.

Граф не имеет строгой фиксированной структуры. Он динамичен. И к вершинам, и ребрам можно добавлять атрибуты. Ребра графа могут быть ненаправленными. В графе поддерживается связь многих ко многим.



Элементы графа сгруппированы по сущностям, к которым относятся. Это позволяет вести поиск среди вершин не по всему графу, а внутри смысловых групп. Например, данные об ОКН (Monument), который относится к типу неукрепленное поселение (MonumentType), в БД представлены в связке вершин с наименованием и описанием ОКН (Knowledge), регионом нахождения (Region), эпохой, к которой ОКН относится (Epoch), а также прилагающимися к объекту исследованиями (Research) и пространственной привязкой (SpatialReference) (Рисунок 1).

Рисунок 1 – Визуализация данных об ОКН в виде графа

Все данные о пространственных объектах с вершинами состоят в непрерывной цепи. Каждое ребро имеет ссылку на предыдущую и следующую вершину. Поэтому для навигации по графу необходимо знать только вершину для начала поиска. Связанные вершины ссылаются друг на друга в базе данных, что позволяет выводить результаты с константным ростом сложности выполнения запроса O(1) [3].

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




Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   10


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница