Поиск похожих изображений по pHash расстоянию в Elasticsearch
Подобная проблема поиска изображения
- Миллионы изображений pHash'ed и хранятся в Elasticsearch.
- Формат "11001101...11" (длина 64), но может быть изменен (лучше нет).
Для данного хеша изображения объекта "100111..10" мы хотим найти все подобные хеши изображений в индексе Elasticsearch в пределах расстояния Хэмминга от 8.
Конечно, запрос может возвращать изображения с расстоянием более 8, и скрипт в Elasticsearch или за его пределами может фильтровать набор результатов. Но общее время поиска должно быть в пределах 1 секунды или около того.
Наше текущее картографирование
Каждый документ имеет вложенность images поле, содержащее хэши изображений:
{
"images": {
"type": "nested",
"properties": {
"pHashFingerprint": {"index": "not_analysed", "type": "string"}
}
}
}
Наше плохое решение
Факт: нечеткий запрос Elasticsearch поддерживает расстояние Левенштейна максимум до 2.
Мы использовали собственный токенизатор, чтобы разбить 64-битную строку на 4 группы по 16 бит и выполнить поиск по 4 группам с четырьмя нечеткими запросами.
Анализатор:
{
"analysis": {
"analyzer": {
"split4_fingerprint_analyzer": {
"type": "custom",
"tokenizer": "split4_fingerprint_tokenizer"
}
},
"tokenizer": {
"split4_fingerprint_tokenizer": {
"type": "pattern",
"group": 0,
"pattern": "([01]{16})"
}
}
}
}
Тогда новое отображение поля:
"index_analyzer": "split4_fingerprint_analyzer",
Тогда запрос:
{
"query": {
"filtered": {
"query": {
"nested": {
"path": "images",
"query": {
"bool": {
"minimum_should_match": 2,
"should": [
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "0010100100111001",
"fuzziness": 2
}
}
},
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "1010100100111001",
"fuzziness": 2
}
}
},
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "0110100100111001",
"fuzziness": 2
}
}
},
{
"fuzzy": {
"phashFingerprint.split4": {
"value": "1110100100111001",
"fuzziness": 2
}
}
}
]
}
}
}
},
"filter": {}
}
}
}
Обратите внимание, что мы возвращаем документы, которые имеют совпадающие изображения, а не сами изображения, но это не должно сильно менять ситуацию.
Проблема в том, что этот запрос возвращает сотни тысяч результатов даже после добавления других специфичных для домена фильтров для уменьшения начального набора. В скрипте слишком много работы, чтобы снова вычислить расстояние Хемминга, поэтому запрос может занять несколько минут.
Как и ожидалось, если увеличение minimum_should_match 3 и 4, возвращается только подмножество изображений, которые должны быть найдены, но результирующий набор мал и быстр. Ниже 95% необходимых изображений возвращаются с minimum_should_match == 3 но нам нужно 100% (или 99,9%) как с minimum_should_match == 2.
Мы пробовали аналогичные подходы с n-граммами, но все еще не достигли большого успеха в подобной манере слишком большого количества результатов.
Какие-либо решения других структур данных и запросов?
Редактировать:
Мы заметили, что в нашем процессе оценки была ошибка, и minimum_should_match == 2 возвращает 100% результатов. Однако впоследствии обработка занимает в среднем 5 секунд. Посмотрим, стоит ли оптимизировать скрипт.
6 ответов
Я смоделировал и реализовал возможное решение, которое позволяет избежать всех дорогих "нечетких" запросов. Вместо этого во время индекса вы берете N случайные образцы M биты из этих 64 битов. Я предполагаю, что это пример хеширования, чувствительного к локальности. Так для каждого документа (и при запросе) номер образца x всегда берется из одних и тех же битовых позиций для согласованного хеширования по документам
Использование запросов term фильтры на bool query "s should оговорка с относительно низким minimum_should_match порог. Нижний порог соответствует более высокой "нечеткости". К сожалению, вам нужно переиндексировать все ваши изображения, чтобы проверить этот подход.
Я думаю { "term": { "phash.0": true } } запросы не выполняются хорошо, потому что в среднем каждый фильтр соответствует 50% документов. С 16 бит / образец каждый образец соответствует 2^-16 = 0.0015% документов.
Я запускаю свои тесты со следующими настройками:
- 1024 сэмпла / хэш (сохраняются в полях документа
"0"-"ff") - 16 бит / образец (сохраняется в
shortтип,doc_values = true) - 4 сегмента и 1 миллион хешей / индекс, около 17,6 ГБ памяти (можно уменьшить, если не хранить
_sourceи сэмплы, только оригинальный бинарный хеш) minimum_should_match= 150 (из 1024)- Бенчмаркинг с 4 миллионами документов (4 индекса)
Вы получаете более высокую скорость и более низкое использование диска с меньшим количеством образцов, но документы между расстояниями Хэмминга от 8 до 9 не так хорошо разделены (согласно моим моделям). 1024, кажется, максимальное количество should статьи.
Тесты проводились на одном Core i5 3570K, 24 ГБ ОЗУ, 8 ГБ для ES, версия 1.7.1. Результаты 500 запросов (см. Примечания ниже, результаты слишком оптимистичны):
Mean time: 221.330 ms
Mean docs: 197
Percentiles:
1st = 140.51ms
5th = 150.17ms
25th = 172.29ms
50th = 207.92ms
75th = 233.25ms
95th = 296.27ms
99th = 533.88ms
Я протестирую, как это масштабируется до 15 миллионов документов, но на создание и хранение 1 миллиона документов для каждого индекса уходит 3 часа.
Вы должны проверить или рассчитать, как низко вы должны установить minimum_should_match чтобы получить желаемый компромисс между пропущенными матчами и неправильными матчами, это зависит от распределения ваших хэшей.
Пример запроса (показано 3 из 1024 полей):
{
"bool": {
"should": [
{
"filtered": {
"filter": {
"term": {
"0": -12094,
"_cache": false
}
}
}
},
{
"filtered": {
"filter": {
"term": {
"_cache": false,
"1": -20275
}
}
}
},
{
"filtered": {
"filter": {
"term": {
"ff": 15724,
"_cache": false
}
}
}
}
],
"minimum_should_match": 150
}
}
Изменить: Когда я начал делать дополнительные тесты, я заметил, что я сгенерировал слишком разные хеши для разных индексов, поэтому поиск по ним привел к нулю совпадений. Вновь созданные документы приводят к 150 - 250 совпадениям / индексу / запросу и должны быть более реалистичными.
Новые результаты показаны на графике ранее, у меня было 4 ГБ памяти для ES и оставшиеся 20 ГБ для ОС. Поиск по 1 - 3 индексам показал хорошую производительность (среднее время 0,1 - 0,2 секунды), но при поиске больше, чем это, было много дискового ввода-вывода, и запросы начали занимать 9 - 11 секунд! Этого можно обойти, взяв меньшее количество образцов хэша, но тогда скорость отзыва и точность будут не такими хорошими, в противном случае вы могли бы иметь машину с 64 ГБ ОЗУ и посмотреть, как далеко вы доберетесь.
Изменить 2: я заново сгенерировал данные с _source: false и не хранить образцы хеша (только необработанный хэш), это сократило объем памяти на 60% до 6,7 ГБ / индекс (из 1 миллиона документов). Это не влияло на скорость запросов для небольших наборов данных, но когда оперативной памяти было недостаточно и требовалось использовать диск, запросы выполнялись примерно на 40% быстрее.
Редактировать 3: я проверял fuzzy выполнить поиск с расстоянием редактирования 2 на наборе из 30 миллионов документов и сравнить его с 256 случайными выборками хэша, чтобы получить приблизительные результаты. В этих условиях методы имеют примерно одинаковую скорость, но fuzzy дает точные результаты и не требует дополнительного дискового пространства. Я думаю, что этот подход полезен только для "очень нечетких" запросов, таких как расстояние Хэмминга больше 3.
Я также реализовал подход CUDA с некоторыми хорошими результатами даже на видеокарте GeForce 650M для ноутбука. Реализация была легкой с библиотекой Thrust. Я надеюсь, что в коде нет ошибок (я не проверял их полностью), но это не должно повлиять на результаты тестов. По крайней мере я звонил thrust::system::cuda::detail::synchronize() перед остановкой высокоточного таймера.
typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;
// Maybe there is a simple 64-bit solution out there?
__host__ __device__ inline int hammingWeight(uint32_t v)
{
v = v - ((v>>1) & 0x55555555);
v = (v & 0x33333333) + ((v>>2) & 0x33333333);
return ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
__host__ __device__ inline int hammingDistance(const uint64_t a, const uint64_t b)
{
const uint64_t delta = a ^ b;
return hammingWeight(delta & 0xffffffffULL) + hammingWeight(delta >> 32);
}
struct HammingDistanceFilter
{
const uint64_t _target, _maxDistance;
HammingDistanceFilter(const uint64_t target, const uint64_t maxDistance) :
_target(target), _maxDistance(maxDistance) {
}
__host__ __device__ bool operator()(const uint64_t hash) {
return hammingDistance(_target, hash) <= _maxDistance;
}
};
Линейный поиск был так же прост, как
thrust::copy_if(
hashesGpu.cbegin(), hashesGpu.cend(), matchesGpu.begin(),
HammingDistanceFilter(target_hash, maxDistance)
)
Поиск был на 100% точнее и намного быстрее, чем мой ответ на ElasticSearch, за 50 миллисекунд CUDA могла передавать 35 миллионов хэшей! Я уверен, что новые настольные карты даже быстрее, чем эта. Кроме того, мы получаем очень низкую дисперсию и постоянный линейный рост времени поиска, поскольку мы просматриваем все больше и больше данных. ElasticSearch обнаружил проблемы с памятью при больших запросах из-за завышенных данных выборки.
Итак, здесь я сообщаю результаты "Из этих N хешей найдите те, которые находятся в пределах 8 расстояний Хэмминга от одного хеша H". Я бегу эти 500 раз и сообщаю процентили.
Существуют некоторые издержки запуска ядра, но после того, как пространство поиска превысило 5 миллионов хешей, скорость поиска остается достаточно постоянной и составляет 700 миллионов хешей в секунду. Естественно, верхняя граница числа хэшей, которые нужно искать, устанавливается ОЗУ графического процессора.
Я сам начал решение этой проблемы. До сих пор я проверял только набор данных из примерно 3,8 миллионов документов, и теперь я намерен увеличить его до десятков миллионов.
Мое решение пока таково:
Напишите собственную функцию оценки и зарегистрируйте ее как плагин. Затем вызовите это при запросе, чтобы настроить _score стоимость документов по мере их возврата.
Как отличный сценарий, время, затрачиваемое на запуск пользовательской функции оценки, было крайне не впечатляющим, но написание ее как встроенной функции оценки (как показано в этом несколько устаревшем сообщении в блоге: http://www.spacevatican.org/2012/5/12/elasticsearch-native-scripts-for-dummies/) был на несколько порядков быстрее.
Мой HammingDistanceScript выглядел примерно так:
public class HammingDistanceScript extends AbstractFloatSearchScript {
private String field;
private String hash;
private int length;
public HammingDistanceScript(Map<String, Object> params) {
super();
field = (String) params.get("param_field");
hash = (String) params.get("param_hash");
if(hash != null){
length = hash.length() * 8;
}
}
private int hammingDistance(CharSequence lhs, CharSequence rhs){
return length - new BigInteger(lhs, 16).xor(new BigInteger(rhs, 16)).bitCount();
}
@Override
public float runAsFloat() {
String fieldValue = ((ScriptDocValues.Strings) doc().get(field)).getValue();
//Serious arse covering:
if(hash == null || fieldValue == null || fieldValue.length() != hash.length()){
return 0.0f;
}
return hammingDistance(fieldValue, hash);
}
}
Стоит отметить, что мои хэши - это двоичные строки с шестнадцатеричным кодированием. Так же, как и у вас, но в шестнадцатеричном коде, чтобы уменьшить объем хранилища.
Кроме того, я ожидаю параметр param_field, который определяет, какое значение поля я хочу сделать на расстоянии Хэмминга. Вам не нужно этого делать, но я использую один и тот же скрипт для нескольких полей, поэтому я делаю:)
Я использую его в таких запросах:
curl -XPOST 'http://localhost:9200/scf/_search?pretty' -d '{
"query": {
"function_score": {
"min_score": MY IDEAL MIN SCORE HERE,
"query":{
"match_all":{}
},
"functions": [
{
"script_score": {
"script": "hamming_distance",
"lang" : "native",
"params": {
"param_hash": "HASH TO COMPARE WITH",
"param_field":"phash"
}
}
}
]
}
}
}'
Я надеюсь, что это поможет в некотором роде!
Другая информация, которая может быть вам полезна, если вы пойдете по этому маршруту:
1. Запомните файл es-plugin.properties
Это должно быть скомпилировано в корень вашего jar-файла (если вы вставите его в /src/main/resources, то создайте свой jar-файл, и он попадет в нужное место).
Моя выглядела так:
plugin=com.example.elasticsearch.plugins.HammingDistancePlugin
name=hamming_distance
version=0.1.0
jvm=true
classname=com.example.elasticsearch.plugins.HammingDistancePlugin
java.version=1.7
elasticsearch.version=1.7.3
2. Ссылка на ваш пользовательский NativeScriptFactory impl в asticsearch.yml
Прямо как в старом посте.
Моя выглядела так:
script.native:
hamming_distance.type: com.example.elasticsearch.plugins.HammingDistanceScriptFactory
Если вы этого не сделаете, он все равно будет отображаться в списке плагинов (см. Далее), но при попытке его использования вы получите сообщение о том, что asticsearch не может его найти.
3. Не утруждайте себя использованием сценария плагина asticsearch для его установки
Это просто боль в заднице, и все, что она делает, это распаковывает вещи - немного бессмысленно. Вместо этого просто вставьте это в %ELASTICSEARCH_HOME%/plugins/hamming_distance и перезапустите эластичный поиск.
Если все прошло хорошо, вы увидите, что он загружается при запуске asticsearch:
[2016-02-09 12:02:43,765][INFO ][plugins ] [Junta] loaded [mapper-attachments, marvel, knapsack-1.7.2.0-954d066, hamming_distance, euclidean_distance, cloud-aws], sites [marvel, bigdesk]
И когда вы вызовете список плагинов, он будет там:
curl http://localhost:9200/_cat/plugins?v
производит что-то вроде:
name component version type url
Junta hamming_distance 0.1.0 j
Я ожидаю, что смогу проверить более десятков миллионов документов в течение следующей недели или около того. Я постараюсь вспомнить и обновить это с результатами, если это поможет.
Недавно предложенный метод FENSHSES из [1], по-видимому, является самым современным методом поиска r-соседей в пространстве Хэмминга на Elasticsearch.
[1] Му, Ц., Чжао, Дж., Ян, Г., Ян, Б., и Янь, З., 2019 г., октябрь. Быстрый и точный поиск ближайшего соседа в пространстве Хэмминга в полнотекстовых поисковых системах. В Международной конференции по поиску сходства и приложениям (стр. 49-56). Спрингер, Чам.
Вот 64- битное решение для ответа @NikoNyrh. Расстояние Хэмминга можно рассчитать, просто используя оператор XOR со встроенной функцией __popcll в CUDA.
struct HammingDistanceFilter
{
const uint64_t _target, _maxDistance;
HammingDistanceFilter(const uint64_t target, const uint64_t maxDistance) :
_target(target), _maxDistance(maxDistance) {
}
__device__ bool operator()(const uint64_t hash) {
return __popcll(_target ^ hash) <= _maxDistance;
}
};
Вот не элегантное, но точное (грубое) решение, которое требует деконструкции хеша вашей функции на отдельные логические поля, чтобы вы могли выполнить запрос следующим образом:
"query": {
"bool": {
"minimum_should_match": -8,
"should": [
{ "term": { "phash.0": true } },
{ "term": { "phash.1": false } },
...
{ "term": { "phash.63": true } }
]
}
}
Я не уверен, как это будет работать по сравнению с fuzzy_like_this, но причина, по которой реализация FLT устарела, заключается в том, что он должен посещать каждый термин в индексе, чтобы вычислить расстояние редактирования.
(тогда как здесь / выше вы используете основную структуру данных с инвертированным индексом Lucene и оптимизированные операции над множествами, которые должны работать в ваших интересах, учитывая, что у вас, вероятно, есть довольно редкие функции)
Я использовал ответ @ndtreviv в качестве отправной точки. Вот мои заметки для ElasticSearch 2.3.3:
es-plugin.propertiesфайл теперь называетсяplugin-descriptor.propertiesВы не ссылаетесь
NativeScriptFactoryвelasticsearch.ymlвместо этого вы создаете дополнительный класс рядом с вашимHammingDistanceScript,
import org.elasticsearch.common.Nullable;
import org.elasticsearch.plugins.Plugin;
import org.elasticsearch.script.ExecutableScript;
import org.elasticsearch.script.NativeScriptFactory;
import org.elasticsearch.script.ScriptModule;
import java.util.Map;
public class StringMetricsPlugin extends Plugin {
@Override
public String name() {
return "string-metrics";
}
@Override
public String description() {
return "";
}
public void onModule(ScriptModule module) {
module.registerScript("hamming-distance", HammingDistanceScriptFactory.class);
}
public static class HammingDistanceScriptFactory implements NativeScriptFactory {
@Override
public ExecutableScript newScript(@Nullable Map<String, Object> params) {
return new HammingDistanceScript(params);
}
@Override
public boolean needsScores() {
return false;
}
}
}
- Затем укажите этот класс в своем
plugin-descriptor.propertiesфайл:
plugin=com.example.elasticsearch.plugins. StringMetricsPlugin
name=string-metrics
version=0.1.0
jvm=true
classname=com.example.elasticsearch.plugins.StringMetricsPlugin
java.version=1.8
elasticsearch.version=2.3.3
- Вы запрашиваете, предоставив имя, которое вы использовали в этой строке:
module.registerScript("hamming-distance", HammingDistanceScriptFactory.class);в 2.
Надеюсь, что это поможет следующей бедной душе, которая имеет дело с дерьмовыми документами ES.