1.一种基于EMD距离的大规模图像数据相似性搜索方法，其特征在于步骤包括：

1)设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据映射函数f，所述图像数据映射函数f包含图像数据和一维实数键值空间Ω(Φ)中键值之间的映射关系；

2)启动一个MapReduce作业MR1，通过MapReduce作业MR1基于查询图像集Q和待检索图像集I估计所述一维实数键值空间Ω(Φ)中各个键值所对应的查询处理负载量；

3)启动一个MapReduce作业MR2，通过MapReduce作业MR2的Map任务基于所述步骤

2)估计得到的查询处理负载量对一维实数键值空间Ω(Φ)进行切割，分别将所述一维实数键值空间Ω(Φ)不同切割区域所对应的查询图像集Q中的图像数据分片或待检索图像集I中的图像数据分片发送给MapReduce作业MR2中的各个Reduce任务；

4)基于所述图像数据映射函数f将MapReduce作业MR2中各个Reduce任务所接收的图像数据分片划分为查询图像集数据分片Q′和待检索图像集数据分片I′并分别映射至一维实数键值空间Ω(Φ)，得到查询图像集数据分片Q′或待检索图像集数据分片I′在一维实数键值空间Ω(Φ)中对应的键值；基于所述待检索图像集数据分片I′在一维实数键值空间Ω(Φ)中对应的键值构建面向EMD距离的索引；

5)所述MapReduce作业MR2中各个Reduce任务分别基于所述面向EMD距离的索引执行查询图像集数据分片Q′中的每个查询对象在待检索图像集数据分片I′上基于EMD距离的相似性搜索；

6)MapReduce作业MR2中的每个Reduce任务将查询图像集数据分片Q′中每个查询对象基于EMD距离的相似性搜索的执行结果取并集输出。

2.根据权利要求1所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于：所述步骤1)中设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据映射函数f时，对于给定任意一组EMD距离对偶线性规划问题的可行解，记为Φ＝{Ψ,Π}，其中Ψ＝{ψ1,…,ψl}和Π＝{π1,…,πl}，其中l表示图像数据的直方图中的数据桶个数，所述图像数据映射函数f通过式(1)计算图像数据集中每张图像X的直方图hx＝{x1,...,xl}的键值key(hx,Φ)，从而将图像X映射至一维实数键值空间Ω(Φ)中；

f(X,Φ)＝key(hx,Φ)＝∑iψi·xi (1)

式(1)中，f(X,Φ)表示将图像X基于一组EMD距离对偶线性规划问题的可行解Φ映射至一维实数键值空间Ω(Φ)的映射函数，key(hx,Φ)表示图像X的直方图hx＝{x1,...,xl}的键值， 表示将所有(ψi·xi)的值求和且1≤i≤l，其中l表示图像数据的直方图中的数据桶个数，ψi表示一组可行解Φ＝{Ψ,Π}中向量Ψ＝{ψ1,…,ψl}的第i维的取值，xi表示图像X的直方图hx＝{x1,...,xl}的第i维的取值。

3.根据权利要求2所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于：所述步骤1)中设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据映射函数f时，所述图像数据映射函数f将EMD距离值相近的直方图所对应的图像数据映射至一维实数键值空间Ω(Φ)中的临近键值区域内，与任意目标图像X相似的所有图像Y均满足式(2)，其中目标图像X的直方图为hx＝{x1,...,xl}，图像Y的直方图为hy＝{y1,...,yl}；且相似图像Y的直方图hy的键值key(hy,Φ)必落在式(3)所示的一维实数键值空间Ω(Φ)中的键值区间内；

EMD(hx,hy)≤θ (2)

式(2)中，hx表示目标图像X的直方图，hy表示与目标图像X相似的图像Y的直方图，EMD(hx,hy)表示直方图hx和直方图hy之间的EMD距离，θ表示给定的相似性阈值；

式(3)中，ψi表示表示一组可行解Φ＝{Ψ,Π}中向量Ψ＝{ψ1,…,ψn}的第i维的取值，πi表示表示一组可行解Φ＝{Ψ,Π}中向量Π＝{π1,…,πn}的第i维的取值， 表示求取所有(ψi+πi)值中的最小值且1≤i≤l，其中l表示图像数据的直方图中的数据桶个数，key(hx,Φ)表示直方图hx基于可行解Φ计算得到的键值，Φ表示EMD距离对偶线型规划问题的一组可行解，θ表示给定的相似性阈值，其中ckey(hx,Φ)表示键值key(hx,Φ)的对称键值，ckey(hx,Φ)的表达式如式(4)所示；

式(4)中， 表示将所有(πj·xj)的值求和且1≤j≤l，其中l表示图像数

据的直方图中的数据桶个数，πj表示一组可行解Φ＝{Ψ,Π}中向量Π＝{π1,…,πn}的第j维的取值，xj表示直方图hx＝{x1,...,xl}的第j维的取值。

