暴力法：欧式距离

原理：计算这个用户与其他用户的欧氏距离，然后进行排序

优点：实现简单

缺点：时间复杂度高，当用户量大时，即使使用类似于 MR 的分布式运算，也需要消耗大量资源。
$总时间复杂度=计算时间+排序时间=O(n) + O(n*logn)$

推荐：GeoHash

原理：将地图展开成一个平面，将平面切割成小格并为小格编号。将用户的位置转换成所处小格的编号。与当前用户同一个格子或附近格子的用户返回给当前用户。

GeoHash：为格子编号的一种编码方式： 『每次将范围折半，值处于前半部分，得 0；反之，得 1。』

// geohash的伪代码
public String getCode(double value, double min, double max, double codeLen){
  StringBuilder sb = new StringBuilder();
  
  // codeLen：对折次数，即code的长度
  for(int i=0; i<codeLen; i++){
    double mid = (max + min) / 2.0;
    if(value < min){  // 说明 值处于前半区
      sb.append('0');
    } else{   // 说明 值处于后半区
      sb.append('1');
    }
  }
  return sb.toString();
}

GeoHash计算方式的示例

GeoHash完整的转换

问题：如何快速查找 “附近的人”？

1）将 (user_id, user_geoCode) 存入数据库并在 user_geoCode 建索引
2）select * from locTable where user_geoCode = curUser_geoCode 返回附近的人（即同一格子的人）

更多问题（如下）见参考文献

编码设置为多少位比较合适？
同一格子内没有人，该如何处理？

“附近的人”的技术原理

“附近的人”的技术原理

暴力法：欧式距离

推荐：GeoHash

问题：如何快速查找 “附近的人”？