在Elasticsearch中通过pHash距离进行相似图像搜索

Question

类似图像搜索问题

• 数百万张图片通过pHash进行哈希处理并存储在 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 位，并使用四个模糊查询进行四组搜索。

分析器：

{
   "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，只返回必须找到的图像子集，但结果集较小且速度快。使用 minimum_should_match == 3 返回的图片不足所需的图片的95％，但我们需要像 minimum_should_match == 2那样达到100％（或99.9％）。

我们尝试了类似的n-grams方法，但无法解决结果太多的问题。

是否有其他数据结构和查询的解决方案？

编辑：

我们注意到评估过程中存在错误，并且 minimum_should_match == 2 返回了100％的结果。但是之后处理时间平均为5秒。我们将看看优化脚本是否值得。

- TautrimasPajarskas

---

如果B是每个指纹中设置的整数位数（0 <= B <= 64），那么您可以将B与每个文档一起存储，并最初过滤掉所有B <（sourceB-8）和B>（sourceB + 8）的记录。这应该可以将您考虑的指纹数量至少减少4倍，假设分布均匀。 - Peter Dixon-Moses

虽然Elasticsearch模糊查询和大多数其他带有模糊度参数的API仅支持最大编辑距离为2，但是fuzzy_like_this查询怎么样呢？他们的文档确实指出了这一点在此处。我认为这可能使您避免使用当前的hacky解决方案。当然，您得到的结果不是汉明距离8而是Levenshtein距离8，所以我不确定您是否会重新计算。 - eemp

实际上，几百万个元素并不算太多，即使是1亿个64位整数（每个8字节），也只占用800 MB的内存，并且可以轻松地放在GPU上。我找不到一个好的参考，但我期望CUDA可以在10毫秒内流式处理该数据集，并将精确的列表作为输出产生。特别是在高维空间中，模糊匹配可能不会从索引和数据结构中获得太多好处。即使在排序时，它们也可以通过每秒1740百万个32位键进行处理！ - NikoNyrh

当然，上述内容可能是过早的优化，除非您需要亚秒级响应时间。（您的用例侧重于回忆，因此显然有人投入了大量时间和精力来审查成千上万个汉明距离为8的匹配项，这将花费足够的用户时间/精力，使搜索性能不那么关键。） - Peter Dixon-Moses

Spotify有一个名为annoy的开源工具，可以直接完成这项任务。 - Dane Macaulay

Answer 1

我已经模拟和实现了一种可能的解决方案，避免使用所有昂贵的“模糊”查询。相反，在索引时间，您从64位中取N个长度为M的随机样本。我猜这是局部敏感哈希的一个例子。因此，对于每个文档（以及查询时），采样编号x始终从相同的位位置进行，以在文档之间保持一致的哈希。

查询在bool query的should子句中使用term过滤器，并具有相对较低的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 GB的存储空间（可以通过不存储_source和样本，而仅存储原始二进制哈希来最小化存储空间）
• minimum_should_match = 150（在1024个样本中）
• 使用4百万个文档（4个索引）进行基准测试

您可以使用更少的样本获得更快的速度和更低的磁盘使用率，但是汉明距离在8和9之间的文档没有很好地分离（根据我的模拟）。 1024似乎是should子句的最大数量。

测试运行于单个Core i5 3570K，24 GB RAM，8 GB for 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

我将测试这种方式能否扩展到1500万个文档，但生成和存储每个索引的100万个文档需要3个小时。

你应该测试或计算出要设置多低的minimum_should_match值，以获得所需的错过匹配和错误匹配之间的平衡，这取决于哈希的分布情况。

示例查询（显示了1024个字段中的3个）：

{
  "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 GB的内存用于ES，其余20 GB用于OS。搜索1-3个索引的性能良好（中位数时间为0.1-0.2秒），但搜索更多索引将导致大量磁盘IO，查询开始需要9-11秒！这可以通过少取哈希样本来解决，但是召回率和准确率就不会那么好，或者您可以拥有一台具有64 GB RAM的机器，看看您能走多远。

编辑2：我使用_source: false重新生成数据，并且不存储哈希样本（只存储原始哈希值），这将存储空间减少了60％，约为每个索引6.7 GB（100万个文档）。这不会影响较小数据集的查询速度，但当RAM不足并需要使用磁盘时，查询速度将快40％。

编辑3：我在包含3000万个文档的数据集上测试了编辑距离为2的fuzzy搜索，并将其与256个哈希样本进行比较，以获得近似结果。在这些条件下，两种方法的速度大致相同，但是fuzzy可以给出准确的结果，并且不需要额外的磁盘空间。我认为这种方法仅适用于“非常模糊”的查询，例如汉明距离大于3。

- NikoNyrh

---

不错！优化性能加一分（还有一个可调节性能与召回率的解决方案！）绝对同意，拥有64个二进制索引字段并不能减少基数以获得良好的性能。尽管最初的目标是在汉明距离为8时实现100%的召回率，但OP似乎愿意为速度而牺牲合理的召回率。 - Peter Dixon-Moses

你说得没错，一个好的LSH投影是一个折中的选择，而且随机样本是在不分析数据集的情况下最好的选择。但是考虑到每个特征位都代表图像的某些方面，可以肯定的是，特征的分布不是随机的，并且根据数据集中频率将一些特征智能地组合在一起可能有助于减少每个过滤操作的基数（并且减少过滤操作的数量到<<1024以提高性能）。 - Peter Dixon-Moses

目前我正在使用 _source: false 重新运行这些测试，并仅存储原始的64位哈希（作为字符串），采样模式被索引但不被存储。这将减少约50％的磁盘使用量，我很想看看它是否有助于查询性能。此外，我将使用256个样本运行这些测试，并与内置的 fuzziness 搜索进行比较，其编辑距离为2。 - NikoNyrh

Answer 2

我还使用CUDA方法，并在笔记本电脑上的GeForce 650M显卡上获得了一些不错的结果。使用Thrust库很容易实现。我希望这份代码没有bug（我没有进行彻底测试），但它不应该影响基准测试结果。至少在停止高精度计时器之前，我调用了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)
)

