Как хранить данные с помощью приблизительного запроса?

Question

Я пытаюсь найти способ хранить мои данные с быстрым доступом (лучше, чем O (n)).

Моя база данных состоит из данных (строки длиной 4096 байт), которые представляют некоторую информацию о некоторых элементах.
Проблема в том, что запрос никогда не бывает точным. Я получаю один предмет, а затем мне нужно найти ближайшее совпадение, используя функцию F(a,b).

только пример:

1234
3456
6466
F(a,b) = return % of similar digits  

GetClosest(1233,F) = 1234

Проблема в том, что F (a, b) - сложный алгоритм (а не правильная метрика).

Теперь у меня есть просто просмотреть всю базу данных, чтобы найти лучшее совпадение.
Существует ли тип дерева или другой тип кластерной базы данных, который может помочь мне быстрее найти сложность?

Дополнительная информация:

F возвращает значение сходства в% процентах. где 100% - идеальное совпадение

Answer 1

Извините, ответ «вероятно, нет», если в вашей проблеме нет какой-то структуры, которую вы не описали.С 4096 байтовыми строками вы страдаете от проклятия размерности .

Если у вас были более короткие строки и достаточно данных, высока вероятность того, что ближайшее совпадение будет одинаковым для большого кускастроки, то вы можете хранить свои данные с несколькими древовидными структурами, проиндексированными по разным фрагментам строки.С высокой вероятностью ближайший будет достаточно близко, чтобы вы могли доказать, что он самый близкий, основываясь только на близких элементах в этих деревьях.Однако, учитывая размер ваших строк и ограниченные данные, которые могут храниться на компьютере, это никоим образом не сработает.

При этом вам нужен точный ближайший или только несколькоБлизкий?Если только вероятный близкий, то вы можете индексировать его несколькими случайными редкими выборками битов.В вашем поиске вы можете проверять только элементы, которые точно соответствуют одному из элементов.Это значительно сократит пространство поиска, отвергая при этом меньшее количество близких соседей, и может дать разумные (хотя часто и неправильные) ответы.

Answer 2

Есть ли какой-нибудь способ, которым вы могли бы присвоить «оценку» каждому датуму?

Вы можете индексировать / упорядочивать данные по вашему счету.

При поиске вы присваиваете оценку критериям поиска и ищите элемент с ближайшей оценкой.

Очень зависит от ваших данных и вашего определения «разницы», будет ли это работать.