Средства и методы ускорения дедуктивного вывода в информационных системах с большим объемом данных Катериненко, Роман Сергеевич

Введение к работе

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

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

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

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

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

этой цели были поставлены и решены следующие задачи:

1. Анализ результатов, полученных по основным направлениям исследований ускорения дедуктивного вывода методом «снизу вверх», с целью выявления особенностей и принципов построения алгоритмов;

2. Разработка и исследование алгоритма дедуктивного вывода на основе бинарных диаграмм решений;

3. Экспериментальное исследование производительности дедуктивного вывода на задаче с практической сложностью;

4. Разработка алгоритма дедуктивного вывода на основе модели баз данных с вертикальной архитектурой.

Научная новизна работы.

4. 1. Разработан алгоритм представления произвольного отношения в виде бинарной диаграммы решения, обладающий линейной сложностью от количества кортежей в отношении;

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

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

   Основные положения, выносимые на защиту:

   4. 3. 1. Алгоритм преобразования произвольного отношения в бинарную диаграмму решений;

         2. Алгоритм дедуктивного вывода с применением бинарных диаграмм решений;

         3. Метод верификации систем отслеживания задач с помощью дедуктивного вывода;

         4. Метод дедуктивного вывода на основе модели баз данных с вертикальной архитектурой.

         Практическая значимость. Основные результаты работы внедрены в проведенном в НИУ ИТМО НИР №610481 «Разработка методов и средств системотехнического проектирования информационных и управляющих вычислительных систем с распределенной архитектурой» кафедры ВТ. Разработанное программное обеспечение для верификации систем отслеживания задач внедрено в производственный процесс «ООО Системи Сершіо.

         Степень достоверности и апробация результатов исследования. Система на основе разработанного алгоритма дедуктивного вывода получила диплом конкурса научно-исследовательских проектов студентов и аспирантов НИУ ИТМО «The Big Bang — 2» (2013 г.). Основные положения диссертационной работы представлялись и обсуждались на 13-ти международных и всероссийских конференциях: «Майоровские чтения» (2009 г., Санкт-Петербург); XLVIII Международная научная студенческая конференция «Студент и научно-технический прогресс» (2010 г., Новосибирск); 12th IACEE World Conference On Continuing Engineering Education (2010 г., Сингапур); Всероссийская конференция «Управление знаниями и технологиями Semantic-Web» (2010 г., Санкт- Петербург); VII Всероссийская конференция Молодых Ученых (2010 г., Санкт- Петербург); XXXIX научная и учебно-методическая конференция СПбГУ ИТМО (2010 г., Санкт-Петербург); VIII Всероссийская межвузовская конференция Молодых Учены,х (2011 г., Санкт-Петербург); Конгресс по интеллектуальным системам и информационным технологиям (2011 г., Дивноморское); Международная конференция KMSW-2011 «Управление знаниями и технологии Semantic Web» (2011 г., Санкт-Петербург); IX Всероссийская межвузовская конференции Молодых Ученых (2012 г., Санкт-Петербург); Международная научно-практическая конференция «Инженерия знаний и технологии Semantic Web» (2012 г., Санкт-Петербург); 5ая Российская мультиконферен- ция по проблемам управления. Конференция «Информационные технологии в управлении» (2012 г., Санкт-Петербург); XLII Научная и учебно-методическая конференция (2013 г., Санкт-Петербург).

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

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

         трудов конференций.

         Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка. Общий объем диссертации 90 страниц. Библиография включает 91 наименование. Работа содержит 26 иллюстраций и 4 таблицы.

         Похожие диссертации на Средства и методы ускорения дедуктивного вывода в информационных системах с большим объемом данных

         

         Разработка и исследование методов создания компьютерной системы интеллектуальной поддержки решения задач физической химии в объеме университетского курса Цветников Вадим Александрович

         Разработка и исследование алгоритмов и программных средств визуализации объемовМельман, Сергей Владимирович

         

         Методы и средства поддержания целостности баз данных в доменно-ориентированных информационных системах Киселев Андрей Владимирович

         Методы и средства автоматизации построения полных систем тестов программУртанс, Гунтис Брониславович

         Методы и средства оптимизации геометрических характеристик оптических резонаторов газовых лазеровШевченко, Василий Геннадьевич

         Методы и средства параллельной высокоточной арифметики на базе систем вертикальной обработкиВаженин, Александр Павлович

         Разработка и исследование методов и средств измерения реляционных программМатвеева, Тамара Олеговна

         Методы и средства экспериментального проектирования архитектуры ЭВМ и микропроцессоровМарчук, Александр Гурьевич

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

         Методы и средства автоматического проектирования программ по операторным термамЧичиков, Александр Викторович