用MapRedeuce实现阈值Top-k查询算法
Top-k查询定义:给定m个按照降序排列的排序表Li,每张列表包含对象Ox的一个属性在该列的评分,最终结果返回评分最高的前k个对象.
例:
P
L1
L2
L3
1
2
3
4
5
6
7
如图,m=3,3个按降序排列的列表包含了对象Ox在不同列表中的属性评分,
例如O1在L1的属性,评分为10,在L2的列表中,评分为2,在L3列表中,评分为10分,
所以最后O1的总体得分=10+2+10=22分
Top-k的朴素算法,就是把所有的对象得分计算出来,然后求出总体得分.
这里我设计的算法是:
Input：m个排序列表
Output：得分最高的前k个结果
Step1：中心节点从各子节点的数据列上读取前k个位置上的对象O及其分数，计算这些对象的部分和V`(Ox).
Step2：对取得部分和最高的两个对象Ox1，Ox2，分别计算其真实值，V(Ox1)和V(Ox2)，并将V(Ox1)和V(Ox2)存入临时候选集合C中，记真实值第k的对象值为τ1，T=τ1/m.
Step3：1.各子节点将位置≥T的对象发送给中心节点，中心节点将Step1中未计算对象的部分和V`(O)补全，实值若序列中不存在对象Ox，则将该序列中对象的得分以V=0计算.
2.若序列中存在某对象Oy的值在各个列表中都被访问到，则将对象Oy及其真实值V(Oy)存入临时候选集C中，并更新临时候选集，将此时临时候选集C中的第k位的值记为τ2.
3.计算上界：U=U1`(O)+U2`(O)+……+Um`(O)，若列表中不存在对象O的得分，则以T代替，若U(O)≤τ2，则将该对象排除.
Step4：此时，将仍剩余的对象作为候选集合S，中心节点将S发往各子节点，子节点在计算出各对象的真实值后返回给中心节点，中心节点确定Top-k对象.
参照上例,本算法的计算过程如下:
Step1：计算前两个位置的部分和:
V`(O1)=10+0+10=20；V`(O2)=0+10+0=10;V`(O3)=8+0+10=18；V`(O4)=0+9+0=9.
获得两个最高的部分和结果分别为：V`(O1)=20；V`(O3)=18；对取得部分和最高的两个对象V`(O1)=19；V`(O3)=18；计算其真实值，并存入C1.
V(O1)=10+2+10=22；V(O3)=8+3+10=21；设其真实值第k个对象的值为τ1；T=τ1/m=21/3=7
Step2：
(1)将值≥T位置上的对象发送至中心节点,即:L1发送P=6之前的序列;L2发送P=4之前的序列;L3发送P=6之前的序列;
(2)补全V`(O):V`(O5)=8+0+0=8;V`(O6)=8+8+7=23;V`(O7)=0+0+8=8；V`(O8)=0+0+0=0；V`(O9)=0+0+7=7；(假如存在对象在三个节点都访问到，则将对象和值存在C1，并更新C1，此时C1中最高k位为τ2，τ2=V(O1)=22)
(3)计算上界：U(O5)=8+T+T=8+7+7=22(排除)；U(O7)=T+T+8=22(排除)；U(O8)=T+T+T=21(排除)；U(O9)=T+T+7=21(排除).
Step3：得出候选集合S：S={O1，O2，O3，O4，O6}
中心节点把S发往各个子节点，计算出最后的Top-k对象为：V(O6) =23; V(O6) =22
通过该例表明，相对于TPUT算法，NT-TPUT算法由于高阈值的设定而可以提前结束访问，同时由于上界设定的提高，可以排除更多的对象.