Следите за нами

/// Эффективные методы поиска в последовательностях для больших баз данных

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

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

  • видео- и аудио-данные (записи систем видеонаблюдения, видеоролики пользователей в социальных сетях и др.);
  • программный код (системы контроля версий, автоматизированные проверяющие системы – например, созданная в Вологодском государственном техническом университете (ВоГТУ) и др.);
  • текст разной степени структурированности (простой текст, html, xml);
  • числовые последовательности в финансово-банковских системах и др.

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

  • по сходству;
  • по подмножествам;
  • по вхождению подпоследовательностей;
  • по регулярным выражениям и их часто применяемым подмножествам (подстрокам, LIKE-шаблонам).

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

Решаемые проектом задачи:

  1.  Определение способа декомпозиции исходных данных на минимальные индексируемые элементы, разработка структуры данных индекса.
  2. Разработка алгоритма начального построения индекса.
  3.  Разработка структур данных и алгоритмов построения и динамической модификации индекса при вставке/удалении записей, алгоритмов выборки данных.
  4. Адаптация структур и алгоритмов к условиям параллельной работы.
  5. Доказательство корректности, анализ сложности алгоритмов (в условиях вычислительной модели с внешней памятью).
  6. Получение экспериментальных результатов и их анализ.
  7. Внедрение полученных результатов в конкретную СУБД с открытым исходным кодом (PostgreSQL).
  8. Практическое применение полученных результатов.

Плюсы обобщенного индекса по сравнению с созданием специализированного индекса для каждого вида поиска:

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

Основные направления коммерциализации проекта

  1. Создание универсальной коммерческой библиотеки функций для интеграции с основными ведущими СУБД.
  2. Встраивание в корпоративные интранет-системы.
  3. Создание прикладных решений:
  • группировка похожих элементов (аудио, видео, текст), например системы распознавания лиц, нахождения плагиата и т.д.;
  • Встраивание в социальные сети (для таргетированной рекламы, data mining);
  • Мониторинг социальных медиа на предмет определения тенденций и скрытых закономерностей;
  • Здравоохранение — раннее обнаружение патологии в результатах цифровых исследований;
  • Прикладная наука (например, анализ спектров и т.п.), поиск и устранение избыточности в программном коде и т.д.

 

Copyright 2012-2017 Адрэм