КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер 20-71-00050

НазваниеИндексные структуры данных

РуководительКосолобов Дмитрий Александрович, Кандидат физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Уральский федеральный университет имени первого Президента России Б.Н. Ельцина", Свердловская обл

Период выполнения при поддержке РНФ

07.2020 - 06.2022

Конкурс№49 - Конкурс 2020 года «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными.

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-715 - Системы текстового поиска

Ключевые словасуффиксное дерево, сжатые структуры данных, разложение Лемпеля-Зива, наибольший общий префикс, LCE

Код ГРНТИ20.53.19

СтатусУспешно завершен

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

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

Ожидаемые результаты
Предполагается разработать ряд новых индексов и алгоритмов их построения: (1) легковесный LCE индекс с улучшенным детерминированным временем построения, (2) навигационный индекс на суффиксном дереве с линейным временем построения, позволяющий по фрагменту данных находить за константное время соответствующую позицию в дереве, (3) сжатый индекс на основе строковых аттракторов с улучшенной оценкой памяти и временем выполнения поиска, (4) инкрементальный алгоритм построения сжатого индекса на основе строковых аттракторов, (5) реализация полученных сжатых индексов и легковесного LCE индекса. Разработка алгоритма (1) немедленно повлечёт за собой улучшение оценки времени конструирования суффиксного массива в условиях ограниченной памяти - ключевой и наиболее трудоёмкой для построения структуры во многих поисковых индексах на неструктурированных данных (часто применяющейся, например, в биоинформатие). Ожидается, что получение результата (2) будет способствовать распространению новой фундаментальной структуры данных - навигационного индекса на суффиксном дереве и, тем самым, улучшению оценок на время выполнения в ряде алгоритмов и структур. Особенностью индекса (3) и соответствующего ему алгоритма (4) будут низкое потребление памяти; в настоящее время чувствуется недостаток в таких алгоритмах и сжатых индексах для, например, коллекций геномных данных: такие данные из-за их размера невозможно приемлемо сжимать существующими методами, потребляющими слишком большой объем памяти. Естественным шагом после разработки описанных индексов и алгоритмов является (5) их реализация и тестирование. Надеемся, что программная реализация полученных систем в тестах проявит себя значительно лучше существующих решений и, тем самым, появится сильный стимул к дальнейшей работе по внедрению. Также ожидается, что полученные алгоритмы найдут применение в других более широких областях, связанных с хранением, доступом и редактированием коллекций из систем контроля версий, журналов работы приложений, текстовых коллекций социальных сетей и т.д. По всем перечисленным задачам ведутся активные исследования различными группами и отдельными исследователями в мире и результаты по ним публикуются в трудах ведущих международных конференций и в престижных журналах.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Аннотация результатов, полученных в 2020 году
В рамках первого года реализации проекта получен ряд новых результатов, перечисленных далее. Все они связаны с хранением и обработкой данных (в особенности текстовых и текстоподобных), рост объема которых значительно опережает рост производительности компьютеров. Исследуются структуры хранения данных с возможностью быстрого поиска, доступа и выполнения других запросов. Подобные структуры называются индексами и включают в себя не только поисковые индексы (которые наиболее известны и тоже являются предметом исследования), но и другие индексы, использующиеся для различных задач обработки информации и построения систем информационного поиска. (1) Наиболее популярные классические индексы для поиска в неструктурированных данных, таких как коллекции геномов или файловые репозитории, основаны на суффиксных деревьях и, в особенности, на (разреженных) суффиксных массивах, повсеместно использующихся для решения подобных задач. Поскольку для многих приложений индексируемые данные настолько велики, что едва вмещаются в оперативную память, вопрос построения суффиксных массивов/деревьев оказывается совсем непростым и классические алгоритмы становятся не применимы. В основе наиболее эффективных известных алгоритмов построения суффиксного массива/дерева в таких условиях лежит так называемый легковесный LCE индекс (от англ. Longest Common Extension), который позволяет сравнивать произвольные фрагменты индексируемых данных за близкое к константному время, при этом занимая незначительный объём памяти. Разработка легковесных LCE индексов интенсивно ведётся как минимум с 2010 года и последние работы, закрывающие вопрос для рандомизированного случая, вышли буквально в том году в трудах престижной конференции SODA. В рамках проекта разработан детерминированный легковесный LCE индекс с оптимальным временем работы и оптимальным временем построения для наиболее распространённых ограничений по памяти, в частности, когда доступно не менее O(sqrt{n}) или не менее O(n^eps) памяти, где n - это длина индексируемых данных и eps>0. Тем самым, для этих диапазонов вопрос закрыт. Для других более экзотических ограничений доступной памяти задача, хоть и не закрыта полностью, но для неё получены более быстрые, чем у предшественников, алгоритмы построения легковесных LCE индексов. Непосредственным следствием этого результата стал оптимальный алгоритм детерминированного построения разреженного суффиксного массива и разреженного суффиксного дерева для наиболее распространённых режимов памяти, в частности, когда доступно не менее O(sqrt{n}) или не менее O(n^eps) памяти, где n - это длина индексируемых данных и eps>0. Оба эти результата явились следствием разработки нового более быстрого алгоритма построения недавно опубликованной другими авторами комбинаторной структуры - так называемого t-разделяющего множества, которая интересна и сама по себе. (2) Суффиксное дерево - это стандартный наиболее мощный индекс, применяющийся в огромном множестве задач поиска и анализа данных. В рамках проекта исследуется фундаментальная задача навигации по суффиксному дереву: определение по любому заданному фрагменту данных соответствующей ему позиции в дереве. Классически эта задача решается спуском из корня дерева, что занимает линейное время. В 2014 году был придуман индекс, который позволяет выполнять такие навигационные запросы за константное время, что явилось неожиданностью для большинства исследователей в области. Этот индекс решает явно фундаментальную задачу в данной области и он уже успел найти ряд интересных приложений, но его широкому распространению мешало то, что его авторы не нашли для него линейного алгоритма построения. В рамках проекта разработан аналогичный индекс с тем же функционалом, но имеющий линейный (т.е. оптимальный) алгоритм построения. Кроме того, новый индекс привлекателен с теоретической точки зрения, так как опирается на совершенно другие комбинаторные принципы нежели его предшественник и, в определённом смысле, является более "однородным" по структуре и использующимся подходам.

