在Elasticsearch中通过pHash距离搜索类似的图像
Tau*_*kas 36 image hamming-distance elasticsearch phash
类似的图像搜索问题
- 数百万张图像在Elasticsearch中进行了标记和存储.
- 格式为"11001101 ... 11"(长度64),但可以更改(最好不要).
给定主题图像的散列"100111..10",我们希望在汉明距离为8的 Elasticsearch索引中找到所有相似的图像散列.
当然,查询可以返回距离大于8的图像,Elasticsearch或外部的脚本可以过滤结果集.但总搜索时间必须在1秒左右.
我们目前的映射
每个文档都有images包含图像哈希的嵌套字段:
{
"images": {
"type": "nested",
"properties": {
"pHashFingerprint": {"index": "not_analysed", "type": "string"}
}
}
}
我们的穷解决方案
事实: Elasticsearch模糊查询仅支持最大2的Levenshtein距离.
我们使用自定义标记生成器将64位字符串拆分为4组16位,并使用4个模糊查询进行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秒.我们将看看脚本是否值得优化.
Nik*_*yrh 16
我已经模拟并实现了一个可能的解决方案,避免了所有昂贵的"模糊"查询.而不是在索引时间,你从这64位中取出N随机的M位样本.我想这是局部敏感哈希的一个例子.因此,对于每个文档(以及查询时),x始终从相同的位位置获取样本编号,以便在文档之间进行一致的散列.
查询term在bool query's should子句中使用过滤器,minimum_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 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个匹配/索引/查询,并且应该更加真实.
之前的图表中显示了新的结果,我有ES的4 GB内存和OS的剩余20 GB.搜索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的"模糊"查询有用.
Nik*_*yrh 10
即使在笔记本电脑的GeForce 650M显卡上,我也实现了CUDA方法并取得了一些不错的效果.使用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设置.
我本人已经开始寻找解决方案。到目前为止，我仅对约380万份文档的数据集进行了测试，现在我打算将其提高到数千万。
到目前为止，我的解决方案是：
编写一个本地评分函数，并将其注册为插件。然后在查询时调用此命令以调整_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.
在老化的博客文章上，在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
我希望在下一周左右的时间内能够对超过千万的文档进行测试。如果有帮助，我会尽量记住弹出并使用结果进行更新。
这是一个不优雅但精确（强力）的解决方案，需要将特征哈希解构为单独的布尔字段，以便您可以运行如下查询：
"query": {
"bool": {
"minimum_should_match": -8,
"should": [
{ "term": { "phash.0": true } },
{ "term": { "phash.1": false } },
...
{ "term": { "phash.63": true } }
]
}
}
我不确定这与 fuzzy_like_this 相比会如何执行，但FLT实现被弃用的原因是它必须访问索引中的每个术语来计算编辑距离。
（而这里/上面，您正在利用 Lucene 的底层倒排索引数据结构和优化的集合操作，鉴于您可能具有相当稀疏的功能，这应该对您有利）