|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Базы данных для хранения графовдипломная работа (Специалист)
- Научный руководитель: Шуткин Ю.С.
- Автор: Точинов Василий Игоревич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2015
- Аннотация: В работе исследуется задача поиска подграфов в базе данных графов. Причем графы рассматриваются неотмеченные. Классический алгоритм подразумевает полный перебор элементов базы данных, с последующим запуском алгоритма поиска подграфа в графе, что уже само по себе является экспоненциально сложной задачей относительно числа ребер в графе. Автором предлагается 2 способа ускорения алгоритма поиска. Первый – организация предварительной фильтрации элементов базы данных с помощью алгоритма полиномиальной сложности. Этот подход был ранее описан в литературе для случая отмеченных графов, и адаптирован автором для случая неотмеченных графов. Второй способ ускорения поиска заключается в предварительном подсчете характеристик графов из базы данных для более быстрой последующей фильтрации. Для каждого из графов из базы данных строится специальное дерево частично-упорядоченных путей графа, которое потом в процессе фильтрации комбинируется с аналогичным деревом для графа-запроса, что позволяет быстро отфильтровать неподходящие графы.
- Добавил в систему: Шуткин Юрий Сергеевич