背景
什麼是軌迹分析?
https://baike.baidu.com/item/%E6%97%B6%E7%A9%BA%E8%BD%A8%E8%BF%B9%E4%BC%B4%E9%9A%8F%E6%A8%A1%E5%BC%8F/13850333 https://postgis.net/docs/reference.html#Temporal https://help.aliyun.com/document_detail/95294.html1、時空軌迹的業務場景:
疫情防控:
- 根據病毒攜帶者的軌迹快速找到密切接觸者. 軌迹距離計算
-
- 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
postgres=> select st_astext('LINESTRING ZM (0 0 1 1432605600,10 0 1 1432609200)'::geometry);
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)
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 例子:
相比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.》![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)