JUST技術：基於軌跡的新冠易感人群查詢方案

COVID-19席捲全球，對全球生命衛生安全構成了極大挑戰。截至2020年11月5日，COVID-19 全球累計確診4826萬人，累計死亡122萬人。在沒有疫苗情況下，早發現、早報告、早隔離、早治療是控制疫情的最有效方案。

在疫情防控最關鍵的前幾個月，京東城市幫北京市找到 500 餘名高危的密切接觸者，為宿遷市找到全市範圍四分之一比例的新冠肺炎確診人員；在全國範圍內，幫廣州、南京、成都等 18 個省市做了高危人群態勢分析。其中，JUST團隊做出了重要貢獻。我們提出了一種新穎的軌跡感染風險度量和高效的查詢方案，這項工作已發布在論文《EfficientSuspected Infected Crowds Detection Based on Spatio-Temporal Trajectories》[1]。

一、問題背景

致命病毒在人與人之間的傳播一直是全球公共衛生面臨的重要問題。從19世紀前半葉開始，由霍亂狐菌引發的霍亂奪取了無數人的生命，僅僅印度，在霍亂爆發之後的100年間，由其造成的死亡人數高達3800萬人。在歐洲，僅在1831年間死亡人數高達90萬人。2002年底，「非典」疫情爆發，其病死率近11％。從2019年底開始至今，一種新冠病毒（SARA-Cov-2）造成的疾病COVID-19席捲全球，對全球生命衛生安全構成了極大挑戰。截至2020年11月5日，COVID-19 全球累計確診4826萬人，累計死亡122萬人。

在沒有疫苗情況下，早發現、早報告、早隔離、早治療是控制疫情的最有效方案。中國政府根據四早方案，果斷採取封城、方艙隔離等措施，很快控制住了COVID-19的傳播，保障了人民的安全。

因為COVID-19具有極高的傳染性，它可以通過唾液等傳播，並且幾乎人人易感。因此，早發現病毒攜帶者並及時將其隔離，就能阻止他傳播給其他人，進而有效地防止疫情大規模傳播。

傳統尋找病毒攜帶者主要通過以下兩種方案：1）人工詢問患者曾經去過的地方和接觸的人群，然後讓相關社區工作人員去核實和隔離密切接觸者；2）通過患者的出行記錄，如火車票，飛機票等，找到與患者同乘的人。但以上這兩種做法十分依賴於患者的記憶，並且很難找全與患者有過一段近距離共處的陌生人。

隨著移動網際網路的高速發展，每時每刻都會產生大量的時空數據。這些時空數據記錄著人的活動軌跡。因此，如果我們掌握了COVID-19患者在被隔離前的活動軌跡，那麼我們就可以很清楚地知道他去過的地方，再通過時空範圍查詢就能找到跟患者有過近距離接觸的人群。如圖1所示，給定患者移動軌跡（如圖1中紅色軌跡），易感人群挖掘找出與這條軌跡有過密切接觸的人群（如圖1中藍色人群）。

圖1：易感人群示意圖

現存軌跡度量，如DTW、EDR、Hausdorff等算法能計算軌跡的全局相似度[3]。但是，只要與患者在很小的時空範圍內近距離接觸就可能被感染，因此這些度量不適用於易感人群判斷。此外，COVID-19潛伏期很長，甚至超過了14天，並且它在潛伏期也有傳染性。然而，一座城市14天產生的軌跡數據量可能會十分龐大。因此，計算全城中所有與患者接觸的人群需要巨大的計算量。

為此，我們提出了一種新穎的軌跡度量，它將軌跡分成若干傳播子段，再計算各個子段與患者密切接觸程度，最後我們將疑似人與患者所有傳播子段的接觸概率綜合起來評價他被感染的概率。此外，我們利用JUST引擎管理防疫期間的海量軌跡，並設計了一種空間優化索引SFT，其將相近時空範圍內的軌跡段聚集在一起，極大地加快了查詢效率。

二、基本框架

為了處理大量患者傳播的易感人群，我們開發了一個快速查詢的解決方案。如圖2所示，我們系統的主要結構由三個部分組成：數據預處理，候選者提取和感染性探索。