搜索速度比我的 ElasticSearch 更快，并且100％准确，在50毫秒内，CUDA可以流式传输3500万个哈希值！我相信更新的台式机显卡甚至比这更快。此外，随着我们浏览越来越多的数据，我们得到了非常低的方差和一致的线性搜索时间增长率。由于采样数据过多，ElasticSearch在较大查询上遇到了不良的内存问题。

因此，我报告了“从这些N个哈希值中找到与一个单独哈希值H之间的汉明距离为8的哈希值”结果。我运行了500次并报告了百分位数。

有一些核启动开销，但是当搜索空间超过500万个哈希值时，搜索速度是相当稳定的，为每秒7000万个哈希值。自然地，要搜索的哈希值数量的上限由GPU的RAM设置。

更新：我在GTX 1060上重新运行了测试，它每秒可以扫描大约3800万个哈希值 :)

- NikoNyrh

---

你有代码的剩余部分吗？想知道数据集的初始加载性能如何... - Visualize

实际上，主文件在这里：https://github.com/nikonyrh/stackoverflow-scripts/blob/master/32785803_es_image_phash/cpp_cuda_thrust/cpp_cuda_thrust/kernel.cu当然，代码有点临时抱佛脚，但应该很容易理解。我想最耗费时间的步骤是从某个地方加载哈希值，无论是从文件还是数据库中。但无论如何，它应该非常快。实际上，您甚至可以使用CUDA“统一内存”来分配比GPU RAM更大的数据集。 - NikoNyrh

这是一个问题，即thrust::copy_if是否可以跨GPU进行扩展。我看不出为什么它不能。 - NikoNyrh

我正在尝试看看能否将其用于Python网络爬虫脚本，以便定期使用查询哈希查询哈希数据库，并最终获得匹配Gpu中的内容。我正在考虑使用pycuda来编译和执行CUDA代码，但不确定是否需要放弃使用thrust API...您对此有任何了解或可以提供任何指针吗？ - Luca Guarro

Answer 3

我已经开始着手解决这个问题。到目前为止，我已经对大约380万份文档的数据集进行了测试，并打算将其推广到数千万份文档。

我的解决方案如下:

编写本地评分函数并将其注册为插件。然后在查询时调用此函数，以调整返回文档的_score值。

作为一种Groovy脚本，运行自定义评分功能所需的时间非常不理想，但是将其编写为本地评分函数（正如在这篇有点过时的博客文章中所演示的那样：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. 在elasticsearch.yml中引用您的自定义NativeScriptFactory实现
就像老博客文章中所述。

我的看起来是这样的：

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

如果您不这样做，它仍会显示在插件列表中（见后文），但是当您尝试使用它时，会出现错误，说elasticsearch找不到它。

3. 不要费心使用elasticsearch插件脚本来安装它。 这只是一个麻烦的事情，似乎它所做的就是解压缩你的东西 - 有点无意义。相反，只需将其放入%ELASTICSEARCH_HOME%/plugins/hamming_distance并重新启动elasticsearch即可。

如果一切顺利，您将在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

我希望在接下来的一周左右能够对数千万份文档进行测试。如果有帮助的话，我会尽力记得回来更新测试结果。

