Введение
Базы данных на основе ДНК были впервые предложены более двадцати лет назад Баумом, однако последние демонстрации их практичности вызвали новый интерес к исследованию связанных теорий и применений.
В некоторых из этих недавних демонстраций хранилища ДНК для своих поисковых схем использовался случайный доступ на основе ключей, что не соответствовало предусмотренному Баумом ассоциативному поиску на основе содержимого.
Эта работа способствует двум достижениям в области хранения ДНК: во-первых, это конструкция цепочек, оптимизированная для ассоциативного поиска.
Во-вторых, последовательный кодировщик, способный сохранять схожесть документов, так что последовательность запросов, сформированная из данного документа, будет извлекать аналогичные документы из базы данных.
В случае если вектор признаков имеет сотни измерений, хорошо известное "проклятье размерности" разрушает эффективные схемы индексирования.
В худшем случае, каждый элемент в базе данных должен быть проверен, чтобы найти все изображения в пределах определенного порога расстояния.
Уменьшение проблемы поиска, допускающее ошибки или упущения, приводит к значительному ускорению поиска с использованием таких алгоритмов, как локально-чувствительное перемешивание (LSH).
В перспективе, когда в будущем каждый год будут генерироваться данные в формате зеттабайт. Такие технологии, как LSH, которые сокращают объем данных, требующих проверки на порядки величины, все равно будут перегружать традиционное хранение огромным количеством запросов ввода-вывода в массивную инфраструктуру хранения с превышением затрат времени и энергии, связанных с расчетом расстояния по вектору характеристик.
Специалисты по компьютерной технике заметили, что мощность, необходимая для перемещения данных с устройства хранения на вычислительное устройство, может быть уменьшена путем перемещения вычислительной подложки ближе к подложке хранилища. Этот класс методов широко называют "обработкой близких к данным".
Схожие результаты поиска
Проблема поиска совпадения заключается в извлечении документов из базы данных, содержание которых схоже с содержанием данного запроса.
Для таких средств массовой информации, как текст, изображения и видео, это может быть трудной задачей.
Большинство современных систем преобразует каждый документ в векторное пространственное представление с помощью либо ручной вставки, либо нейросети.
Векторы этих признаков затем можно сравнить с метриками, такими как расстояние по Евклидану, где аналогичные документы будут иметь тенденцию к сближению в пространстве признаков. Таким образом, поиск сходства может быть сведен к поиску k ближнего соседа или R ближнего соседа.
Характерные векторы, которые эффективны для поиска схожести, имеют тенденцию быть крупногабаритными.
Визуальные особенности каждого изображения в наборе данных были извлечены с помощью VGG16, общедоступной нейронной сети, прошедшей обучение по задаче классификации изображений.
В качестве промежуточного слоя в VGG16 мы использовали 4096-мерные активации из слоя FC2, который доказал свою эффективность в задачах поиска изображений на основе содержимого. Эти характеристики были уменьшены до 100, 10 и 2 измерений с помощью анализа основных компонентов (PCA).
Справа от каждого запроса отображаются ближайшие соседи в каждом из этих подпространств (по отношению к расстоянию по Евклидею). Качественно, ближайшие соседи в низкоразмерных пространствах больше похожи на запросы, чем ближайшие соседи в низкоразмерных пространствах.
Параллельный поиск на основе ДНК
Вычисления ДНК в стиле Adleman можно рассматривать как экстремальную версию обработки близких к реальности данных: каждая цепочка ДНК предназначена как для хранения, так и для обработки информации - подложки вычислений и хранения одни и те же.
Как и оригинальное решение проблемы гамильтониана Адлемана, этот стиль параллельной обработки требует экспоненциального количества ДНК для решения комбинаторных задач.
В то же время, для решения менее сложных задач, таких как поиск сходства, количество требуемого количества ДНК гораздо меньше: если каждый из N элементов в базе данных нанесен на единую "целевую" молекулу, то для реакции с каждым элементом в базе достаточно N идентичных копий молекулы "запроса".
Следовательно, если запрос оснащен наконечником биотина и предназначен для гибридизации только с соответствующими данными, то соответствующие предметы могут быть "вырваны" из базы данных с помощью металлических шариков со спиральным напылением.
Следовательно, параллельный поиск с очень высокой скоростью передачи данных в русле методов, близких к обработке данных.
Кроме того, поскольку ПЦР может делать экспоненциально много копий молекулы запроса, количество ДНК, которое должно быть непосредственно синтезировано, минимально.
Это делает поиск на основе ДНК особенно привлекательным в зеттабайт-йотабайт будущем.
Хранение данных на основе ДНК
Современнейшие системы хранения ДНК (в том числе система Органик и др. включает хороший обзор последних работ) ориентированы на поиск произвольных цифровых данных с нулевым разрядом ошибок.
Каждый цифровой файл разделен на сегменты и закодирован во многие тысячи уникальных последовательностей, и отдельные файлы могут быть получены из смешанной базы данных с помощью случайного доступа на основе ПЦР.
В данной работе мы делаем упор на базу данных для хранения и извлечения метаданных. Вместо хранения последовательностей, содержащих полный файл, каждый файл ассоциируется с последовательностью, которая содержит семантические свойства, используемые для поиска по содержимому, а также указатель на файл в другой базе данных (может быть либо традиционной, либо основанной на ДНК).