Стратегия индексирования для поиска похожих строк

Question

Я работаю над разработкой стратегии индексирования для поиска похожих хэшей. Хеши генерируются для изображений. т.е.

String A = "00007c3fff1f3b06738f390079c627c3ffe3fb11f0007c00fff07ff03f003000" //Image 1 
String B = "6000fc3efb1f1b06638f1b0071c667c7fff3e738d0007c00fff03ff03f803000" //Image 2 

Эти два хешей подобны (на основе расстояния Хемминга и Левенштейна расстояния) и, следовательно, подобных изображений. У меня более 190 миллионов таких хэшей. Я должен выбрать подходящую структуру данных индексирования, где сложность худшего случая для поиска аналогичного хеша не является O (n). Хэш-структура данных не будет работать, потому что она будет искать <, = и> (или будет?). Я могу найти расстояние Хэмминга или другое расстояние, чтобы рассчитать сходство, но в худшем случае я в конечном итоге вычислил его в 190 миллионов раз.

Это моя стратегия в настоящее время:

В настоящее время я работаю над BTree, где я буду ранжировать все ключи в узле не на основе не. из последовательных одинаковых символов и пересечь ключ, который имеет наивысший рейтинг, и если ранжирование ключей ребенка меньше, чем ранг другого ключа в родительском узле, я начну обходить этот ключ в родительском узле. Если весь ранг родительского элемента будет таким же, я сделаю обычный траверс BTree (givenkey < nodeKey -> перейти к дочернему узлу nodeKey..используя сравнение ASCII), где моя проблема.

Потому что это приведет к множеству ложных негативов в поиске. Как и в худшем случае, я пройду только одну часть дерева, где потенциально подобный ключ можно найти в других проходах. Иначе я должен искать целые деревья, которые снова O (n), где я мог бы также не иметь дерева.

Я чувствую, что должен быть лучший способ, и прямо сейчас я застрял, и было бы здорово услышать какие-либо входы при разрушении проблемы. Пожалуйста, поделитесь своими мыслями.

P.S: и я не могу использовать внешнюю базу данных.

Answer 1

Во-первых, это очень сложная проблема. Не ожидайте опрятных, аккуратных ответов.

Одна приблизительная структура данных, которую я видел, это Spatial Approximation Sample Hierarchy (SASH).

SASH (Иерархия выборки пространственной аппроксимации) - это структура данных общего назначения для эффективного вычисления приблизительных ответов на запросы сходства. Запросы на сходство, естественно, возникают в ряде важных вычислительных контекстов, в частности на основе контента, на базе мультимедийных баз данных и методах ближайшего соседства для кластеризации и классификации.

SASH использует только функцию расстояния для построения структуры данных, поэтому функция расстояния (и в вашем случае, функция хэш-функции изображения) должна быть «хорошей». Основная интуиция примерно такова, что если A ~ B (изображение A близко к изображению B) и B ~ C, то обычно A ~ C. Структура данных создает связи между относительно близкими объектами, и вы обрезаете свой поиск, только глядя для вещей, которые ближе к вашему запросу. Фактически ли эта стратегия работает, зависит от характера ваших данных и функции расстояния.

Прошло 10 лет с тех пор, как я посмотрел на SASH, поэтому, возможно, появились и новые разработки. Michael Houle's page, по-видимому, указывает, что у него есть более новые исследования по поводу того, что называется Rank Cover Trees, которые кажутся похожими на SASH. Это, по крайней мере, должно помочь вам начать исследования в этой области; прочитайте несколько статей и следуйте эталонному маршруту.