Автореферат (Методы и средства эффективного выполнения сценариев аналитической обработки данных на основе оптимизации и приближенных вычислений)

На правах рукописиЯрыгина Анна СергеевнаМетоды и средства эффективного выполнения сценариеваналитической обработки данных на основе оптимизации иприближенных вычислений05.13.17 — теоретические основы информатикиАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата физико-математических наукСанкт-Петербург2015Работа выполнена в Санкт-Петербургском государственном университетена кафедре информационно-аналитических систем.Научный руководитель:Новиков Борис Асеновичдоктор физико-математических наук, профессорОфициальные оппоненты:Махортов Сергей Дмитриевичдоктор физико-математических наук, доцент(ФГБОУ ВО “ВГУ”, зав. кафедрой)Бакин Евгений Александровичкандидат технических наук(ФГАОУ ВО ГУАП, доцент)Ведущая организация:ЗащитанадиссертациизаседанииМГУ имени М.В.

Ломоносовасостоится“17”диссертационногоСанкт-ПетербургскогоСанкт-Петербург,мартасоветагосударственногоПетродворец,2016годаД212.232.51,университета,Университетскийпр.,в15час.30мин.созданногонабазепод.адресу:28,198504математико-механический факультет, ауд. 405.СдиссертациейГорькогоадресу:наможноознакомитьсяСанкт-Петербургского199034,сайтеСанкт-Петербург,вНаучнойгосударственногоУниверситетскаябиблиотекеим.университетанаб.,д.7/9поиhttp://spbu.ru/science/disser/soiskatelyu-uchjonoj-stepeni/dis-list/details/14/694.html.Автореферат разослан “”2016 года.Ученый секретарьдиссертационного совета Д212.232.51,доктор физико-математических наук,профессорМ.Демьянович Ю.

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

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

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

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

Растущий спрос на обработку боль3ших объемов данных за ограниченное время, а также современные методы анализа данных на основе подобия вызывают необходимость в приближенных вычислениях. Например, системы Blinkdb, Sciborq поддерживают приближенноепараллельное выполнение запросов в реальном времени, предоставляя пользователю статистические гарантии качества неточного результата.Значительная часть элементов традиционной архитектуры систем выполнения декларативных запросов, включая компиляцию в промежуточный алгебраический язык, оптимизацию и интерпретацию алгебраического выражения,требует пересмотра в контексте новых моделей данных, классов систем хранения и доступа, и вычислительных архитектур.Таким образом, современные проблемы анализа больших данных требуютсоздания методов и средств, обеспечивающих реализацию систем, которые позволят единообразно формулировать запросы к разнородным данным и описывать их обработку; реализуют эффективное выполнение сложных сценариеванализа данных на основе их оптимизации; и будут поддерживать приближенное выполнение запросов в реальном времени, то есть будут обеспечивать предсказуемое и контролируемое время ответа на запрос.Цельюисследования являлась разработка методов оптимизации дляприближенного выполнения сценариев нечеткого анализа данных.Для достижения цели были поставлены и решены следующие задачи:∙Разработать систему понятий и теоретическую модель оптимизации иконтролируемого приближенного выполнения нечетких запросов;∙Разработать методы решения задачи распределения ограниченного количества вычислительных ресурсов среди операций в плане приближенноговыполнения запроса;∙Предложить методы решения задачи многокритериальной оптимизациизапросов, допускающих приближенное выполнение, ориентированные наспецифические ограничения на количество вычислительных ресурсов икачество ответа.Положения, выносимые на защиту:∙Предложенасистемапонятий,составляющихтеоретическуюмодель,формализующую оптимизацию и контролируемое приближенное выполнение декларативных запросов, на основе модели стоимости и качестваопераций;∙Разработана математическая модель распределения ресурсов среди операций в плане выполнения запроса и решена задача выбора оптимальногораспределения;∙Разработан приближенный алгоритм распределения ограниченного количества вычислительных ресурсов среди операций в плане выполнениязапроса на основе моделей качества;4∙Разработаны алгоритмы бикритериальной оптимизации запросов, ориентированные на специфические в контексте приближенного выполнения,ограничения на количество вычислительных ресурсов и качество ответа.Методология и методы исследования.

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

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

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