现有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 合并

This is an interested question. Here is my thoughts.

1) We only need one MR job.
2) 重点 is how to design a custom key class, which will sort the data as the way we want. Remember, in MapReduce job, almost every key will be compared with each other, to grouping/partition and sorted. This is the key feature provided from Hadoop, and we should utilize that.

The input of mapper will be (LongWritable, Text), as default TextInputFormat, but the output of the mapper will be <KeyClass, NullWriteable).

The most important is to design this custom KeyClass.

Here are some important information related this key class, I will use pseudo code:

Class Key {
     enum type
     altitude double
     latitude double
}

In this mapper, we have to have the custom SortComparator, GroupComparator  and PartitionComparator. Here are the trick parts of each:

1) For sort comparator:
     For same type, compare altitude and latitude.
     For different type, make sure all 酒店 is less than 地标, that will sort 酒店s first, then 地标.

2) For grouping and Partition comparator, this is very important part.
     a) Make sure each 酒店 will be different key, means they are different. So same 酒店 will go to same reducer.
     b) For 地标 data, if the compared object is another 地标, just compare their altitude and latitude, so different 地标 will omit as different, but if the compared object is 酒店, and if 2 pair of (altitude and latitude) are within 1公里, mark these 2 objects are the same. So this 地标 data will treat as same grouping as the 酒店 data, and both will be treat as the same key, and sent to the same reducer.

All this will just need one MR job, this interview question is really to check if you are design a custom key, and override the grouping and partition comparator (Make sure that if 地标 data is within 1公里 as 酒店 data, they will be grouped and partitioned together, so they will go to same reducer). So after mapper stage, you will have 100万 reducer group key, as you have 100万酒店 data, but all the 地标 data within 1公里 of the 酒店 will be treated as the same key of that 酒店, then being sent to the same reducer.

I hope I explain clearly in English, as typing Chinese is too slow for me.

import java.io.OutputStream;
import java.util.Random;
 
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
 
public class ctrip001_createdata {
    public static void main(String[] args) throws Exception {
        // 现有100万酒店坐标和20亿地标,里面记录地标的经纬度，请设计mapreduce计算所有酒店1公里范围内的地标。
        // 类型(酒店/地标) id(酒店id/地标id) 纬度 经度
        // 假设一个1600平方公里的小城市 = 40 公里 * 40 公里 = 40000 米* 40000米
        // 假设有1000个酒店，1000,000个地标
 
 

[1] [2] [3] [4] [5] [6] 下一页