41

相似图片搜索问题

  • 数百万张经过 pHash 处理的图像并存储在 Elasticsearch 中。
  • 格式为“11001101...11”（长度为 64），但可以更改（最好不要）。

给定主题图像的哈希“100111..10”，我们希望在8 的汉明距离内的 Elasticsearch 索引中找到所有相似的图像哈希。

当然query可以返回距离大于8的图片，Elasticsearch或者外部的脚本可以过滤结果集。但总搜索时间必须在 1 秒左右。

我们当前的映射

images每个文档都有包含图像哈希的嵌套字段：

{
  "images": {
    "type": "nested", 
    "properties": {
      "pHashFingerprint": {"index": "not_analysed", "type": "string"}
    }
  }
}

我们糟糕的解决方案

事实： Elasticsearch 模糊查询仅支持最大 2 的 Levenshtein 距离。

我们使用自定义标记器将 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_match3 和 4，则只返回必须找到的图像子集，但结果集小而快。低于 95% 的所需图像返回minimum_should_match== 3，但我们需要 100%（或 99.9%），如minimum_should_match== 2。

我们用 n-gram 尝试了类似的方法，但在太多结果的类似方式中仍然没有太大的成功。

其他数据结构和查询的任何解决方案？

编辑：

我们注意到，我们的评估过程中有一个错误，minimum_should_match== 2 返回 100% 的结果。但是，之后的处理时间平均需要 5 秒。我们将看看脚本是否值得优化。

4

7 回答 7

20

我已经模拟并实现了一个可能的解决方案，它避免了所有昂贵的“模糊”查询。相反，在索引时，您从这 64 位中N抽取随机位样本。M我猜这是Locality-sensitive hashing的一个例子。因此，对于每个文档（以及在查询时），样本编号x总是取自相同的位位置，以便在文档之间具有一致的散列。

查询在's子句中使用阈值相对较低的term过滤器。较低的阈值对应于较高的“模糊性”。不幸的是，您需要重新索引所有图像来测试这种方法。bool queryshouldminimum_should_match

我认为{ "term": { "phash.0": true } }查询表现不佳，因为平均每个过滤器匹配50%文档。使用 16 位/样本，每个样本匹配2^-16 = 0.0015%文档。

我使用以下设置运行测试：

  • 1024 个样本/哈希（存储到 doc 字段"0"- "ff"）
  • 16 位/样本（存储到short类型，doc_values = true）
  • 4 个分片和 100 万个哈希/索引，大约 17.6 GB 的存储空间（可以通过不存储_source和采样来最小化，只有原始二进制哈希）
  • minimum_should_match= 150（共 1024 个）
  • 以 400 万份文档（4 个索引）为基准

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

测试在单个 Core i5 3570K、24 GB RAM、8 GB 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：我fuzzy在一组 3000 万个文档上测试了编辑距离为 2 的搜索，并将其与 256 个随机散列样本进行比较以获得近似结果。在这些条件下，方法的速度大致相同，但fuzzy给出了准确的结果，并且不需要额外的磁盘空间。我认为这种方法仅适用于“非常模糊”的查询，例如大于 3 的汉明距离。

于 2015-10-07T17:27:11.280 回答
11

我还实现了 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 可以流过 3500 万个哈希！我敢肯定，较新的桌面卡甚至比这更快。随着我们处理越来越多的数据，我们也会得到非常低的方差和搜索时间的一致线性增长。由于采样数据膨胀，ElasticSearch 在较大的查询中遇到了内存问题。

所以在这里我报告“从这 N 个哈希中，找到距离单个哈希 H 8 汉明距离内的那些”的结果。我运行了这 500 次并报告了百分位数。

搜索性能

有一些内核启动开销，但在搜索空间超过 500 万哈希后，搜索速度相当一致，为 7 亿哈希/秒。自然，要搜索的哈希数的上限由 GPU 的 RAM 设置。

搜索性能

更新：我在 GTX 1060 上重新运行测试，它每秒扫描大约 38 亿个哈希 :)

于 2015-10-27T08:28:20.300 回答
5

我自己已经开始解决这个问题。到目前为止，我只针对大约 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 impl
就像在旧博客文章中一样。

我的看起来像这样：

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

我希望能够在下周左右对数以千万计的文档进行测试。如果有帮助，我会尽量记住弹出并用结果更新它。

于 2016-02-09T13:58:52.730 回答
3

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

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

于 2019-12-26T03:44:16.730 回答
2

这是@NikoNyrh答案的64 位解决方案。汉明距离可以通过使用带有 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;
    }
};
于 2018-01-08T18:42:55.903 回答
2

我以@ndtreviv 的回答为起点。这是我对 ElasticSearch 2.3.3 的注释：

  1. es-plugin.properties文件现在被称为plugin-descriptor.properties

  2. 您没有在 中引用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;
        }
    }
}
  1. 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
  1. 您可以通过提供您在此行中使用的名称进行查询：module.registerScript("hamming-distance", HammingDistanceScriptFactory.class);in 2。

希望这可以帮助下一个必须处理糟糕的 ES 文档的可怜人。

于 2016-06-20T14:08:00.867 回答
2

这是一个不优雅但精确（蛮力）的解决方案，需要将您的特征哈希解构为单独的布尔字段，以便您可以运行如下查询：

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

我不确定这与fuzzy_like_this 的表现如何，但不推荐使用FLT实现的原因是它必须访问索引中的每个术语来计算编辑距离。

（而在这里/上面，您正在利用 Lucene 的底层倒排索引数据结构和优化的集合操作，鉴于您可能具有相当稀疏的功能，这应该对您有利）

于 2015-09-29T15:18:17.123 回答