Проект предполагает исследование задач, связанных с хранением и обработкой данных (в особенности текстовых и текстоподобных). Рост объема таких данных значительно опережает рост производительности компьютеров. При этом общее развитие информационных технологий диктует всё новые требования к обработке больших объёмов информации. Возникающий разрыв между желаниями и возможностями обработки данных порождает ряд как теоретических, так и практических вызовов. Проект предусматривает исследование структур хранения данных с возможностью быстрого поиска, доступа и выполнения других запросов. Подобные структуры называются индексами и включают в себя не только поисковые индексы (которые наиболее известны и тоже являются предметом наших исследований), но и другие индексы, использующиеся для различных задач обработки информации и построения систем информационного поиска. В данной теме достаточно много конкурирующих исследований. Будут рассмотрены как чисто теоретические задачи (установление пределов возможностей для алгоритмов и структур данных в соответствующих моделях вычислений), так и задачи, имеющие прикладное значение (новые виды индексных структур данных и алгоритмы поиска в них). Руководитель уже имеет успешный опыт работы в данной области, вылившийся в публикации высокого международного уровня. Ниже более подробно раскрыто содержание проекта.
Наиболее популярные классические индексы для поиска в неструктурированных данных, таких как коллекции геномов или файловые репозитории, основаны на суффиксных деревьях и, в особенности, на (разреженных) суффиксных массивах, повсеместно использующихся для решения подобных задач. Поскольку для многих приложений индексируемые данные настолько велики, что едва вмещаются в оперативную память, вопрос построения суффиксных массивов оказывается совсем непростым и классические алгоритмы становятся не применимы. В основе наиболее эффективных известных алгоритмов построения суффиксного массива в таких условиях лежит так называемый легковесный LCE индекс (от англ. Longest Common Extension), который позволяет сравнивать произвольные фрагменты индексируемых данных за близкое к константному время, при этом занимая незначительный объём памяти. Разработка легковесных LCE индексов интенсивно ведётся как минимум с 2010 года и последние работы, закрывающие вопрос для рандомизированного случая, вышли буквально в этом году в трудах престижной конференции SODA; руководитель проекта принял активное участие по этому направлении, по итогу опубликовав статью в известном международном журнале, в которой была определена точная оценка того, насколько быстрым в принципе может быть легковесный LCE индекс при заданных ограничениях на используемую память (именно на основе этой оценки можно судить о закрытии вопроса). В рамках проекта предполагается разработать детерминированный легковесный LCE индекс с близким к оптимальному временем построения и оптимальным временем работы. Ожидается, что опыт анализа LCE индексов руководителем позволит достигнуть такого результата. Непосредственным следствием этого результата будут улучшения алгоритмов детерминированного построения (разреженного) суффиксного массива и разреженного суффиксного дерева.
Суффиксное дерево - это стандартный индекс, применяющийся в огромном множестве задач поиска и анализа данных. В рамках проекта нас будет интересовать фундаментальная задача навигации по суффиксному дереву: определение по любому заданному фрагменту данных соответствующей ему позиции в дереве. Классически эта задача решается спуском из корня дерева, что занимает линейное время. В 2014 году был придуман индекс, который позволяет выполнять такие навигационные запросы за константное время, что явилось неожиданным для большинства исследователей в области. Этот индекс решает явно фундаментальную задачу в данной области и он уже успел найти ряд интересных приложений, но его широкому распространению мешает то, что его авторы не нашли для него линейного алгоритма построения. В проекте предполагается разработать модификацию этого индекса с теми же характеристиками и линейным алгоритмом построения.
В связи с растущими объемами обрабатываемых текстовых данных остро встает вопрос построения так называемых сжатых индексов, способных обеспечивать быстрый доступ к сжатым коллекциям текста, которые в противном случае не удалось бы за разумное время обрабатывать и осуществлять поиск в них. Подобные индексы не новы (первые относительно эффективные версии появились в начале 2000-х), но по-прежнему активно разрабатываются и совершенствуются многими международными научными коллективами, потому что для многих задач (например, обработки банков биологических последовательностей) мощностей существующих инструментов недостаточно. Современные сжатые индексы обычно представляют собой сложные математические конструкции, основанные на эффективно вычислимых комбинаторных преобразованиях - преобразовании Барроуза-Уилера, разложении Лемпеля-Зива и недавно открытых строковых аттракторах. В проекте предполагается разработать индексы, ориентированные преимущественно на так называемые сильно сжимаемые данные (базы данных систем контроля версий, базы схожих геномных последовательностей, файлы журналирования различных систем и так далее). Такие индексы вплоть до недавнего времени опирались либо на преобразование Барроуза-Уилера, либо на разложение Лемпеля-Зива; отметим, что руководитель активно и успешно работал над разработкой индексов как на основе первого, так и второго, и результаты этой работы опубликованы в ряде статей высокого международного уровня. Но буквально год назад вышла прорывная статья, в которой большинство таких индексов были обобщены с помощью нового понятия строковых аттракторов и индексов на их основе. В рамках проекта предполагается улучшить время поиска в этих новых индексах и эффективность занимаемой ими памяти, а также исследовать некоторые вопросы их оптимальности. Ожидается, что уже имеющийся у руководителя опыт разработки схожих индексов обеспечит выполнение этой цели.
В продолжение темы сжатых индексов, планируется изучить следующий вопрос: до сих пор нет никаких достаточно эффективных сжатых индексов для сильно сжимаемых данных, которые позволяли бы эффективно модифицировать эти данные, даже если такие модификации всего лишь добавляют новые куски ("документы" в обычной терминологии) в конец уже обработанных и индексированных данных. Такой особый тип модификаций особенно важен для многих приложений сжатых индексов. В проекте предполагается разработать сжатый индекс на основе строковых аттракторов с возможностью выполнения подобных модификаций.
В рассматриваемых направлениях исследования индексных структур данных у руководителя имеются результаты и публикации мирового уровня, что позволит активно конкурировать на международном уровне и обеспечит успешное выполнение проекта.
Результатами проекта будут математические модели, структуры данных, алгоритмы, а также теоретические и экспериментальные оценки их релевантности и эффективности. Результаты обеспечат дальнейший прогресс в области индексных структур, информационного поиска, а также будут применимы в некоторых практических приложениях.