背景
什么是轨迹分析?
https://postgis.net/docs/reference.html#Temporal
https://help.aliyun.com/document_detail/95294.html
1、时空轨迹的业务场景:
疫情防控:
- 根据病毒携带者的轨迹快速找到密切接触者. 轨迹距离计算
- 1度、2度、N度接触者
公安刑侦:
- 同行人分析: 轨迹相似度
- 密切接触分析: 轨迹距离
预测:
- 根据轨迹数据建模, 预测群体事件、时空数据热点分布等, 用于智慧城市管理、智慧交通等.
- 与商业结合, 时空轨迹+用户画像.
2、业务挑战:
数据量大, 数据与业务割裂, 计算纯靠coding实现, 开发效率低下, 运行效率良莠不齐.
3、对时序数据库系统的诉求:
写入吞吐要求高, 延迟低, 查询要求响应快, 压缩比要求高(节省存储成本), 算法的扩展能力要求强.
4、PG解决方案:
- 轨迹类型:
- geometry
- 轨迹分析函数:
- 最近距离计算
- 相似度计算
- 相遇时间计算
- 相遇可能性判断
- 轨迹有效性判断
- 压缩能力
- sharding 能力(citus, timescaledb, ymatrix, POLARDB 等)
ST_IsValidTrajectory — Returns true if the geometry is a valid trajectory.
ST_ClosestPointOfApproach — Returns the measure at which points interpolated along two trajectories are closest.
ST_DistanceCPA — Returns the distance between the closest point of approach of two trajectories.
ST_CPAWithin — Returns true if the closest point of approach of two trajectories is within the specified distance.
节点内并行(PG parallel scan, since PG 9.6)
多节点并行(fdw async append, since PG 14)
5、阿里云PG Ganos 支持更加丰富的轨迹计算:
- 轨迹压缩
- 空间关系判断
- 空间处理
- 空间统计
- 时空关系判断
- 时空处理
- 时空统计
- 距离测量
- 相似度分析
PG开源版本例子
1、创建时空插件
create extension postgis;
2、构造轨迹例子
select st_astext(ST_AddMeasure('LINESTRING Z (0 0 1, 10 0 1)'::geometry,
extract(epoch from '2015-05-26 10:00'::timestamptz),
extract(epoch from '2015-05-26 11:00'::timestamptz)
));
st_astext
----------------------------------------------------
LINESTRING ZM (0 0 1 1432605600,10 0 1 1432609200)
(1 row)
postgres=> select 'LINESTRING ZM (0 0 1 1432605600,10 0 1 1432609200)'::geometry;
geometry
----------------------------------------------------------------------------------------------------------------------------------------------------
01020000C00200000000000000000000000000000000000000000000000000F03F000000E8F458D54100000000000024400000000000000000000000000000F03F0000006CF858D541
(1 row)
postgres=> select st_astext('LINESTRING ZM (0 0 1 1432605600,10 0 1 1432609200)'::geometry);
st_astext
----------------------------------------------------
LINESTRING ZM (0 0 1 1432605600,10 0 1 1432609200)
(1 row)
3、创建构建随机轨迹的函数
create or replace function gen_traj(
x int, -- x坐标
y int, -- y坐标
z int, -- z坐标
ts timestamptz, -- 轨迹开始时间
n int -- 轨迹由多少个点组成
) returns geometry as $$
declare
s text := '';
begin
select string_agg(
format('%s %s %s %s',
round(x+(random()*10*xx)::numeric,2),
round(y+(random()*10*xx)::numeric,2),
round(z+(random()*10*xx)::numeric,2),
round( (extract(epoch from ts+(5*xx||' second')::interval)::numeric ),2)
), ',')
into s
from generate_series(1,n) xx;
return st_astext((format('LINESTRING ZM (%s)', s))::geometry);
end;
$$ language plpgsql strict;
postgres=> select st_astext(gen_traj(1,1,1,now(),3)); st_astext
----------------------------------------------------------------------------------------------------------
LINESTRING ZM (7.54 1.48 3.6 1622622896.13,10.7 19.39 1.27 1622622901.13,18.36 1.32 21.07 1622622906.13)
(1 row)
4、创建测试表和随机轨迹
create table tbl (
uid int,
tr geometry,
ts timestamp
);
insert into tbl select
random()*100000000,
gen_traj((random()*100)::int,(random()*100)::int,(random()*100)::int,now(),10+(random()*20)::int),
clock_timestamp() from generate_series(1,10000);
postgres=> select uid,st_astext(tr),ts from tbl limit 4;
uid | st_astext | ts
----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------
87154252 | LINESTRING ZM (84.3 106.87 26.33 1622624311.12,95.98 105.98 36.33 1622624316.12,87.55 124.92 23.79 1622624321.12,114.8 112.13 23.11 1622624326.12,80.08 146.61 58.37 1622624331.12,103.81 124.19 47.08 1622624336.12,82.57 99.07 51.36 1622624341.12,84.22 110.42 36.83 1622624346.12,150.16 129.81 37.73 1622624351.12,90.29 193.69 33.82 1622624356.12,109.23 129.11 82.05 1622624361.12,91.59 142.15 59.14 1622624366.12,148.37 122.26 83.74 1622624371.12,188.92 228.99 104.44 1622624376.12,155.4 208.43 157.83 1622624381.12,135.78 209.92 141.47 1622624386.12,200.09 251.99 142.22 1622624391.12,152.53 187.91 37.76 1622624396.12,164.07 169.84 182.82 1622624401.12,196.46 235.24 186.23 1622624406.12,93.29 226.16 198.91 1622624411.12,115.67 113.34 119.06 1622624416.12,120.75 212.01 230.62 1622624421.12,158.83 248.54 108.83 1622624426.12,109.7 230.41 51.79 1622624431.12,253.15 157.96 125.62 1622624436.12,219.21 114.95 171.93 1622624441.12,237.65 308.1 36.65 1622624446.12,225.06 205.71 229.1 1622624451.12) | 2021-06-02 16:58:26.119226
88746992 | LINESTRING ZM (93.41 29.11 37.48 1622624311.12,93.69 37.41 41.68 1622624316.12,111.11 36.28 58.96 1622624321.12,108.89 25.64 66.77 1622624326.12,137.92 38.5 48.32 1622624331.12,139.58 80.31 86.86 1622624336.12,127.01 74.04 84.13 1622624341.12,143.12 95.53 73.53 1622624346.12,163.16 24.36 79.29 1622624351.12,167.36 69.3 78.77 1622624356.12,188.43 91.88 50.37 1622624361.12,116.55 138.69 79.59 1622624366.12,174.13 64.99 114 1622624371.12,172.57 27.94 89.31 1622624376.12,136.19 136.54 111.18 1622624381.12,120.69 150.36 160.34 1622624386.12,200.27 62.56 65.32 1622624391.12,266.46 53.64 190.56 1622624396.12,244.57 119.41 195.44 1622624401.12,278.96 38.09 190.81 1622624406.12,93.3 197.69 123.86 1622624411.12,241.38 233.35 157.09 1622624416.12,255.77 190.09 133.93 1622624421.12,190.35 49.35 124.47 1622624426.12,141.54 116.37 65.89 1622624431.12,164.17 107.92 199.23 1622624436.12,334.91 258.2 37.07 1622624441.12,169.62 103.11 164.43 1622624446.12) | 2021-06-02 16:58:26.119741
65960978 | LINESTRING ZM (86.69 96.08 50.5 1622624311.12,95.42 96.69 56.84 1622624316.12,106.99 107.17 45.21 1622624321.12,113.78 105.49 67.92 1622624326.12,94.11 102.31 50.15 1622624331.12,120.62 135.32 53.96 1622624336.12,84.1 133.23 75.2 1622624341.12,119.55 167.03 55.87 1622624346.12,136.78 152.61 44.17 1622624351.12,99.79 140.98 92.78 1622624356.12,98.74 125.04 71.93 1622624361.12,113.22 98.16 162.16 1622624366.12,103.82 165.26 76.41 1622624371.12,151.18 116.19 152.82 1622624376.12) | 2021-06-02 16:58:26.11999
53468478 | LINESTRING ZM (8.98 70.37 91.44 1622624311.12,2.97 76.69 105.05 1622624316.12,18.02 86.47 116.15 1622624321.12,30.62 71.76 123.3 1622624326.12,37.91 64.33 111.2 1622624331.12,1.92 61.3 134 1622624336.12,36.01 64.1 95.64 1622624341.12,3.29 71.32 134.82 1622624346.12,65.26 119.27 121.93 1622624351.12,94.19 149.69 129.23 1622624356.12,35.36 120.08 106.27 1622624361.12,116.33 112.25 105.43 1622624366.12,53.84 128.84 186.2 1622624371.12,35.61 112.67 134.48 1622624376.12,45.04 144.55 161.33 1622624381.12,132.3 111.8 231.47 1622624386.12,25.77 197.72 223.77 1622624391.12,169.64 226.08 230.44 1622624396.12,146.69 208.8 118.28 1622624401.12,151.34 247.07 90.2 1622624406.12,166.49 166.12 216.25 1622624411.12) | 2021-06-02 16:58:26.120299
(4 rows)
应用: 轨迹相遇查询
explain
select uid,ts,
st_astext(tr) as tr,
ST_DistanceCPA(tr, 'LINESTRING ZM (84.3 106.87 26.33 1622624311.12,95.98 105.98 36.33 1622624316.12,87.55 124.92 23.79 1622624321.12,114.8 112.13 23.11 1622624326.12,80.08 146.61 58.37 1622624331.12,103.81 124.19 47.08 1622624336.12,82.57 99.07 51.36 1622624341.12,84.22 110.42 36.83 1622624346.12,150.16 129.81 37.73 1622624351.12,90.29 193.69 33.82 1622624356.12,109.23 129.11 82.05 1622624361.12,91.59 142.15 59.14 1622624366.12,148.37 122.26 83.74 1622624371.12,188.92 228.99 104.44 1622624376.12,155.4 208.43 157.83 1622624381.12,135.78 209.92 141.47 1622624386.12,200.09 251.99 142.22 1622624391.12,152.53 187.91 37.76 1622624396.12,164.07 169.84 182.82 1622624401.12,196.46 235.24 186.23 1622624406.12,93.29 226.16 198.91 1622624411.12,115.67 113.34 119.06 1622624416.12,120.75 212.01 230.62 1622624421.12,158.83 248.54 108.83 1622624426.12,109.7 230.41 51.79 1622624431.12,253.15 157.96 125.62 1622624436.12,219.21 114.95 171.93 1622624441.12,237.65 308.1 36.65 1622624446.12,225.06 205.71 229.1 1622624451.12)'::geometry), -- 两个轨迹的最近距离
ST_ClosestPointOfApproach(tr, 'LINESTRING ZM (84.3 106.87 26.33 1622624311.12,95.98 105.98 36.33 1622624316.12,87.55 124.92 23.79 1622624321.12,114.8 112.13 23.11 1622624326.12,80.08 146.61 58.37 1622624331.12,103.81 124.19 47.08 1622624336.12,82.57 99.07 51.36 1622624341.12,84.22 110.42 36.83 1622624346.12,150.16 129.81 37.73 1622624351.12,90.29 193.69 33.82 1622624356.12,109.23 129.11 82.05 1622624361.12,91.59 142.15 59.14 1622624366.12,148.37 122.26 83.74 1622624371.12,188.92 228.99 104.44 1622624376.12,155.4 208.43 157.83 1622624381.12,135.78 209.92 141.47 1622624386.12,200.09 251.99 142.22 1622624391.12,152.53 187.91 37.76 1622624396.12,164.07 169.84 182.82 1622624401.12,196.46 235.24 186.23 1622624406.12,93.29 226.16 198.91 1622624411.12,115.67 113.34 119.06 1622624416.12,120.75 212.01 230.62 1622624421.12,158.83 248.54 108.83 1622624426.12,109.7 230.41 51.79 1622624431.12,253.15 157.96 125.62 1622624436.12,219.21 114.95 171.93 1622624441.12,237.65 308.1 36.65 1622624446.12,225.06 205.71 229.1 1622624451.12)'::geometry), -- 两个轨迹相遇(最近距离)的时间点
st_astext(ST_Force3DZ(ST_GeometryN(ST_LocateAlong(tr,
ST_ClosestPointOfApproach(tr, 'LINESTRING ZM (84.3 106.87 26.33 1622624311.12,95.98 105.98 36.33 1622624316.12,87.55 124.92 23.79 1622624321.12,114.8 112.13 23.11 1622624326.12,80.08 146.61 58.37 1622624331.12,103.81 124.19 47.08 1622624336.12,82.57 99.07 51.36 1622624341.12,84.22 110.42 36.83 1622624346.12,150.16 129.81 37.73 1622624351.12,90.29 193.69 33.82 1622624356.12,109.23 129.11 82.05 1622624361.12,91.59 142.15 59.14 1622624366.12,148.37 122.26 83.74 1622624371.12,188.92 228.99 104.44 1622624376.12,155.4 208.43 157.83 1622624381.12,135.78 209.92 141.47 1622624386.12,200.09 251.99 142.22 1622624391.12,152.53 187.91 37.76 1622624396.12,164.07 169.84 182.82 1622624401.12,196.46 235.24 186.23 1622624406.12,93.29 226.16 198.91 1622624411.12,115.67 113.34 119.06 1622624416.12,120.75 212.01 230.62 1622624421.12,158.83 248.54 108.83 1622624426.12,109.7 230.41 51.79 1622624431.12,253.15 157.96 125.62 1622624436.12,219.21 114.95 171.93 1622624441.12,237.65 308.1 36.65 1622624446.12,225.06 205.71 229.1 1622624451.12)'::geometry) ),1))) pa -- 两个轨迹相遇(最近距离)的坐标
from tbl where
ST_CPAWithin(tr,
'LINESTRING ZM (84.3 106.87 26.33 1622624311.12,95.98 105.98 36.33 1622624316.12,87.55 124.92 23.79 1622624321.12,114.8 112.13 23.11 1622624326.12,80.08 146.61 58.37 1622624331.12,103.81 124.19 47.08 1622624336.12,82.57 99.07 51.36 1622624341.12,84.22 110.42 36.83 1622624346.12,150.16 129.81 37.73 1622624351.12,90.29 193.69 33.82 1622624356.12,109.23 129.11 82.05 1622624361.12,91.59 142.15 59.14 1622624366.12,148.37 122.26 83.74 1622624371.12,188.92 228.99 104.44 1622624376.12,155.4 208.43 157.83 1622624381.12,135.78 209.92 141.47 1622624386.12,200.09 251.99 142.22 1622624391.12,152.53 187.91 37.76 1622624396.12,164.07 169.84 182.82 1622624401.12,196.46 235.24 186.23 1622624406.12,93.29 226.16 198.91 1622624411.12,115.67 113.34 119.06 1622624416.12,120.75 212.01 230.62 1622624421.12,158.83 248.54 108.83 1622624426.12,109.7 230.41 51.79 1622624431.12,253.15 157.96 125.62 1622624436.12,219.21 114.95 171.93 1622624441.12,237.65 308.1 36.65 1622624446.12,225.06 205.71 229.1 1622624451.12)'::geometry
, 2); -- 最近距离在2以内的轨迹
uid | 11991427
ts | 2021-06-02 16:58:27.174658
tr | LINESTRING ZM (65.69 18.47 16.64 1622624311.12,74.18 23.92 18.66 1622624316.12,62.83 44.51 24.13 1622624321.12,71.66 38.27 27.75 1622624326.12,79.88 58.1 57.83 1622624331.12,105.01 25.52 29.8 1622624336.12,74.58 84.03 43.39 1622624341.12,97.76 62.02 56.5 1622624346.12,80.8 78.54 74.25 1622624351.12,72.56 95.7 96.95 1622624356.12,78.3 99.45 62.16 1622624361.12,87.92 70.53 90 1622624366.12,125.35 57.58 129.41 1622624371.12,151.19 101.95 85.66 1622624376.12,68.34 126.72 132.65 1622624381.12,200.19 76.83 73.14 1622624386.12,181.19 181.93 89.55 1622624391.12,159.21 185.92 139.25 1622624396.12,179.48 111.12 78.82 1622624401.12,152.01 108.25 72.82 1622624406.12,165.11 197.52 132.46 1622624411.12,112.8 124.15 122.76 1622624416.12,131.68 110.19 188.82 1622624421.12,209 226.92 208.84 1622624426.12,128.25 184 78.75 1622624431.12,183.18 31.74 124.51 1622624436.12,231.91 194.95 83.5 1622624441.12)
st_distancecpa | 1.68167315343679
st_closestpointofapproach | 1622624416.59687
pa | POINT Z (114.600669448853 122.81857280159 129.060435582161)
-[ RECORD 16 ]------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
uid | 99115424
ts | 2021-06-02 16:58:27.178605
tr | LINESTRING ZM (24.81 49.03 33.63 1622624311.12,31.99 63.52 41.68 1622624316.12,44.76 73.72 44.55 1622624321.12,25.64 62.34 42.09 1622624326.12,51.06 75.84 52.39 1622624331.12,56.11 85.5 54.09 1622624336.12,31.6 109.74 79.32 1622624341.12,93.78 107.9 30.5 1622624346.12,86.58 83.57 112.16 1622624351.12,107.76 106 43.98 1622624356.12,64.22 49.75 87.05 1622624361.12,105.26 79.46 32.54 1622624366.12,67.54 146.99 135.45 1622624371.12,152.19 70.56 118.24 1622624376.12,139.48 150.48 75.86 1622624381.12,66.24 87.42 159.77 1622624386.12,95.21 52.25 159.17 1622624391.12,94.69 163.69 197.75 1622624396.12,136.4 238.92 161.38 1622624401.12,51.31 186.37 36.78 1622624406.12,107.1 121.82 176.82 1622624411.12,27.86 143.56 163.13 1622624416.12,119.61 189.91 63.17 1622624421.12,201.12 254.62 264.96 1622624426.12,127.52 110.11 232.87 1622624431.12,141.75 160.5 69.15 1622624436.12,117.3 277.74 252.73 1622624441.12,296.52 225.21 78.62 1622624446.12,296.22 249.6 32.5 1622624451.12,58.06 200.22 53.66 1622624456.12)
st_distancecpa | 0.86718689843767
st_closestpointofapproach | 1622624345.2933
pa | POINT Z (83.499126531601 108.204226554871 38.5719241352081)
阿里云Ganos 例子:
https://help.aliyun.com/document_detail/95294.html
相比PostGIS的增强: 支持轨迹类型, 支持轨迹类型索引, 支持更多的轨迹计算算子
create extension ganos_trajectory ;
create table tbl1 (
uid int8,
tr trajectory, -- 轨迹类型
ts timestamp
);
create index idx_tbl1_1 on tbl1 using trajgist -- 基于轨迹类型的索引
(tr trajgist_ops_2dt);
建立索引后，可以加速各类算子以及ST_ndIntersect、ST_ndDWithin、ST_ndContains、ST_ndWithin函数的查询。
参考
- 压缩算法可扩展
- 存储引擎可扩展
- 索引架构可扩展
- 计算算法可扩展
202104/20210428_03.md 《PostgreSQL 时序数据库设计最佳实践- 关联citus,columnar,partition,timescaledb,压缩,高速写,parallel append 多分区并行查询,分区》
202103/20210320_01.md 《PostgreSQL 14 preview - TOAST 支持lz4 压缩算法- --with-lz4 , 新增GUC default_toast_compression》
202003/20200324_10.md 《PostgreSQL appendonly 压缩存储引擎- pg_cryogen》
201801/20180107_01.md 《SQL流式案例- 旋转门压缩(前后计算相关滑窗处理例子)》
201608/20160813_01.md 《旋转门数据压缩算法在PostgreSQL中的实现- 流式压缩在物联网、监控、传感器等场景的应用》
201908/20190816_01.md 《如何扩展、新增PostgreSQL索引接口- index access method》
201905/20190531_03.md 《PostgreSQL 基于access method api的列存zedstore》
202105/20210518_02.md 《结合PostgreSQL, MADlib, Tensorflow 实现机器学习是时序分析. 使用本地数据, 不需要move data.》
