• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Уваренков Илья Дмитриевич
Использование контекстного кодирования Хаффмана в задаче сжатия векторов высокой размерности
Науки о данных
(Магистратура)
2018
В работе рассматривается задача сжатия векторов высокой размерности на примере дескрипторов изображений SIFT из датасета SIFT1M, а также глубоких нейросетевых дескрипторов из датасета DEEP1B. Классическим решением данной задачи является применение алгоритма Product Quantization (PQ) к исходному множеству векторов для получения нового множества целочисленных векторов с фиксированным и задаваемым в качестве параметра алгоритма коэффициентом сжатия. Алгоритм Product Quantization является алгоритмом сжатия с потерями, причём потери неизвестны до применения алгоритма. В существующих модификациях алгоритма PQ, таких как Optimized Product Quantization (OPQ), или Additive Quantization (AQ) оптимизируется ошибка кодирования, при том же коэффициенте сжатия, что и в исходном алгоритме. В данной работе предлагается применить к выходу Product Quantization биграммное Хаффмановское кодирование, чтобы оптимизировать коэффициент сжатия, при фиксированной ошибке кодирования, вносимой Product Quantization. В работе разработаны два метода сжатия, основанные на построении минимального остовного дерева, а также на лексикографической сортировке кодированных при помощи Product Quantization векторов. Оба метода дают различную степень сжатия на различных параметрах запуска и датасетах, от 5.6 до 1.4 бита на каждый байт выходного объёма Product Quantization, однако требуют дополнительных вычислительных мощностей, а также значительных объёмов оперативной памяти как для кодирования, так и для декодирования. Кроме того, оба метода вводят переменный размер элементов датасета, что лишает возможности произвольного доступа к векторам, а также фиксируют структуру хранения векторов в датасете. Тем не менее, предложенный алгоритм может быть использован в задачах сжатия векторов, где применим алгоритм Product Quantization, а указанные дополнительные ограничения не играют большой роли.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Расширенный поиск ВКР