- ndtreviv

---

我了解您拥有一个具有非常快速处理速度的O(n)算法。这看起来像是一个完美的解决方案，可以作为我们原始模糊查询方法的后处理工具。也许您可以将它们两个结合起来使用？您只需要处理其中的一小部分记录 - 处理速度应该很快。 - TautrimasPajarskas

@TautrimasPajarskas 为了明确：您的意思是在标记化的哈希上使用模糊查询，以清除那些明显不符合要求的结果，然后再使用此评分脚本清理其余结果吗？ - ndtreviv

@TautrimasPajarskas PS：目前这个评分脚本在大约380万个结果中返回约700毫秒。 - ndtreviv

使用64位哈希，在elasticsearch 2.3.1上结合模糊匹配和本地评分脚本，我可以在约31万个文档中在1秒左右得到结果。使用简单评分脚本，第一个查询需要15秒，之后只需5秒（看起来es正在缓存某些内容）。@TautrimasPajarskas - ndtreviv

Answer 4

最近提出的FENSHSES方法[1]似乎是在Elasticsearch上进行汉明空间中r-邻居搜索的最先进方法。

[1]Mu，C，Zhao，J.，Yang，G.，Yang，B。和Yan，Z.，2019年10月。全文搜索引擎上汉明空间中快速准确的最近邻居搜索。在相似性搜索和应用国际会议上（第49-56页）。斯普林格，Cham。

- dragon.warrior.nyc

Answer 5

我以@ndtreviv的答案为起点。以下是我对ElasticSearch 2.3.3的注释:

1. es-plugin.properties文件现在改名为plugin-descriptor.properties

2. 您不需要在elasticsearch.yml中引用NativeScriptFactory，而是在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. 你可以通过提供在第2步中使用的名称 module.registerScript("hamming-distance", HammingDistanceScriptFactory.class); 来查询。

希望这能帮助下一个不得不处理糟糕的ES文档的可怜人。

- mirosval

---

还没有。但我仍然认为这是一个临时解决方案，因为它是O(n)的。以后在生产中必须想出更聪明的东西。 - mirosval

哈！我刚刚更新了我们的插件，使其与2.3.1版本兼容，并且不得不经历这个过程。真希望我先读了这篇文章！哎，算了。值得一提的是，我们正在使用的插件已经开源了，尽管我还没有提交ES 2.x的更改。https://github.com/CameraForensics/elasticsearch-plugins - ndtreviv

PS：使用我的本地插件，我可以在第一次查询时在31m个文档内获得结果，并且之后的查询时间为5秒。在评分之前首先使用模糊过滤器来限制结果集合，有时甚至可以在小于1秒的时间内返回结果。大多数情况下，大约需要1-2秒钟左右。但这是在64位哈希上的结果。 - ndtreviv

Answer 6

这里有一个不太优雅，但确切的（暴力）解决方案，需要将您的特征哈希拆分为单个布尔字段，以便您可以运行以下查询：

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

我不确定这个方法与模糊搜索相比表现如何，但是FLT实现被弃用的原因是它必须访问索引中的每个词来计算编辑距离。

(然而在这里/上面，您正在利用Lucene的底层倒排索引数据结构和优化的集合操作，这应该对您有利，因为您可能有相当稀疏的特征)

- Peter Dixon-Moses

---

你启发了我们另一种策略，我们将尝试使用它。不再创建64个字段，而是添加一个字段，将所有64个状态存储在一个字符串中：001 010 020 031 040 ... 631（位置+状态），这与您的建议相同，但性能可能会有所不同。 - TautrimasPajarskas

当然。如果你想进一步优化，你可以将“设置位”存储为整数（1-64值的数组），并使用否定（not query）来测试未设置的位。这样你就可以减少集合大小，并避免数字值的字符串比较。 - Peter Dixon-Moses

很高兴这个答案给你带来了可行的解决方案！回忆起来没有问题吧？（是否成功获取到汉明距离为8的图像的100％？） - Peter Dixon-Moses

有许多方法可以探索提高性能。您是否愿意打开另一个帖子，详细介绍您的收集大小、集群配置（节点/副本数量、硬件类型（内存/CPU）、存储类型（SSD vs 旋转磁盘 vs NAS）等）？ - Peter Dixon-Moses

记录一下，我们也尝试过这个确切的64布尔字段解决方案，性能大多相同。对于1500万个哈希值，需要超过5秒的时间。 - TautrimasPajarskas

Answer 7

这里是64位解决方案，用于改进@NikoNyrh的答案。可以通过使用CUDA内置的__popcll函数和XOR运算符计算汉明距离。

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

- Bahadir