Fagin’s Algorithm and Threshold Algorithm
Fagin算法和Threshold算法都是Top-K排序领域的经典算法(K代表只要对前K个值排序值)，不同于传统Top-k对一维数组前K个值排序，Fargin和Threshhold算法适用于参考多个排序指标时对前k个物品排序。
比如说我要去旅游，选酒店的时候我有两个指标：
- 价格合适
- 好评率
那么我在网站上得到了下面的酒店信息：
能够想到的一种常规的做法是对两种评价指标分别赋予一个权重，然后计算两种指标的加权得分:
然后按照score排序取TOP-k个作为结果。
这样的做法存在一个问题，就是当候选集合比较大时（酒店数目较多），我们对所有的候选都计算出得分进行排序比较会浪费大量的计算资源，时间开销也很大，而我们真正所关注的就只有很少的K个最优的Hotel，Fagin’s Algorithm就是针对这样的问题的一种Top-k检索算法。
Fagin’s Algorithm
Fagin’s Algorithm的策略如下：
每一轮在不同的指标中依次选取排名最靠前的候选，直到从多个指标序列中选出的候选中有K个已经被送所有的指标列表中选出来了，这K个就是最终给的TOP-k结果。
结合上面选酒店的例子，假设我们要选top-3的酒店：
- 第一轮，选取两个列表中最靠前的：
- 第二轮，选取两个列表中第二靠前的：
- 第三轮，选取两个列表中第三靠前的，此时，已经有一个候选Hotel——Novotel在所有的评价指标（列表）中被选中了：
- 第四轮，选取两个列表中第四靠前的：
- 第五轮，选取两个列表中第五靠前的，此时，有三个候选Hotel——Novotel、Hilton、Ibis在所有的评价指标（列表）中被选中了，结束：
因此最终通过Fagin’s Algorithm计算出来的TOP-3的Hotel结果就是：
再对比一下之前的方式，可以看出对于后面的大量不可能成为结果的候选集节省了计算和时间开销。
Fagin’s Threshold Algorithm
在上面的算法基础之上，提出了更为严谨的Fagin’s Threshold Algorithm：
还是上面的例子：
将初始threshold设置为无穷大
第一轮，在Cheapness和Rating表中选取最高的，计算其在所有评价指标下的综合得分，放入Top-k列表中，并计算第一行的threshold：
根据Fagin’s Threshold算法，如果当前的th值已经小于top表中的所有值，就认为后面不可能再出现比top表中更好的候选了，即可停止计算，此时还不能够停止。
第二轮，在Cheapness和Rating表中选取第二高的，计算其在所有评价指标下的综合得分，更新Top-k表，计算threshold，还不能够停止计算
第三轮，
第四轮，
此时threshold已经低于所有的top-k候选了，后面不能再有更好的候选了，因此停止计算，得到结果。
海量数据TOP-k查询
top K问题很适合采用MapReduce框架解决，用户只需编写一个Map函数和两个Reduce 函数，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解决该问题。具体而言，就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reduce task；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce 函数，统计所有Reduce task，输出数据中的top K即可。