现有100万酒店坐标和20亿地标,里面记录地标的经纬度，请设计mapreduce计算所有酒店1公里范围内的地标
说假设酒店坐标和地标坐标都在一个文件，假设字段为
类型(酒店/地标) id(酒店id/地标id) 纬度 经度
这里需要解决的问题就是在同一个文件中怎么设计map 把同一个酒店1公里范围内的地标找出来，以酒店id为key，地标id为value 传递给reduce来处理。

放弃纬度经度了，直接用一个欧式二维平面图来解这道题目
把坐标换成X和Y，最小单位米，没有小数点
有两种办法，但都需要2个MR来解决
1、暴力算法：
第一个MR：在MAP阶段穷举出100万个酒店的所有坐标（单位米），这样酒店数据会被冗余成
1000000*(999*4+1000+2) = 4,998,000,000 = 49亿条酒店数据
格式是 Key = X,Y  Value = 酒店/地标ID ，类型(酒店/地标)
把聚合出来KEY Count>1的数据放到HDFS --〉tmpfile
输出格式是 酒店ID 数量
第二个MR：读取tmpfile 根据酒店ID做一次聚合加法得到最终结果

这个算法最大的缺陷就是 酒店被穷举的太多，导致MAP至Reduce输出数据太庞大
所以我想了第二个办法，在第一个算法的基础上，实现降维

1、降维算法：
第一个MR：
1、根据每个酒店的坐标，找到4个新坐标（X/Y根据半径做+/-法），看蓝线
把蓝线旋转45度得到新的4个坐标，红线
把酒店和地标的X/Y除以半径（1000）得到Xa/Ya，落在8个点连接起来的灰线内的酒店坐标Xa/Ya就是我们要统计出来的数据

但这里有个问题，由8个点形成的8边型并不能覆盖整个圆内的所有地标数据

解决的办法，就是把酒店覆盖面看成一个正方形（不是圆），边的宽度=半斤*2
把这个正方形切成4个小正方形，每个正方形，代表某个酒店所能覆盖到的区域
这样就会出现4*4=16个坐标，除去重复坐标最后保留 9个，这样就能保证覆盖到所有该酒店能覆盖到的地标了。其中还包括一些半径外的地标，这里先不用管他，让reduce去处理。

这样每个酒店只需要冗余出8+1（别忘了圆心）条数据，这样Map酒店输出 = 1000000*9 = 9百万

格式是 Key = Xa,Ya  Value = 酒店/地标ID ，类型(酒店/地标) ，X，Y
reduce和之前一样但需要多做一步判断 就是 酒店和地标的距离是否在半径内
把聚合出来KEY Count>1的数据放到HDFS --〉tmpfile

第二个MR：跟第一个方法一样，读取tmpfile 根据酒店ID做一次聚合加法得到最终结果

我的初步想法是， 20亿条数据如果和200万条数据， 如果没做区域分的话，
差不多复杂度最少是 o(20 0000 0000 * 200 0000)
而且reduce 还只能有一个，这处理起来速度肯定慢
如果是我做的话，20亿条数据，
第一步 MR 抽样计算 按坐标 x, 或者y来分100或者1000份
得到一个相对来说比较平均100个x或者y坐标值
第二步 MR 拿这些点的坐标，将20亿条坐标和200W酒店坐标也分成对应的100份或者1000份
这里边还得考虑一个边界问题，考虑到极限值，有些酒店刚好坐标在我们分的点的X/Y值上
所以在坐标数据分区的时候，第一个块的实际区域是划分点往x 上再加一公里，同理第二个快的区域往下减一公里(在map 计算的时候， 往这两个区域各传递一个条数据)， 酒店区域直接按抽样点来分就可以, 输出key都为对应的抽样点x或者y值,  数据为坐标
第三步 MR 标记两个文件酒店的tag为0 坐标数据的tag为1组合抽样点作为key,  然后在reduce端作聚合操作, 酒店坐标先到，用容器保存，后来的坐标数据每个都计算与容器保存的酒店坐标计算距离， 满足的输出,
如果是1000份来分的话， 基本就是o(20 0000 0 * 200 0 * 1000)
第四步MR 合并

[1] [2] 下一页