入职后感觉很空虚

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1323|回复: 7
收起左侧

Geohashing VS. Space filling curve VS. Google S2

[复制链接] |试试Instant~ |关注本帖
我的人缘0
sterne 发表于 2017-8-4 07:18:45 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (13)
 
 
0% (0)  踩

2017(10-12月) 码农类General 硕士 全职@Uber - 内推 - Onsite  | Other | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
一个系统设计问题,在设计附近POI, Yelp寻找附近restaurant的时候,我们会用到Geohash, 用00, 01, 10, 11来把一个小的square细分成四块,这个貌似是一个Z curve? 最近看文档看到还有别的Space filling curve, 例如Peano curve, Hilbert curve. 请问Geohashing和各种Curve是什么关系? 根据Uber engineering blog, Uber使用的是Google S2,S2内部使用的是Hilbert curve. 那Google S2跟Geohashing又是什么关系?Google S2是open source的library(*.jar) or restful service?

. From 1point 3acres bbs

补充内容 (2017-8-4 07:57):
请教高手解答。

上一篇:脸家加面,似乎他家最近新题很多?
下一篇:口袋宝石店面壹
我的人缘0
facetothefate 发表于 2017-8-20 05:10:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (3)
 
 
25% (1)  踩
Geohash 原理就是把2维的坐标想办法换成一维,所以你需要一个变换,你这里00 01 10 11 的分发就是一种拉成1维的办法。如果每个格子都是按照这个来,你画个图就能发现每个四个格子之间都是自相似的曲线。所以这个拉成一维的问题就是个分形问题了。因此会有很多种分形曲线的做法。所以geohash就是在一个2维矩阵上生成分形图的过程。
回复

使用道具 举报

我的人缘0
facetothefate 发表于 2017-8-20 05:17:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (3)
 
 
25% (1)  踩
facetothefate 发表于 2017-8-20 05:10
Geohash 原理就是把2维的坐标想办法换成一维,所以你需要一个变换,你这里00 01 10 11 的分发就是一种拉成1 ...

然后评价一个分形曲线的效果就是说 地图上两个相近的点要在映射成分形曲线一维点以后也离得近,z curve因为有突变,所以有时候会出现两个二维点离的很近但是在曲线上离得很远的情况。这样你搜最近有什么的时候就出问题了,会丢结果。
回复

使用道具 举报

我的人缘0
zhanghaowx 发表于 2017-8-20 06:13:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩
听上去和Tile Scheme很像,看看这个http://www.maptiler.org/google-maps-coordinates-tile-bounds-projection/
回复

使用道具 举报

我的人缘0
f1371342385 发表于 2017-9-4 08:12:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (48)
 
 
12% (7)  踩
那这道题的话 用QuadTree是不是也可以呀
回复

使用道具 举报

我的人缘0
胖子Jeffwan 发表于 2017-9-22 02:25:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (24)
 
 
7% (2)  踩
f1371342385 发表于 2017-9-4 08:12.1point3acres网
那这道题的话 用QuadTree是不是也可以呀

我觉得可以的。只要说清楚都行
回复

使用道具 举报

我的人缘0
longfeix 发表于 2018-4-8 03:34:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
Google S2 是library, 是geohash一种。

大概意思就是吧整个三维地球映射到一个六面体,这样降为到2d。然后用hilbert curve再降为到一维。用hilbert curve的原因就是,2维空间相近的两点,在映射到1d后依然相近,这样就便于计算。
回复

使用道具 举报

我的人缘0
longfeix 发表于 2018-4-8 03:34:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
这题到底是在问什么?好像没看懂
Mobile Apps Category (English)728x90
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-7-19 06:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表