Ähnliche Bilder Suche von pHash Entfernung in Elasticsearch

Habe ich simuliert und implementiert eine mögliche Lösung, die vermeidet teure "fuzzy" - Abfragen. Statt zur index-Zeit, die Sie nehmen N Stichproben M bits, die 64 bits. Ich denke, dies ist ein Beispiel von Locality-sensitive-hashing. So wird für jedes Dokument (und wenn-Abfragen) Beispiel Anzahlx ist immer von der gleichen bit-Positionen haben eine gleichmäßige Vermischung zwischen Dokumenten.

Abfragen verwenden term Filter bool query's should Klausel mit relativ niedrigen minimum_should_match Schwelle. Untere Schwelle entspricht höheren "Unschärfe". Leider müssen Sie re-index alle Ihre Bilder zum test dieses Ansatzes.

Ich denke { "term": { "phash.0": true } } Abfragen nicht gut führen, weil im Durchschnitt jeder filter entspricht 50% von Dokumenten. Mit 16 bits /sample jedes sample entspricht 2^-16 = 0.0015% von Dokumenten.

Ich meine tests mit folgenden Einstellungen:

• 1024 samples /hash (gespeicherte doc Felder "0" - "ff")
• 16 bits /sample (gespeichert short Typ doc_values = true)
• 4 Scherben und 1 Mio hashes /index, etwa 17.6 GB Speicher (könnte minimiert werden, indem nicht speichern _source und Proben, nur die original-binary hash)
• minimum_should_match = 150 (von 1024)
• Benchmark mit 4-Millionen-docs (4 Indizes)

Erhalten Sie schnellere Geschwindigkeit und der unteren Datenträger-Auslastung mit weniger Proben, aber Dokumente zwischen den hamming-Distanzen von 8 und 9 sind nicht so gut getrennt sind (laut meinen Simulationen). 1024 scheint die maximale Anzahl von should Klauseln.

Prüfungen wurden auf einem single-Core-i5-3570K, 24 GB RAM, 8 GB für LiveCycle ES, version 1.7.1. Ergebnisse von 500 Abfragen (siehe Hinweise unten, die Ergebnisse sind zu optimistisch):

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

Werde ich testen, wie sich diese Skalen zu 15 Millionen Dokumente, aber es dauert 3 Stunden zu erzeugen und zu speichern 1 Millionen Dokumente zu jedem index.

Sollten Sie testen, oder berechnen, wie tief Sie sollten minimum_should_match um die gewünschte trade-off zwischen treer und falschen entspricht, dieser richtet sich auf die Verteilung der hashes.

Beispiel Abfrage (3 von 1024 Felder gezeigt):

{
  "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
  }
}

Edit: Als ich anfing, weitere benchmarks habe ich gemerkt, dass ich erzeugt hatte zu unterschiedlichen hashes für die verschiedenen Indizes, also die Suche von diesen führte zu null Treffern. Die neu generierten Dokumente Ergebnis in etwa 150 - 250 matches /index /query und sollten realistischer sein.

Neuen Ergebnisse sind in der Grafik dargestellt, bevor, ich hatte 4 GB Speicher für ES zu und die restlichen 20 GB für OS. Suche 1 - 3-Indizes hatten gute performance (mittelwertbildungszeit 0.1 - 0.2 Sekunden), aber die Suche mehr als dies führte zu viele Datenträger-E /a und die Anfragen gestartet die Einnahme von 9 - 11 Sekunden! Dies könnte umgangen werden, indem man weniger Proben der hash aber dann recall-und precision-raten wäre nicht so gut, alternativ könnten Sie eine Maschine mit 64 GB RAM und sehen, wie weit Sie erhalten.

Edit 2: ich re-generierte Daten mit _source: false und nicht die Speicherung von hash-Beispiele (nur die raw-hash), dies reduziert den Speicherplatz um 60% auf rund 6.7 GB /index (von 1 Millionen Dokumente). Dies hatte keinen Einfluss auf die abfragegeschwindigkeit auf kleinere Datensätze, aber wenn RAM nicht ausreichend und Datenträger verwendet werden musste-Abfragen wurden über 40% schneller.

Edit 3: getestet habe ich fuzzy Suche mit edit-Distanz von 2 auf einen Satz von 30 Millionen Dokumente, und im Vergleich zu 256 Stichproben der hash zu bekommen Ungefähre Ergebnisse. Unter diesen Bedingungen sind die Methoden in etwa die gleiche Geschwindigkeit, aber fuzzy gibt genaue Ergebnisse und nicht brauchen, dass extra-Speicherplatz. Ich denke, dieser Ansatz ist nur sinnvoll für "sehr fuzzy" - Abfragen wie hamming-Distanz von größer als 3.