Публикации

1. Белаззоги Дж., Косолобов Д.А., Пуглизи С.Дж., Раман Р. Weighted Ancestors in Suffix Trees Revisited Proceedings of 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), Leibniz International Proceedings in Informatics (LIPIcs), - (год публикации - 2021)

Аннотация результатов, полученных в 2021 году
В рамках проекта получен два новых результатов, перечисленных далее. Они оба связаны с хранением и обработкой данных (в особенности текстовых и текстоподобных), рост объёма которых значительно опережает рост производительности компьютеров. Исследуются структуры хранения данных с возможностью быстрого поиска, доступа и выполнения других запросов. Подобные структуры называются индексами и включают в себя не только поисковые индексы (которые наиболее известны), но и другие индексы, использующиеся для различных задач обработки информации и построения систем информационного поиска. Наиболее популярные классические индексы для поиска в неструктурированных данных, таких как коллекции геномов или файловые репозитории, основаны на суффиксных деревьях и суффиксных массивах, повсеместно использующихся для решения подобных задач, и на их так называемых "разреженных" аналогах, которые используются, когда не достаёт памяти для полноценных суффиксных деревьев/массивов. Поскольку для многих приложений индексируемые данные настолько велики, что едва вмещаются в оперативную память, вопрос построения разреженных суффиксных массивов/деревьев оказывается совсем непростым и классические алгоритмы становятся не применимы. Построение разреженных суффиксных деревьев с ограниченной памятью было популярной темой в последние годы и наша работа по-существу закрывает эту задачу теоретически в большинстве важных случаев. В качестве побочного результата нами разработан новый оптимальный алгоритм построения комбинаторной структуры, называемой t-разделяющее множество, которая появилась недавно, но уже успела получить множество приложений в индексах и становится всё популярнее в данной области. (а) Нами разработан оптимальный по времени и памяти алгоритм детерминированного построения разреженного суффиксного массива и разреженного суффиксного дерева для наиболее распространённых режимов памяти, в частности, когда доступно не менее O(sqrt{n}) или не менее O(n^eps) памяти, где n - это длина индексируемых данных и eps>0. Этот результат, таким образом, полностью решает данную задачу, по крайней мере теоретически, для важнейших режимов доступной памяти. (б) Результат из пункта (а) был получен с помощью разработанного нами нового оптимального по скорости и памяти алгоритма построения недавно опубликованной другими авторами комбинаторной структуры - так называемого t-разделяющего множества, которая интересна и сама по себе и уже получила множество приложений в публикациях различных исследователей. Более конкретно, нами получен первый известный оптимальный по времени и памяти алгоритм, который конструирует оптимальное по размеру t-разделяющее множество в тех же рамках памяти, что и в пункте (а). Таким образом, эта задача тоже теоретически решена, в некотором роде, по крайней мере в рассматриваемых диапазонах памяти.

Публикации

1. Косолобов Д.А., Сивухин Н.С. Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space arxiv, pp.1-27 (год публикации - 2021)

Возможность практического использования результатов
Результаты проекта носят теоретический характер, несмотря на то, что рассматриваемые задачи имеют вполне практические приложения в области хранения, обработки и поиска в больших данных (геномных базах, системах контроля версий, данных журналирования (logs) и т.п.). Результаты работы формируют научный и технологический задел в области сжатых структур данных, которая имеет огромный потенциал приложений в мире обработки и хранения всё более растущих массивов данных.