The practice of spatial index in geographic service

I share my practice 《Application of spatial index in geographic service》. The contents are as follows:
- How to understand n-dimensional space and n-dimensional space-time
- Efficient multi-dimensional spatial point indexing algorithm — Geohash and Google S2
- How to generate CellID in Google S2?
- The algorithm of finding LCA recent public ancestor on the quadtree in Google S2
- The magical of Bruyne sequence
- How to find the neighbors of Hilbert curve on the quadtree?
- How does Google S2 solve the problem of optimal solution in spatial coverage?

Article is in there: https://github.com/halfrost/Halfrost-Field#-go

Transcript

1. 空间索引在地理服务中实践 W E L C O M E
2. ⾃我介绍 ID：⼀缕殇流化隐半边冰霜（花名：霜菜） 了解 iOS 开发、前端⼩⽩、后端新⼿ 略懂 JavaScript、Go、C、C++、Objective-C、Swift Github：@halfrost 微博：@halfrost
3. F O R E W O R D N E X T S L I D E
4. PRESENTATION AGENDA Geohash 01 03 Google S2 02 04 Application Space filling curve
5. #01 GEOHASH S P AT I A L I N D E X N E X T S L I D E
6. EXAMPLE B A S E - 3 2 B A S E - 3 6
7. EXAMPLE
8. 4 5 % 4 5 % 4 5 % 4 5 % 4 5 % 4 5 % GEOHASH (LEVEL-6) (31.1932993, 121.43960190000007) 纬 经
9. GEOHASH (LEVEL-6) 101011000101110 L AT I T U D E 纬 度 110101100101101 L O N G I T U D E 经 度 偶数位放经度，奇数位放纬度 (第 0 位为第⼀位) 111001100111100000110011110110
10. N E X T 11100 11001 11100 00011 00111 10110 28 25 28 3 7 22 wtw37q
11. EXAMPLE
12. CODE package geohash import ( "bytes" ) const ( BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz" MAX_LATITUDE float64 = 90 MIN_LATITUDE float64 = -90 MAX_LONGITUDE float64 = 180 MIN_LONGITUDE float64 = -180 ) var ( bits = []int{16, 8, 4, 2, 1} base32 = []byte(BASE32) ) type Box struct { MinLat, MaxLat float64 // 纬度 MinLng, MaxLng float64 // 经度 } func (this *Box) Width() float64 { return this.MaxLng - this.MinLng } func (this *Box) Height() float64 { return this.MaxLat - this.MinLat } // 输⼊值：纬度，经度，精度(geohash的⻓度) // 返回geohash, 以及该点所在的区域 func Encode(latitude, longitude float64, precision int) (string, *Box) { var geohash bytes.Buffer var minLat, maxLat float64 = MIN_LATITUDE, MAX_LATITUDE var minLng, maxLng float64 = MIN_LONGITUDE, MAX_LONGITUDE var mid float64 = 0 bit, ch, length, isEven := 0, 0, 0, true for length < precision { if isEven { if mid = (minLng + maxLng) / 2; mid < longitude { ch |= bits[bit] minLng = mid } else { maxLng = mid } } else { if mid = (minLat + maxLat) / 2; mid < latitude { ch |= bits[bit] minLat = mid } else { maxLat = mid } } isEven = !isEven if bit < 4 { bit++ } else { geohash.WriteByte(base32[ch]) length, bit, ch = length+1, 0, 0 } } b := &Box{ MinLat: minLat, MaxLat: maxLat, MinLng: minLng, MaxLng: maxLng, } return geohash.String(), b }
13. SCALE
14. ERROR
15. SHARDING RULE 根据经纬度计算 Shard ID 及 Cell ID 若上⼀次在同⼀个 Cell，直接更新 若上⼀次在不同 Cell，先删除上⼀ 个 Cell，再加⼊当前 Cell 的队列 中。 W R I T E ( U P D AT E L O C AT I O N ) 计算相交的 Shard 每个 Shard 做并⾏ Nearby 计算。 Geohash 只能先按照⼴度优先查 找相应的 Cell，过滤出 Cell 中符 合条件的点。 R E A D ( N E A R B Y S E A R C H )
16. WHY why？ 偶 数 位 放 经 度 ， 奇 数 位 放 纬 度 why？ 理 论 基 础 why？ 有 缺 点 么 ？
17. #02 SPACE FILLING CURVE S P AT I A L F I L L I N G C U R V E N E X T S L I D E
19. Z-ORDER
20. Z-ORDER
21. DISADVANTAGE
22. DISADVANTAGE
23. DISADVANTAGE Z 阶曲线可以将⼆维或者多 维空间⾥的所有点都转换成 ⼀维曲线。在数学上成为分 形维。 降 维 局 部 保 序 性 突 变 性 搜 索 查 找 邻 近 点 ⽐ 较 快
24. EXAMPLE
25. PEANO CURVE ⽪亚诺曲线是⼀条连续的但处处不可导的曲线。
26. DRAGON CURVE
27. GOSPER CURVE
28. KOCH CURVE
29. MOORE CURVE
30. SIERPIŃSKI CURVE
31. HILBERT CURVE
32. HILBERT CURVE
33. HAUSDORFF FRACTALS DIMENSION
34. HILBERT CURVE
35. HILBERT CURVE
36. HILBERT CURVE
37. HILBERT CURVE
38. HILBERT CURVE
39. HILBERT CURVE
40. HILBERT CURVE
41. HILBERT CURVE
42. HILBERT CURVE
43. CHARACTERISTIC 降 维 稳 定 连 续 希尔伯特曲线是连续的，所以能保证⼀定 可以填满空间。连续性是需要数学证明 的。具体证明⽅法这⾥就不细说了，感兴 趣的可以点⽂章末尾⼀篇关于希尔伯特曲 线的论⽂，那⾥有连续性的证明。
44. CONTINUITY
45. ANY QUESTIONS? T H A N K S F O R Y O U R AT T E N T I O N ! N E X T S L I D E
46. #03 GOOGLE S2 S P AT I A L I N D E X N E X T S L I D E
47. LAT / LNG x = r * sin θ * cos φ y = r * sin θ * sin φ z = r * cos θ
48. LAT / LNG s(lat,lng) -> f(x,y,z)
49. PROJECTION
50. PROJECTION
51. FRACTAL
52. FRACTAL
53. FRACTAL 3 0 % 4 5 % 5 0 % f(x,y,z) -> g(face,u,v)
54. FIXED g(face,u,v) -> h(face,s,t)
55. PROGRAM 线性变换 u = 0.5 * ( u + 1) tan() 三⻆变换 u = 2 / pi * (atan(u) + pi / 4) = 2 * atan(u) / pi + 0.5 ⼆次变换 u >= 0，u = 0.5 * sqrt(1 + 3*u) u < 0，u = 1 - 0.5 * sqrt(1 - 3*u) 1 2 3
56. TRANSFORM h(face,s,t) -> H(face,i,j)
57. HILBERT CURVE
58. HILBERT CURVE
59. HILBERT CURVE
60. HILBERT CURVE LEVEL H(face,i,j) -> CellID
61. CELL ID
62. N E X T S L I D E S(lat,lng) -> f(x,y,z) -> g(face,u,v) -> h(face,s,t) -> H(face,i,j) -> CellID GOOGLE S2
63. CLACULATE
64. GEOHASH VS GOOGLE S2 各种向量计算，⾯ 积计算，多边形覆 盖，距离问题，球 ⾯球体上的问题 ⼏ 何 计 算 S2 还能解决多 边形覆盖的问题 多 边 形 覆 盖 S2 有30级，从 0.7cm² 到 85,000,000km² 。S2 的存 储只需要⼀个 uint64 即可 存下 突 变 性 Geohash 有12级，从5000km 到 3.7cm。中间每⼀ 级的变化⽐较⼤。有时候可能选择上⼀级会⼤很 多，选择下⼀级⼜会⼩⼀些。⽐如选择字符串⻓度 为4，它对应的 cell 宽度是39.1km，需求可能是 50km，那么选择字符串⻓度为5，对应的 cell 宽度 就变成了156km，瞬间⼜⼤了3倍了。Geohash 需 要 12 bytes 存储 L E V E L 精 细 度
65. GOOGLE S2 1.涉及到⻆度，间隔，纬度经度点，单位⽮量等的表示，以及对这些 类型的各种操作。 2.单位球体上的⼏何形状，如球冠（“圆盘”），纬度 - 经度矩形，折 线和多边形。 3.⽀持点，折线和多边形的任意集合的强⼤的构造操作（例如联合） 和布尔谓词（例如，包含）。 4.对点，折线和多边形的集合进⾏快速的内存索引。 5.针对测量距离和查找附近物体的算法。 6.⽤于捕捉和简化⼏何的稳健算法（该算法具有精度和拓扑保证）。 7.⽤于测试⼏何对象之间关系的有效且精确的数学谓词的集合。 8.⽀持空间索引，包括将区域近似为离散“S2单元”的集合。此功能可 以轻松构建⼤型分布式空间索引。
66. #04 APPLICATION F I N A L N E X T S L I D E
67. APPLICATION
68. APPLICATION
69. APPLICATION
70. APPLICATION
71. APPLICATION
72. APPLICATION
73. APPLICATION
74. APPLICATION 流量是每秒钟⼤概数万条消息，⼀天⼤概是⼏亿，并且每条消息包含⼏⼗个字段 1.⽀持时序和地理空间的切⽚ 2.⽀持⼤流量数据 3.⽀持秒级(毫秒级？)查询 4.⽀持原始数据查询 ElasticSearch + Kafka
75. ONE MORE THING https://github.com/halfrost/Halfrost-Field
76. THANKS B Y E B Y E