V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
TangMonk
V2EX  ›  问与答

像默默,微信的附近的人的功能是是怎么实现的。

  •  1
     
  •   TangMonk · 2014-07-06 17:13:57 +08:00 · 6963 次点击
    这是一个创建于 3777 天前的主题,其中的信息可能已经有所发展或是发生改变。
    数据表可能是这样的

    user_id | latitude | longtitude

    但是不可能遍历整个数据表吧。

    求大概的算法和实现方式
    12 条回复    2014-07-06 21:50:56 +08:00
    akfish
        1
    akfish  
       2014-07-06 17:20:06 +08:00   ❤️ 4
    当然不可能遍历,地理位置网格分块,存块ID,然后四叉搜索。

    你的经纬度换算成网格ID,同网格的人撸出来,临近网格的人撸出来,搞定。
    lsylsy2
        2
    lsylsy2  
       2014-07-06 17:20:27 +08:00   ❤️ 1
    灯塔算法
    fangzhzh
        3
    fangzhzh  
       2014-07-06 17:29:36 +08:00 via Android
    范围扩大一倍 人数指数级增长
    TangMonk
        4
    TangMonk  
    OP
       2014-07-06 17:33:34 +08:00
    @akfish 谢谢,请问怎么把地理位置分块,怎么把经纬度转化成网格 ID 呢。
    TangMonk
        5
    TangMonk  
    OP
       2014-07-06 17:33:55 +08:00
    貌似有个 geohash,研究下
    akfish
        6
    akfish  
       2014-07-06 18:00:11 +08:00
    @TangMonk 方法很多,本质上就是hash
    udonmai
        7
    udonmai  
       2014-07-06 18:37:11 +08:00
    KD Tree
    R Tree
    TangMonk
        8
    TangMonk  
    OP
       2014-07-06 19:55:46 +08:00
    貌似这个叫做Spatial Search,python,java(solr)都有实现

    http://django-haystack.readthedocs.org/en/latest/spatial.html

    https://wiki.apache.org/solr/SpatialSearch

    继续研究下。。
    TangMonk
        9
    TangMonk  
    OP
       2014-07-06 20:57:47 +08:00
    nice! mongodb 支持 spatial search, 童鞋们可以看下:

    http://docs.mongodb.org/manual/core/geospatial-indexes/
    won
        10
    won  
       2014-07-06 21:17:25 +08:00 via iPhone
    购买geo
    wanjun
        11
    wanjun  
       2014-07-06 21:18:01 +08:00
    就看你的用户量了,如果最多只有几亿的话,mysql就可以了,存储x,y坐标,加索引,
    然后mongodb自身实现了计算距离,排序。
    geohash并不好用,https://github.com/kungfoo/geohash-java
    leiz
        12
    leiz  
       2014-07-06 21:50:56 +08:00
    postgis
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3603 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 04:17 · PVG 12:17 · LAX 20:17 · JFK 23:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.