圖2：算法框架

數據預處理：如圖2中最上面的方框所示，我們首先將軌跡的噪聲位置過濾掉。之後，我們將軌跡分段。然後，我們使用XZ2T索引來組織軌跡段，再通過JUST[2]將它們存儲到NoSQL資料庫中。

候選者提取：候選者提取過程使用分段算法、SFT索引策略和時空查詢接口。分段的目的是避免軌跡太長而帶來的較大的內存和I/O開銷。我們在所有待查詢軌跡段上建立了SFT索引，其中具有類似時空範圍的段被放置在SFT索引同一葉節點中。然後，我們通過擴展SFT每個葉節點的時空範圍，再從資料庫中提取候選片段。最後，我們從資料庫中獲得了粗粒度的候選對象，並且數據冗餘度低且I / O消耗較小。

感染性探索:圖2的最底部的框顯示了感染性探索的過程。首先，我們修剪一些不可能是密切接觸的候選人；然後，我們計算剩餘疑似人群在患者可傳播段的感染概率，再聚合屬於同一軌跡的局部軌跡段的所有傳染性，並計算出其軌跡的總體傳染性。最後，我們過濾傳染性低於感染閾值的軌跡。

三、數據預處理

由於用戶軌跡數量巨大，造成傳統資料庫難以實現快速查詢。因此，我們通過分布式資料庫（如HBase），將海量軌跡數據用key-value的形式存儲在具有多備份且安全的分布式集群上。然而，傳統分布式並不直接支持軌跡數據，為此需要為軌跡數據設計特殊的行鍵結構，才能取得更佳查詢效率。我們設計的XZ2T索引，能高效的管理類似軌跡這種多維時空數據。XZ2T索引按照固定時間跨度（如，年，月，日）將時間劃分為若干不相交的區間，並通過XZ2索引將二維空間範圍映射到一維整數域中，如圖3所示，然後再組合時間分區號和空間編碼值為存儲鍵，再將其鍵和數據存儲在分布式資料庫中以備易感人群挖掘查詢離線使用。

圖3：表設計

四、候選者提取

1、分段

首先，我們患者的軌跡分成若干個可傳播片段，這些片段可以準確的表示患者曾經在那些地方活動過。然後，我們通過查詢每個軌跡片段可能感染的時空範圍，找到候選易感人群。我們從兩個時間或者空間間隔超過一定值的軌跡點中間切斷軌跡，形成軌跡段。如圖4中，最大時間間隔為30分鐘，最大空間間隔為50m。

圖4：軌跡分段

2、SFT索引

在實際的使用場景中，患者的數據會批量增加，如果採用循環查詢將花費大量的時間。為此，我們設計了空間優先時空索引SFT，其將相近時空範圍內的軌跡段聚集在一起並一同查詢疑似人群。這樣的設計極大地減少了I/O開銷和數據冗餘。如圖5所示，在SFT索引中，我們首先通過四叉樹將軌跡段聚類在不同節點上，然後再在每一個葉子節點中建立一維R索引管理時間範圍。

圖5：SFT空間優先索引

3、ST Query

如圖6所示，我們患者軌跡（藍色軌跡）分成兩條子段s1, s2，每條軌跡段會形成一個活動的空間（如圖6中紅色實線表示的矩形範圍）和時間（如圖6中q1.t和q3.t之間的時間範圍）範圍，我們將空間範圍和時間範圍擴張θd, θt得到受影響時空範圍。最後，我們從資料庫中提取出所有出現在患者影響時空範圍內的人群，並根據用戶ID聚合屬於同一人的軌跡，進而得到疑似人群。並通過下面的具體實現第五節中描述的感染風險度量方案確定疑似人群的風險值。

圖6：疑似人群查詢

五、感染風險

COVID-19患者會感染跟他有過密切接觸的人。因此，被感染風險的影響因素與患者和正常人接觸的時空距離遠近有很重要的關係。所以，患者軌跡中的每一個軌跡點都能形成一個傳播的時空範圍。

1、時空關係度量