Habe ich begonnen, an einer Lösung um dieses selbst. Ich habe nur bisher getestet gegen ein Datensatz von rund 3,8 Millionen Dokumente, und ich beabsichtige, zu drängen, dass die nach oben von zehn Millionen.

Meine Lösung bisher ist:

Schreiben einen einheitlichen scoring-Funktion, und registrieren Sie es als plugin. Dann rufen Sie diese beim Abfragen anpassen der _score Wert der Dokumente, wie Sie kommen zurück.

Als ein groovy-Skript, die Zeit, die zum ausführen des benutzerdefinierten scoring-Funktion wurde extrem unscheinbar, aber schreiben Sie als einen einheitlichen scoring-Funktion (wie gezeigt, in diesem Jahre gekommenen blog-post: http://www.spacevatican.org/2012/5/12/elasticsearch-native-scripts-for-dummies/) war um Größenordnungen schneller.

Meine HammingDistanceScript sah so etwas wie dieses:

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);
    }
}

Es ist erwähnenswert an dieser Stelle, dass meine Hashwerte sind hex-codiert-Binär-strings. So, das gleiche wie deins, aber hex-codiert reduzieren den storage-Größe.

Auch, ich erwarte einen param_field parameter, der angibt, welches Feld Wert, die ich tun will hamming-Distanz gegen. Sie nicht brauchen, um dies zu tun, aber ich verwende das gleiche script für mehrere Felder, so dass ich tun 🙂

Ich benutze es in Anfragen wie diese:

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"
            }
          }
        }
      ]
    }
  }
}'

Ich hoffe das hilft in irgendeiner Weise!

Andere Informationen, die möglicherweise nützlich für Sie, wenn Sie diesen Weg gehen:

1. Denken Sie daran, die es-plugin.Eigenschaften Datei

Diese muss kompiliert werden, die in der Wurzel Ihrer jar-Datei (wenn Sie kleben Sie es in /src/main/resources dann bauen Sie Ihr Glas, es gehe in die richtige Stelle).

Sah meins so aus:

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. Verweisen Sie Ihre benutzerdefinierte NativeScriptFactory impl in elasticsearch.yml

Genau wie auf im Alter blog-post.

Sah meins so aus:

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

Wenn Sie dies nicht tun, es zeigt immer noch bis auf die plugins-Liste (siehe später), aber Sie erhalten Fehler, wenn Sie versuchen, es zu sagen, dass elasticsearch kann es nicht finden.

3. Nicht die Mühe mit dem elasticsearch-plugin-Skript, um es zu installieren

Es ist nur ein Schmerz, der Esel und alles, was es scheint zu tun ist, packen Sie Ihre Sachen - ein bisschen sinnlos. Statt, nur kleben Sie es in %ELASTICSEARCH_HOME%/plugins/hamming_distance
und neu starten elasticsearch.

Wenn alles geklappt hat, sehen Sie, dass es geladen wird elasticsearch Start:

[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]

UND wenn Sie rufen Sie die Liste der plugins, die es werden da sein:

curl http://localhost:9200/_cat/plugins?v

produziert so etwas wie:

name        component                version type url
Junta       hamming_distance         0.1.0   j

Erwarte ich um testen zu können, gegen die nach oben von zehn Millionen Dokumenten innerhalb der nächsten Woche oder so. Ich werde versuchen, und denken Sie daran, pop zurück und aktualisieren diese mit den Ergebnissen, wenn es hilft.

Habe ich verwendet @ndtreviv ist Antwort als Ausgangspunkt. Hier sind meine Notizen für ElasticSearch 2.3.3:

1. es-plugin.properties Datei heißt jetzt plugin-descriptor.properties

2. Du keinen Verweis auf die NativeScriptFactory im elasticsearch.yml stattdessen erstellen Sie eine weitere Klasse neben Ihrem 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;
        }
    }
}

1. Dann die Referenz dieser Klasse, die in Ihrem plugin-descriptor.properties Datei:

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

1. Sie die Abfrage, indem der name, den Sie in dieser Zeile: module.registerScript("hamming-distance", HammingDistanceScriptFactory.class); im 2.

Hoffe, dies hilft, die nächste Arme Seele, die zu tun hat mit der beschissenen ES docs.