Подобный поиск изображения по расстоянию pHash в Elasticsearch

Ответ 1

Я смоделировал и реализовал возможное решение, которое позволяет избежать всех дорогостоящих "нечетких" запросов. Вместо этого в индексном времени вы берете N случайные выборки из M бит из этих 64 бит. Я предполагаю, что это пример чувствительность к местоположению. Таким образом, для каждого документа (и при запросе) номер образца x всегда берется из одинаковых позиций битов, чтобы иметь согласованное хеширование между документами.

В запросах используются фильтры term в bool query should с относительно низким порогом minimum_should_match. Нижний порог соответствует более высокой "размытости". К сожалению, вам нужно повторно проиндексировать все ваши изображения, чтобы проверить этот подход.

Я думаю, что { "term": { "phash.0": true } } запросы не работали хорошо, потому что в среднем каждый фильтр соответствует 50% документов. С 16 битами/образцом каждый образец соответствует 2^-16 = 0.0015% документов.

Я запускаю свои тесты со следующими настройками:

• 1024 samples/hash (хранится в doc-полях "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 миллионов документов, но требуется 3 часа для создания и хранения 1 миллиона документов для каждого индекса.

Вы должны проверить или рассчитать, как низко вы должны установить 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.

Ответ 2

Я также реализовал подход 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 миллионах хэшей в секунду. Естественно, верхняя граница количества хэшей, подлежащих поиску, задается ОЗУ GPU.

Ответ 3

Я начал решать это сам. Пока что я тестировал только набор данных объемом около 3,8 млн. Документов, и сейчас я намерен подтолкнуть его вверх на десятки миллионов.

Мое решение до сих пор:

Напишите собственную функцию подсчета и зарегистрируйте ее как плагин. Затем вызовите это при запросе, чтобы настроить значение _score документов по мере их возврата.

В качестве groovy script время, затрачиваемое на выполнение пользовательской функции подсчета очков, было крайне не впечатляющим, но написание его как собственной функции подсчета очков (как показано в этом несколько устаревшем сообщении в блоге: http://www.spacevatican.org/2012/5/12/elasticsearch-native-scripts-for-dummies/) на порядок быстрее.

My 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, который идентифицирует, какое значение поля я хочу сделать с удалением. Вам не нужно это делать, но я использую тот же script для нескольких полей, поэтому я:)

Я использую его в таких запросах:

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, тогда создайте свою банку, он пойдет в нужном месте).

Шахта выглядела так:

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 в elasticsearch.yml
Так же, как и в возрасте блога.

Шахта выглядела так:

script.native:
    hamming_distance.type: com.example.elasticsearch.plugins.HammingDistanceScriptFactory

Если вы этого не сделаете, он по-прежнему отображается в списке плагинов (см. ниже), но при попытке использовать его вы получите ошибки, заявив, что elasticsearch не может его найти.

3. Не пытайтесь использовать плагин elasticsearch script для его установки
Это просто боль, и все, что ей кажется, это распаковать твои вещи - немного бессмысленно. Вместо этого просто вставьте его в %ELASTICSEARCH_HOME%/plugins/hamming_distance и перезапустите поиск elastics.

Если все пошло хорошо, вы увидите, что он загружается при запуске elasticsearch:

[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

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

Ответ 4

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

"query": {
    "bool": {
      "minimum_should_match": -8,
      "should": [
          { "term": { "phash.0": true } },
          { "term": { "phash.1": false } },
          ...
          { "term": { "phash.63": true } }
        ]
    }
}

Я не уверен, как это будет выполняться против fuzzy_like_this, но причина, по которой реализация FLT устарела, заключается в том, что она должна посещать каждый термин в индексе для вычисления расстояния редактирования.

(тогда как здесь/выше вы используете Lucene, лежащую в основе структуры данных с инвертированным индексом, и оптимизированные операции с множеством, которые должны работать в ваших интересах, учитывая, что у вас, вероятно, есть довольно редкие функции)

Ответ 5

Я использовал @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;
        }
    }
}

3. Затем укажите этот класс в файле 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

4. Вы запрашиваете, указав имя, которое вы использовали в этой строке: module.registerScript("hamming-distance", HammingDistanceScriptFactory.class); в 2.

Надеюсь, это поможет следующей бедной душе, которая должна иметь дело с дерьмовыми документами ES.

Ответ 6

Вот 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;
    }
};