4.根据权利要求3所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于：所述步骤2)启动的MapReduce作业MR1包括m个Map任务和1个Reduce任务；

所述MapReduce作业MR1的每一个Map任务执行下述步骤：①对查询图像集Q的文件分块Qi或待检索图像集I的文件分块Ii进行随机采样；②、挑选出基数分别为|Qi|·p和|Ii|·p的两个图像数据子集分发给MapReduce作业MR1的Reduce任务，其中p表示预设的采样比率；所述MapReduce作业MR1的Reduce任务执行下述步骤：①、接收来自m个Map任务发送的图像数据，将所接收的图像数据根据其携带的标签划分成查询图像集Q的子集Q′、待检索图像集I的子集I′；②、基于EMD距离相似性搜索算法执行查询图像集Q的子集Q′中的每一个查询对象qi在待检索图像集I的子集I′上的相似性检索，并记录相似性检索的时间代价ci作为其查询处理负载代价；③、将每一个查询对象qi的直方图 基于给定用于数据划分的一组EMD距离对偶线性规划问题的可行解Φpartition计算得到的键值 和该查询对象qi对应的查询负载代价ci组成二元组④、执行完查询图像集子集Q的子集Q′中所有查询对象qi的查询

后，将得到的由所有二元组 组成的“键值-查询负载代价”二元组的

序列 写入分布式文件系统中。

5.根据权利要求4所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于，所述步骤3)启动的MapReduce作业MR2包括m个Map任务和n个Reduce任务，其中每一个Map任务执行下述步骤：

3.1)从分布式文件系统中读取“键值-查询负载代价”二元组的序列

3.2)将所述序列 中的每个二元组 基

于其键值 进行从小到大排序得到排序后的列表为Listsorted{}，同时累加其中的查询负载代价ci得到总查询负载代价C；

3.3)基于排序后的列表Listsorted{}找到所述可行解Φpartition所对应的一维实数键值空间Ω(Φpartition)中的n-1个分位数{keyi,…,keyn-1}，使得排序后的列表Listsorted{}中落在任意两个相邻分位数区间内的键值的累计查询负载值约等于平均查询负载值 其中平均查询负载值 为总查询负载C除以MapReduce作业MR2中Reduce任务的数量n所得到的结果；

3.4)从分布式存储系统中读取查询图像集Q和待检索图像集I中的每一个数

据分块；针对读取的每一个数据分块包含的图像数据d，首先抽取图像数据d的直方图hd，并基于所述直方图hd和所述EMD距离对偶线性规划问题的可行解Φpartition计算出所述图像数据d在所述可行解Φpartition所对应的一维实数映射空间Ω(Φpartition)中的键值key(hd,Φpartition)；然后对图像数据d的键值key(hd,Φpartition)进行判断，若key(hd,Φpartition)≤key1，则将图像数据d发送给第1个Reduce任务；若keyi≤key(hd,Φpartition)≤keyi+1，则将图像数据d发送给第i+1个Reduce任务；若keyn-1≤key(hd,Φpartition)，则将图像数据d发送给第n个Reduce任务，其中key1表示所述n-1个分位数{keyi,…,keyn-1}中的第1个分位数，keyi表示所述n-1个分位数{keyi,…,keyn-1}中的第i个分位数，keyi+1表示所述n-1个分位数{keyi,…,keyn-1}中的第i+1个分位数，keyn-1表示所述n-1个分位数{keyi,…,keyn-1}中的第n-1个分位数。

6.根据权利要求5所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于，所述步骤4)的详细步骤包括：

4.1)MapReduce作业MR2中各个Reduce任务将MapReduce作业MR2中各个Map任务发送过来的图像数据分片根据各个图像数据携带的标签划分成查询图像集数据分片Q′和待检索图像集数据分片I′，所述查询图像集数据分片Q′为查询图像集Q的子集，所述待检索图像集数据分片I′为待检索图像集I的子集；

4.2)已知由L组EMD距离对偶线性规划问题的可行解构成的可行解集合，记为SΦ＝{Φ1,…,ΦL}，对待检索图像集数据分片I′中的每一个待检索图像对象i，其中1≤i≤L，基于可行解集合SΦ中每组可行解Φi计算待检索图像对象i的直方图hi在Φi所对应的一维映射空间Ωi(Φi)内的键值key(hi,Φi)，因此针对待检索图像集数据分片I′中的每个待检索图像对象i而言，可得到相对于L组可行解的L个键值{key(hi,Φi),…,key(hi,ΦL)}；

4.3)以待检索图像集数据分片I′中每张图像基于所述可行解集合SΦ中同一组可行解Φi计算得到的键值为B+树的键值构建一棵B+树索引结构，记为B+(Φi)，因为所述可行解集合SΦ一共包含L组可行解，因此共为待检索图像集数据分片I′构建了L棵B+树索引结构，记为{B+(Φ1),...,B+(ΦL)}；对于查询图像集数据分片Q′中的任一查询对象q，基于所述L棵B+树索引结构可以得到L组查询候选集{Ca(q,Φ1),...,Ca(q,ΦL)}，则所述L组查询候选集{Ca(q,Φ1),...,Ca(q,ΦL)}的交集Ca(q,Φ1)∩...∩Ca(q,ΦL)即构成了查询对象q在待检索图像集数据分片I′上的查询候选集Ca(q)。