我們將軌跡點定義為l = (p, t)，其中p表示位置，t表示時刻。給定一個軌跡點位置l, 一個空間影響範圍θd和一個時間影響範圍θt.我們用STR（l, θd, θt.）來表示時空影響範圍。如下：

其中dist表示空間距離，在位置l影響的時空範圍STR（l, θd, θt.）內，我們通過公式（1）計算人群與該時空位置上的密切接觸程度：

(1)

其中，st_dist(l, v)表示兩個時空位置之間的距離。如公式（2）所示:

(2)

其中，λ屬於[0, 1]區間，它用來控制空間和時間的偏好，和將空間距離和時間間隔歸一化到[0,1]範圍內。注意，如果一條軌跡與STR（l,θd, θt.）不相交，那麼它在l處的時空接觸可能為0。

2、軌跡感染風險

（1）局部軌跡段的感染風險

為了更精準的描述患者傳播路徑，需要將患者從潛伏期開始到被隔離期間的所有軌跡集中起來。但，由於GPS終端有些信號不穩定或者用戶關閉了終端等原因，造成了患者在這段時間的軌跡並不一定是一直連續的。並且，患者所有時空點組成的一條軌跡具有較大的時空範圍，這樣會在時空查詢時產生大量的冗餘數據。因此，我們需要將軌跡分段，將長軌跡分割成較為合適的軌跡局部段。如圖四所示，我們從兩個時間或者空間間隔超過一定距離的軌跡點中間切斷軌跡，形成軌跡段。

給定病毒攜帶者的局部軌跡段（s）和疑似感染人員的軌跡（T），我們通過公式（3）衡量疑似人員在攜帶者的局部軌跡段被感染的風險。公式（3）如下：

(3)

其中，l是軌跡段s中的一個時空位置，|s|代表s的時空位置數量。

（2）軌跡感染風險

一個病毒攜帶者的完整軌跡由多個局部軌跡段組成。因此，僅僅通過局部軌跡段的感染風險並不能完全反應疑似人員被感染風險。如，某個疑似人員雖然跟患者在各個軌跡局部段接觸並不多，但是他多次出現在患者不同的局部軌跡段中，那麼他也被感染的風險應該更大。因此，簡單的做法通過將疑似人員在攜帶者各個局部段的被感染風險值相加作為最終感染風險。但是，如果病毒攜帶者在某一個軌跡局部段停留時間越長，那麼他在該位置傳播病毒的可能越大。因此，如公式（4），我們需要考慮給攜帶者的局部軌跡段加上權重來標記它可能的傳播強度。如公式（5）中，我們用時間的相對佔比來標記可能的強度。

(4)

(5)

3、剪枝策略

易感人群算法需要計算患者每個時空點與附近疑似人群的感染概率，因此需要大量的計算量。所有，我們提供了四種剪枝策略來減少計算量。剪枝策略的詳細描述見[1]。

(6)

(7)

(8)

(9)

六、案例

圖7：易感人群系統

我們基於本算法開發了易感人群查詢系統。如圖7所示，我們將手機等設備和應用產生的時空軌跡數據存儲在JUST平臺中，並利用JUST提供的軌跡預處理功能完成原始軌跡去噪和分段操作。然後我們將軌跡存儲在JUST提供的軌跡表中。再將第五節設計的易感人群算法封裝為DAL操作，讓用戶可以通過一條簡單的SQL語句就能很快地完成易感人群查詢。最後，對外輸出易感人群名單支持上層應用。

該系統已經支持了北京、武漢、廣州、南京、成都等多個省市。在疫情最關鍵的前幾個月，我們幫北京市找到 500 餘名高危的密切接觸者；為宿遷市找到全市範圍四分之一比例的新冠肺炎確診人員；並協助其它團隊完成高危人群態勢分析。

參考文獻：

[1] He, Huajun & Li, Ruiyuan &Wang, Rubin & Bao, Jie & Zheng, Yu & Li, Tianrui. (2020). EfficientSuspected Infected Crowds Detection Based on Spatio-Temporal Trajectories.

[2] http://just.urban-computing.com/

[3] https://mp.weixin.qq.com/s/95DJin1jHNntg1X9sp6R8Q