C********g
发帖数: 1548 | 1 Suppose I have a social network application that allows a user to search
users nearby him. There are tens of thousands of users all cross America in
a relational database. How to do the search? Any programming language is
fine. |
g*****g
发帖数: 34805 | 2 precompute a zip map, for each zip code, get every zip code within 50 miles.
Query by zip code. If it needs to be more accurate, you can do something
similar using address->coordinates.
in
【在 C********g 的大作中提到】
: Suppose I have a social network application that allows a user to search
: users nearby him. There are tens of thousands of users all cross America in
: a relational database. How to do the search? Any programming language is
: fine.
|
n*********u
发帖数: 1030 | 3 most db has spatial index. (mongodb, Apache Lucene, pgsql, and even mysql's
spatial index extension). |
a9
发帖数: 21638 | 4 关键你有什么数据啊？zip code? gps? ip address?
in
【在 C********g 的大作中提到】
: Suppose I have a social network application that allows a user to search
: users nearby him. There are tens of thousands of users all cross America in
: a relational database. How to do the search? Any programming language is
: fine.
|
ET
发帖数: 10701 | 5 concur this
【在 a9 的大作中提到】
: 关键你有什么数据啊？zip code? gps? ip address?
:
: in
|
C********g
发帖数: 1548 | 6 addresses including street, city, state and zipcode.
I may end up with mysql Spatial Indexes.
【在 a9 的大作中提到】
: 关键你有什么数据啊？zip code? gps? ip address?
:
: in
|
z****e
发帖数: 54598 | 7 用google map api获取当前位置（lat，lon）
然后存到内存中去，找个内存数据库吧
mysql也行
然后计算出50miles对应的lat范围
同样计算出50miles对应的lon范围
然后汇总后再用google map api计算dis
最后reduce，不过我觉得没有必要算得这么精确
直接根据50^0.5计算lat范围，以及50^0.5计算lon范围
然后满足这两个条件的就算是附近的人
当然这样搜索出来的不是一个圆形，而是一个正方形
但是会快不少，因为省去了reduce操作 |
r*a
发帖数: 1503 | 8 如果你又他们的经纬度，那就很简单了，有数学公式一算就可以了。维基上又公式的。
Spherical-surface formulae in https://en.wikipedia.org/wiki/Geographical_
distance
如果你没有经纬度，那么你要通过GEOCODING服务，把他们的经纬度给算出来，然后再
计算距离。 |
a9
发帖数: 21638 | 9 如果地址是固定的，可以后台算出任意两个人的距离存在数据库里。
实时算的话就如赵策所说，先用正方形过一遍，再用圆形过滤。自己狗一下，有很成熟
的算法。
【在 C********g 的大作中提到】
: addresses including street, city, state and zipcode.
: I may end up with mysql Spatial Indexes.
|
d******e
发帖数: 2265 | 10 那里用的那么麻烦。直接上mongo里面的spatial feature.
或者要功能更强，上postgresql好了。
【在 z****e 的大作中提到】
: 用google map api获取当前位置（lat，lon）
: 然后存到内存中去，找个内存数据库吧
: mysql也行
: 然后计算出50miles对应的lat范围
: 同样计算出50miles对应的lon范围
: 然后汇总后再用google map api计算dis
: 最后reduce，不过我觉得没有必要算得这么精确
: 直接根据50^0.5计算lat范围，以及50^0.5计算lon范围
: 然后满足这两个条件的就算是附近的人
: 当然这样搜索出来的不是一个圆形，而是一个正方形
|
|
|
z****e
发帖数: 54598 | 11 spatial featue就是我说的方法，按照经度纬度做排列，然后建两个indexes
只不过我把api的实现给拆分了而已
也没啥难的，自己做也就是那么一回事
【在 d******e 的大作中提到】
: 那里用的那么麻烦。直接上mongo里面的spatial feature.
: 或者要功能更强，上postgresql好了。
|
d******e
发帖数: 2265 | 12 人家是geohash好吧。就一个字串查找搞定。比你那个强太多了。
【在 z****e 的大作中提到】
: spatial featue就是我说的方法，按照经度纬度做排列，然后建两个indexes
: 只不过我把api的实现给拆分了而已
: 也没啥难的，自己做也就是那么一回事
|
l*******m
发帖数: 1096 | 13 kd tree or ball tree, which provides O(ln(n)) search complexity
in
【在 C********g 的大作中提到】
: Suppose I have a social network application that allows a user to search
: users nearby him. There are tens of thousands of users all cross America in
: a relational database. How to do the search? Any programming language is
: fine.
|
z****e
发帖数: 54598 | 14 为什么还要字符串查找？
如果有字符串的话，直接丢给google map api，很快就能定位出来
还有一般这种查找都是需要获取本地地址的
社交软件大部分都是手机的app
用mobile api就可以获取经纬度，然后剩下的就是根据经纬度查找了
用字符串查找应该属于小众
经纬度两个都是单纯的数字，这种查找还能更简单一点吗？不知道难在哪里
【在 d******e 的大作中提到】
: 人家是geohash好吧。就一个字串查找搞定。比你那个强太多了。
|
d******e
发帖数: 2265 | 15 你要找poi活着user,肯定是在后端做了。
那么，最简单的scan，计算，就是你说的o(n).
这对uber这样的级别数据库是不可行的。
其次，rtree range query. postgre gis 支持。但是这个不可scalable.
在其次， kd tree, k维还是太复杂。
geohash将为一维,这个可以用btree index了。甚至可以做成hash+trie，纯内存结构。
update, query 都是常数到o(log(n)) + o(t)级别的操作。t在bounding box里面的用
户数目。
geohash本质就是经纬度变成01然后base 36编码。
【在 z****e 的大作中提到】
: 为什么还要字符串查找？
: 如果有字符串的话，直接丢给google map api，很快就能定位出来
: 还有一般这种查找都是需要获取本地地址的
: 社交软件大部分都是手机的app
: 用mobile api就可以获取经纬度，然后剩下的就是根据经纬度查找了
: 用字符串查找应该属于小众
: 经纬度两个都是单纯的数字，这种查找还能更简单一点吗？不知道难在哪里
|
z****e
发帖数: 54598 | 16 哪里要那么复杂
针对经度和纬度分别建两个index，查找效率是2*lg(n)复杂度，还可以并行
然后这种互相之间没有任何关联的数据
直接就可以分派出n个任务，然后汇总，reduce后交给客户
所以就解决了scale out的问题，随便分库，每个库自己做好index就可以
所以最后时间复杂度是lg(n)/m，m是分派出来的worker#
这是查找，然后update和insert，这个因为分库了
保证每一个库所伺候的nodes不会太多便可
update/insert的话我没看出有啥问题，做到线性scale没啥问题
index用tree结构比较好，保证update，insert和查找都是o(lg(n))的复杂度
一般mobile app上获取location/coordinates都有很多现成的api
拿到的一般是经度和纬度
最后就是一般社交数据，精度要求都不会太高，跟money transaction不能比
所以不做任何replica都没啥问题
说到底就是，经度和纬度之间没有任何必然联系，这种不做hash比较好
不做的话，直接并行两个threads，一个找经度，一个找纬度，最后汇总
然后找经度纬度这个可以做成o(lg(n))复杂度，就是直接二分下去，毕竟有了index
所以查找起来要快很多
如果做hash的话，也是扫一次，但是是o(n)复杂度，二分好像是不行
至少没有index那么直观
【在 d******e 的大作中提到】
: 你要找poi活着user,肯定是在后端做了。
: 那么，最简单的scan，计算，就是你说的o(n).
: 这对uber这样的级别数据库是不可行的。
: 其次，rtree range query. postgre gis 支持。但是这个不可scalable.
: 在其次， kd tree, k维还是太复杂。
: geohash将为一维,这个可以用btree index了。甚至可以做成hash+trie，纯内存结构。
: update, query 都是常数到o(log(n)) + o(t)级别的操作。t在bounding box里面的用
: 户数目。
: geohash本质就是经纬度变成01然后base 36编码。
|
z****e
发帖数: 54598 | 17 一般社交用户很少自己输入location
就像微信，你搜索附近的人，都是mobile自动定位location的
这种api给出的就是经度和纬度数据，而非某个字符串
这不make sense，然后经度找经度差在一定范围内的
纬度亦然，最后两者做一个reduce便可 |
a9
发帖数: 21638 | 18 要是没意义，一帮人还搞这个干嘛。
【在 z****e 的大作中提到】
: 哪里要那么复杂
: 针对经度和纬度分别建两个index，查找效率是2*lg(n)复杂度，还可以并行
: 然后这种互相之间没有任何关联的数据
: 直接就可以分派出n个任务，然后汇总，reduce后交给客户
: 所以就解决了scale out的问题，随便分库，每个库自己做好index就可以
: 所以最后时间复杂度是lg(n)/m，m是分派出来的worker#
: 这是查找，然后update和insert，这个因为分库了
: 保证每一个库所伺候的nodes不会太多便可
: update/insert的话我没看出有啥问题，做到线性scale没啥问题
: index用tree结构比较好，保证update，insert和查找都是o(lg(n))的复杂度
|
z****e
发帖数: 54598 | 19 不同的应用范畴，有些时候只能通过string来做查找
这个时候hashcode显得很顶用，但是纯粹数字，没事hash了干什么？
数字查找用hash？hashcode这个用法是体育老师教的？
hash的主要意义在于把string -> number，如果你拿到就已经是number了
你没事hash了做啥？number -> number?
【在 a9 的大作中提到】
: 要是没意义，一帮人还搞这个干嘛。
|
z****e
发帖数: 54598 | 20
你知道我在说什么吗？
我说的没有关联性就是第一是客户和客户数据之间无关联
你在哪里，跟我在哪里，没有关系
这一点决定了很容易scale out，分库可行
其次第二，经度和纬度可以通过直接画正方形来取逼近值
最后再通过画圆来筛选，所以在你画正方形的时候
不需要在乎经度和纬度之间的关系
这一点决定了parallel可行，可以在单个node上启双线程最后汇总后reduce
我最近正好就在思考这个问题
这里可能会涉及到一个meter 2 lat/lon的问题
这个我已经找到答案了
http://gis.stackexchange.com/questions/46729/corner-coordinates |
|
|
a9
发帖数: 21638 | 21 你能不能wiki一下看看这个hash工作的原理再说？
【在 z****e 的大作中提到】
: 不同的应用范畴，有些时候只能通过string来做查找
: 这个时候hashcode显得很顶用，但是纯粹数字，没事hash了干什么？
: 数字查找用hash？hashcode这个用法是体育老师教的？
: hash的主要意义在于把string -> number，如果你拿到就已经是number了
: 你没事hash了做啥？number -> number?
|
z****e
发帖数: 54598 | 22
我前面不是说了用tree建index吗？
或者干脆就用index就好了，估计这种index也都是tree结构
至于什么tree，无所谓，很容易实现lg(n)的复杂度
你难道不会把原文好好看看？
就在你装逼贴的上一贴 |
z****e
发帖数: 54598 | 23
哦，有趣了，我好像还真的懂这个hashcode是咋回事
要不你给说说，lat/lon这种42.37827837842378的给我hash看看
用哪个prime？
【在 a9 的大作中提到】
: 你能不能wiki一下看看这个hash工作的原理再说？
|
z****e
发帖数: 54598 | 24 这贴的解决方案你自己不都说了嘛
一个tree，一个index，不知道你还在辩啥
这是最简单的方案 |
z****e
发帖数: 54598 | 25
【在 a9 的大作中提到】
: 你能不能wiki一下看看这个hash工作的原理再说？
|
z****e
发帖数: 54598 | 26
把下面这段话好好看看，其次球面几何只有非常精确时候才需要
对于social data来说，这种精确度属于没事找事，做一个大概就可以了
所以一个rect足够用了，连保证50miles这个radius都不需要
这样可以节省其中一步，没有人在乎谁跟谁的距离是不是确切的50miles以内
这个问题最重要的是要解决，第一获取客户location
其次第二，转换miles -> lat/lon，这个比较难，方法参考我给出的link
最后第三，我们用过geohash什么狗屁，couchdb里面就有，叫couchspace还是啥的
结果都觉得很垃圾，全班没有一个人最后选择了这个东西，都是自己搞index
因为没啥难的，就那点东西
发信人: zhaoce (米高蜥蜴), 信区: Programming
标 题: Re: How to Search Users within 50 miles away from me
发信站: BBS 未名空间站 (Thu Jun 18 11:39:01 2015, 美东)
哪里要那么复杂
针对经度和纬度分别建两个index，查找效率是2*lg(n)复杂度，还可以并行
然后这种互相之间没有任何关联的数据
直接就可以分派出n个任务，然后汇总，reduce后交给客户
所以就解决了scale out的问题，随便分库，每个库自己做好index就可以
所以最后时间复杂度是lg(n)/m，m是分派出来的worker#
这是查找，然后update和insert，这个因为分库了
保证每一个库所伺候的nodes不会太多便可
update/insert的话我没看出有啥问题，做到线性scale没啥问题
index用tree结构比较好，保证update，insert和查找都是o(lg(n))的复杂度 |
z****e
发帖数: 54598 | 27 对于第二步，如果你用的是google map api的话
google api有现成的工具，就是能够转换点为具体的lat/lon
这个js,android,obj c都有类库，所以可以避开第二难点
我之所以找到那个link，是因为我用的是static map
所以js等api基本上用不上，所以不得不去计算pixel -> meter -> lat/lon
以及反过来的转换，我用java实现，如果其他人也有实现过
非常欢迎给我代码，因为我还没测试我的代码，也懒得写，有抄太好了
至于什么geoindex，那个玩意不是重点
用index就足够了，简单效率高，表没事找事，这个玩意我做过好几个项目了
包括手头上这一个 |
z****e
发帖数: 54598 | 28 说说我毕业时候做的这个东西
就是给一个google map
然后根据map上任意一个点，选择一个范围
然后获取social data
是不是跟你做得有点像？
只不过我找的是twits，你找的是user
从本质上说没啥大不了的，无非就是划定范围
然后查找嘛，我连二分tree都懒得用，直接就上index
也没多慢，挺快的，一个简单的reduce就搞定了
这里有优化空间，但是没啥太大意义，除非真的是人数多到这个程度
那我到时候花钱请wdong来做
基本上google api足够用，但是我后来遇到另外一个问题
就是我打算通过server获取google map的image
然后再把这个stream发送给app，那么这个时候
很多api都不管用了，因为我自建server，所以这个时候我得烦恼pixel -> meter ->
lat/lon的转换
麻痹的真难做啊，我给出那个link的python代码看得一知半解的
虽然抄是抄了，但是效果还没测试，所以如果有谁做过的，有现成的java代码的
欢迎给我哈，多谢，不过每次一到这种干货的时候，装逼的几个都尿遁了
习惯了，我已经不抱有任何期待了 |
z****e
发帖数: 54598 | 29 顺便说一下
语言的话
我当时用dart+js做的，主要是dart
服务器用vert.x，用java和groovy，主要是groovy |
z****e
发帖数: 54598 | 30 顺便说一下，我后来这个项目
之所以需要精确计算，是因为觉得google map的work api太贵
屌丝没办法，喜欢在技术上省钱
所以就想自己拼凑出自己需要的static map，只要images就好了
这个时候精确计算出边界很重要，如果边界错误，会导致整个地图tiles无法拼接出来
这都已经不是什么social data能比的了，这种精度如果我自己搞不定
那就先做简化版的，以后卖premium版的向客户收钱
我用static map主要是用在app里面，而且不太想让app访问google
因为怕被封锁，天朝尤其喜欢封锁这种东西，所以想在cloud上找个中介
然后发送image给app，就这么一个思路
然后meter -> lat/lon这个我找了n个贴，只有那个链接中的比较靠谱
其他都比较扯蛋，无非告诉我怎么用google api |
|
|
z****e
发帖数: 54598 | 31 而且回头看楼主的贴
人家已经说了有一个rational db
直接在db里面弄两个indexes表太简单
你弄其他spacial的plugin，麻烦死你
还都不知道有还是没有，index只要是db，丫就有
没有的话，弄死它
自建tree都显得多余，index简单直接
index建好之后，一个select的where clauses就差不多搞定了
是我直接上index排lat/lon的序
然后画正方形查找，如果对方鸡婆，非要圆形区域
那其实我也不用那么麻烦，就把所有数据显示在地图上
然后把这个圆形区域给画出来，是否在这个区域内，用户自己去选去
如果不在区域内，我也给你标示出来，用户爱选不选
这个思路你从twitter的public api就可以看出来，twitter就喜欢给你方块区域
尤其是streaming的api，现在不知道改了没有，但是我们当时用的时候
主要还是用方块，来获取tweets，twitter就偷懒了，就是按照lat/lon做切割
所以最重要的是如何转换楼主说的50miles -> lat/lon的范围
因为不同地理位置，经度应该还好，但是纬度改变会有差异
这个难题困扰了我一段时间鸟，但是接近有曙光了 |
w***g
发帖数: 5958 | 32 我觉得我上面回帖实在太mean了，向你道歉。那些存照贴都删了。
【在 z****e 的大作中提到】
: 而且回头看楼主的贴
: 人家已经说了有一个rational db
: 直接在db里面弄两个indexes表太简单
: 你弄其他spacial的plugin，麻烦死你
: 还都不知道有还是没有，index只要是db，丫就有
: 没有的话，弄死它
: 自建tree都显得多余，index简单直接
: index建好之后，一个select的where clauses就差不多搞定了
: 是我直接上index排lat/lon的序
: 然后画正方形查找，如果对方鸡婆，非要圆形区域
|