7.根据权利要求6所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于，所述步骤4.2)中已知由L组EMD距离对偶线性规划问题的可行解构成的可行解集合中L的取值为3。

8.根据权利要求7所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于，所述步骤5)通过所述MapReduce作业MR2中各个的Reduce任务分别基于所述面向EMD距离的索引执行查询图像集数据分片Q′中的每个查询对象在待检索图像集数据分片I′上基于EMD距离的相似性搜索的详细步骤包括：

5.1)将查询图像集数据分片Q′中的每个查询对象q按照其基于已知L组EMD距离对偶线性规划问题的可行解集合SΦ中某组可行解Φi计算得到的一维键值进行从小到大排序；

+ + +

5.2)基于所述B树索引结构{B (Φ1),...,B(ΦL)}，根据步骤5.1)中从小到大排序得到的顺序，执行查询图像集数据分片Q′中的每个查询对象q在待检索图像集数据分片I′上基于EMD距离的相似性搜索，为每个查询对象q检索出待检索图像集数据分片I′中与其EMD距离相近的所有查询对象。

9.根据权利要求8所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于，所述步骤5.2)的详细步骤包括：

+ + +

5.2.1)基于所述B树索引结构{B (Φ1),...,B(ΦL)}，并利用式(3)所示的索引过滤结论获取每个查询对象q在待检索图像集数据分片I′上的查询候选集Ca(q)；并统计所述可行解集合SΦ＝{Φ1,…,ΦL}中每组EMD距离对偶线性规划问题的可行解Φi对待检索图像集数据分片I′中无关图像数据的过滤性能；

5.2.2)在步骤5.1)从小到大排序得到的顺序的基础上，若每个查询对象q的上一查询对象q′的查询结果集RS(q′)不为空，则基于三角不等式理论过滤每个查询对象q的查询候选集Ca(q)，得到约简后的查询候选集Ca(q)1；

5.2.3)基于EMD距离的下界函数LBIM和基于EMD距离的上界函数UBp进一步约简每个查询对象q的查询候选集Ca(q)1，得到约简后的查询候选集Ca(q)2；

5.2.4)针对每个查询对象q的查询候选集Ca(q)2中的每个图像数据i，计算图像数据i的直方图hi和对应的查询对象q的直方图hq之间的EMD距离EMD(hq,hi)，若该EMD距离EMD(hq,hi)小于给定的相似性阈值θ，则判定图像数据i为查询对象q的查询结果，将查询结果二元组插入查询对象q的结果列表RS(q)，并写入分布式文件系统中；

同时，在计算计算图像数据i的直方图hi和对应的查询对象q的直方图hq之间的EMD距离EMD(hq,hi)的过程中会顺带产生一组新的EMD距离对偶线性规划问题的可行解 将所述可行解 插入新可行解候选列表

5.2.5)从所述新可行解候选集合 中随机挑选一组新可行解Φnew，根据统计得到的所述可行解集合SΦ＝{Φ1,…,ΦL}中每组可行解Φi对所述待检索图像集数据分片I′中无关图像数据的过滤性能，用Φnew替换掉所述可行解集合SΦ＝{Φ1,…,ΦL}中过滤性能最差的那组可行解；

5.2.6)将各个查询对象q的查询结果集RS(q)作为查询对象q检索出的待检索图像集数据分片I′中与其EMD距离相近的所有查询对象输出。

10.根据权利要求9所述的基于EMD距离的大规模图像数据相似性搜索方法，其特征在于，所述步骤5.2.2)中基于三角不等式理论过滤每个查询对象q的查询候选集Ca(q)的详细步骤包括：针对每个查询对象q，对于查询对象q中任意隶属于查询候选集Ca(q)中的查询候选图像i′，若查询候选图像i′也在位于查询对象q之前的上一查询对象q′的查询结果集RS(q′)中，且查询候选图像i′若满足下式(5)，则判定查询候选图像i′不是查询对象q的查询结果，将查询候选图像i′从查询候选集Ca(q)中剔除；

UBp(hq,hq')+EMD(hq',hi')≥θ (5)

式(5)中，UBp表示基于EMD距离的上界函数，EMD(hq',hi')表示直方图hq′和直方图hi′之间的EMD距离，hq表示查询对象q的直方图，hq′表示查询对象q之前的上一查询对象q′的直方图，hi′表示查询对象q的查询候选集Ca(q)中的查询候选图像i′的直方图，且该查询候选图像i′是查询对象q之前的上一查询对象q′的查询结果，θ表示给定的相似性阈值。