| Аннотация |
Проект направлен на исследование задач хранения и обработки больших объёмов данных с избыточностью (что подразумевает их сжимаемость). Во многих областях наблюдается взрывообразный рост таких данных, причём часто это не просто мёртвые репозитории, которые можно было бы заархивировать (т.е. сжать) и извлекать лишь в тех редких случаях, когда они понадобятся, а это живые данные, к которым необходим непрерывный доступ для поиска в них или проведения каких-то операций обработки и анализа. Но объёмы таких данных в подобных приложениях далеко не всегда позволяют хранить их в несжатом или фрагментарно сжатом виде (что, на первый взгляд, кажется необходимым для обеспечения быстрого доступа) с приемлемыми затратами на носители памяти. Эта ситуация порождает ряд теоретических и практических вызовов.
Проект предполагает, во-первых, исследование и улучшение определённых недавно появившихся прорывных методов хранения данных в сжатом виде, а во-вторых, исследование структур хранения сжатых данных с возможностью быстрого поиска, доступа и выполнения других запросов. Подобные структуры называются сжатыми индексами. Будут рассмотрены как чисто теоретические задачи (анализ эффективности существующих методов), так и задачи, имеющие прикладное значение (новые сжатые индексы). Конкуренция в данной теме высока, но заявитель имеет успешный опыт работы в ней, вылившийся в публикации высокого международного уровня, что обеспечит выполнение проекта. Ниже более подробно раскрыто содержание проекта.
Последнее десятилетие в области хранения данных в сжатом виде без потерь наблюдается определённое оживление, главным образом среди практиков и технологических компаний, простимулированное появлением нового семейства энтропийных кодеров: Asymmetric Numeral Systems (ANS). Энтропийный кодер является базовой частью большинства алгоритмов сжатия, в том числе сжатых индексов. Новые ANS кодеры пришли на замену классическим кодерам Хаффмана и арифметическим кодерам, предоставляя качество последних со скоростью первых. В то время как практическая значимость ANS очевидна, теоретическое место ANS, обосновывающее его успех, не до конца понятно. В рамках проекта предполагается восполнить пробел в теоретическом понимании эффективности ANS кодеров, математически точно оценив их избыточность; также планируется разработать модификации ANS с улучшенным временем работы в некоторых ситуациях с прицелом на использование этих модификаций в сжатых индексах.
Сжатые индексы активно разрабатывают с 2000-х годов. Наибольшего успеха, по-видимому, эта область добилась в биоинформатике, где такие инструменты являются стандартом и не удивляет, что компьютер с 32 гигабайтами памяти может моментально осуществлять поиск в (локальной) базе из тысяч геномов, которая в несжатом виде могла бы занимать десятки терабайт. Почему же эти индексы не получили большего распространения в других областях, где они могли бы демонстрировать такие же впечатляющие результаты? (Например, для систем контроля версий, файлов журналирования, данных социальных сетей и т.д.). По-видимому, причина в том, что до сих пор не существует, во-первых, достаточно быстрых и, главное, приемлемых по потребляемой памяти алгоритмов построения этих индексов (например, базу геномов индексируют на суперкомпьютере и распространяют уже готовый индекс среди пользователей), а во-вторых, не существует эффективных индексов с возможностью редактировать индексируемые данных, хотя бы добавляя новые. В рамках проекта предполагается подступиться к решению этих проблем, разработав сжатый индекс с возможностью эффективного добавления новых данных и с быстрыми стандартными операция доступа и поиска.
Результатами проекта будут математические модели, доказательства, структуры данных, алгоритмы и теоретические и экспериментальные оценки их релевантности и эффективности. Результаты обеспечат дальнейший прогресс в области сжатого хранения данных, индексных структур и информационного поиска, а также смогут быть применимы в некоторых практических приложениях.
|
