“附近的人”的技术原理

摘自 怎么快速找到:附近的人 - 知乎
仅供个人使用

问题描述:如何实现 “附近的人” 功能?

暴力法:欧式距离

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

优点:实现简单

缺点:时间复杂度高,当用户量大时,即使使用类似于 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 返回附近的人(即同一格子的人)

更多问题(如下)见参考文献

  • 编码设置为多少位比较合适?
  • 同一格子内没有人,该如何处理?
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。