基于時空耦合的時空網(wǎng)格快速伴隨研究

黃曉雄,賴 偉,史 超

(廣州匯智通信技術(shù)有限公司,廣東 廣州 510630)

0 引 言

隨著移動通信、智能手機(jī)和衛(wèi)星導(dǎo)航定位技術(shù)的發(fā)展，人們在使用這些技術(shù)及產(chǎn)品的過程中產(chǎn)生了大量的位置數(shù)據(jù)，包括全球定位系統(tǒng)(Global Positioning System，GPS)定位數(shù)據(jù)、移動終端設(shè)備和通信基站之間的通信數(shù)據(jù)以及人們在購物旅游過程中的位置等數(shù)據(jù)，這些位置數(shù)據(jù)和時間與數(shù)據(jù)實(shí)體結(jié)合就形成了實(shí)體對象的時空軌跡數(shù)據(jù)。在大數(shù)據(jù)廣泛應(yīng)用的今天，時空軌跡數(shù)據(jù)具有非常高的應(yīng)用價值，通過對時空軌跡數(shù)據(jù)的研究可以挖掘人們的出行習(xí)慣以便于制定交通規(guī)劃方案和市場營銷方案，分析人群聚集地和聚集時間以便于制定應(yīng)急方案，挖掘多個實(shí)體對象的伴隨關(guān)系，以便于進(jìn)行同伙犯罪分析從而維護(hù)社會安全等。

通過時空軌跡數(shù)據(jù)進(jìn)行伴隨關(guān)系挖掘分析是近年來的一個研究熱點(diǎn)，大數(shù)據(jù)技術(shù)的發(fā)展使得時空數(shù)據(jù)的搜集、存儲和分析變得更為簡單，但同時也帶來了問題，例如在海量的時空數(shù)據(jù)中快速而準(zhǔn)確的挖掘出具有伴隨關(guān)系的兩個實(shí)體對象。

時空軌跡伴隨分析是通過計算兩條軌跡的相似度來比較兩條軌跡的實(shí)體對象是否具有伴隨關(guān)系，常見的軌跡相似度計算方法包括歐式距離[1]、動態(tài)時間規(guī)劃(Dynamic Time Warping，DTW)[2]、最長公共子序列(Longest Common Subsequence，LCSS)[3]、編輯距離(Edit Distance on Real Sequences，EDR)[4]、弗雷歇距離[5]和豪斯多夫距離[6]等。在動態(tài)時間規(guī)劃方面，文獻(xiàn)[7]出了一種基于DTW改進(jìn)的軌跡相似度算法。在最長公共子序列LCSS研究方面，文獻(xiàn)[8]使用改進(jìn)LCSS進(jìn)行移動用戶軌跡相似性查詢算法研究，文獻(xiàn)[9]進(jìn)行了基于LCSS的非同步相似軌跡判斷研究，文獻(xiàn)[10]提出了一種LCSS+算法解決時空軌跡相似度計算中軌跡點(diǎn)比較的時間閾值敏感問題。在基于編輯距離EDR進(jìn)行軌跡相似研究方面，文獻(xiàn)[11]改進(jìn)了實(shí)數(shù)代價編輯距離算法，更好地應(yīng)用于移動軌跡。在弗雷歇距離研究方面，文獻(xiàn)[12]將其應(yīng)用于地圖匹配算法研究中，在基于豪斯多夫距離進(jìn)行軌跡相似性研究方面，文獻(xiàn)[13]提出一種基于單位時間平均值的Hausdorff距離的時空軌跡相似性度量方法。除了基于軌跡點(diǎn)距離計算軌跡相似性之外，文獻(xiàn)[14]提出了一種基于面積劃分的軌跡相似性度量方法很好地提升了軌跡點(diǎn)分布不均勻的軌跡相似度計算準(zhǔn)確率，文獻(xiàn)[15]進(jìn)行了基于時空鄰域的多粒度軌跡相似性查詢研究。

上述這些距離都是通過計算軌跡數(shù)據(jù)中相對應(yīng)的軌跡點(diǎn)的距離來計算兩條軌跡的相似度，但是在實(shí)際數(shù)據(jù)中，由于受各種環(huán)境因素包括天氣、地形和建筑物的影響以及終端設(shè)備的移動速度等影響，通過基站得到的實(shí)體對象的軌跡數(shù)據(jù)存在漂移、誤差甚至錯誤，特別是終端設(shè)備和通信基站之間通信時產(chǎn)生的位置數(shù)據(jù)不是終端設(shè)備的實(shí)際位置，因此這些伴隨分析算法并不適合于使用基站位置數(shù)據(jù)的場景。文獻(xiàn)[16]提出了一種基于網(wǎng)格索引的時空軌跡伴隨模式挖掘算法，該算法將需要挖掘的區(qū)域劃分為多個小的矩形網(wǎng)格，并引入“8-近鄰”網(wǎng)格的概念，通過計算兩個實(shí)體對象經(jīng)過的共同網(wǎng)格或“8-近鄰”網(wǎng)格的數(shù)量來衡量是否具有伴隨關(guān)系。但該算法具有兩個問題，1)使用的網(wǎng)格為自定義網(wǎng)格，不具有通用性，在大數(shù)據(jù)分析場景中，如果數(shù)據(jù)預(yù)處理時采用多種網(wǎng)格，在數(shù)據(jù)查詢時無法進(jìn)行高效的查詢；2)每個網(wǎng)格內(nèi)或多或少都存在與目標(biāo)實(shí)體對象不具有伴隨關(guān)系的其他實(shí)體對象，這些實(shí)體對象如果不進(jìn)行有效的排除，不僅對伴隨結(jié)果造成干擾，也會增加后續(xù)的計算量。針對上述兩個問題，提出了基于時空網(wǎng)格的快速伴隨相似度算法(Spatial-temporal Grid Accompany Similarity, SGAS)，采用基于希爾伯特曲線的Google S2空間索引算法[17]，生成通用的S2網(wǎng)格，通用的網(wǎng)格相比自定義網(wǎng)格具有以下三個優(yōu)點(diǎn)。

1)自定義網(wǎng)格需要保存經(jīng)緯度和網(wǎng)格的映射關(guān)系，在空間范圍比較大的情況下，映射關(guān)系的加載與查詢需要占用較多的資源，而通用網(wǎng)格可直接通過經(jīng)緯度進(jìn)行計算，無需保存映射關(guān)系；

2)自定義網(wǎng)格沒有網(wǎng)格級別之分，不同大小的網(wǎng)格之間無法進(jìn)行轉(zhuǎn)換，而通用網(wǎng)格有多個級別，不同級別的網(wǎng)格可以直接轉(zhuǎn)換；

3)在大數(shù)據(jù)場景中，存在較多的跨系統(tǒng)調(diào)用情況，通用網(wǎng)格更利用系統(tǒng)對接部署。

將網(wǎng)格與時間組合形成時空空格，在借鑒網(wǎng)格“8-近鄰”概念的基礎(chǔ)上，計算兩條軌跡具有相同或相鄰時空網(wǎng)格的數(shù)量；并在此基礎(chǔ)上，深入分析伴隨關(guān)系特征，提出了時空耦合伴隨模式，即在主對象運(yùn)動軌跡中的每一個軌跡采樣點(diǎn)的位置和時刻，時空耦合具有以下兩個特征。

1)當(dāng)主對象的位置已經(jīng)發(fā)生變化時，相同時刻仍在主對象的上一個或多個位置點(diǎn)的其他實(shí)體對象和主對象不具有伴隨關(guān)系；

2)當(dāng)主對象的位置還未發(fā)生變化時，相同時刻已經(jīng)在主對象下一個或多個位置點(diǎn)的其他實(shí)體對象和主對象不具有伴隨關(guān)系。

基于時空耦合的時空網(wǎng)格快速伴隨分析，可以大幅減少主對象伴隨結(jié)果中的干擾項，適用于大數(shù)據(jù)場景下的伴隨關(guān)系挖掘分析，能夠有效屏蔽實(shí)體對象軌跡數(shù)據(jù)的誤差、偏差甚至錯誤以及多個實(shí)體對象的軌跡數(shù)據(jù)采樣時間不同步問題，其運(yùn)行效率和準(zhǔn)確性也有較大提高，實(shí)測結(jié)果表明，在億級時空數(shù)據(jù)場景下，對一個主對象任意24 h內(nèi)的運(yùn)動軌跡進(jìn)行伴隨分析，能夠在十秒內(nèi)返回結(jié)果，且相比于不使用時空耦合的快速伴隨，能平均減少伴隨結(jié)果集的對象數(shù)量69%，顯著提高目標(biāo)對象在伴隨結(jié)果集中的排名，減少數(shù)據(jù)分析過程中的干擾項。

1 軌跡數(shù)據(jù)降維

時空軌跡數(shù)據(jù)包括時間和經(jīng)緯度數(shù)據(jù)，是由一系列時間和位置組成的軌跡點(diǎn)序列，理論上時間和對象的移動軌跡都是連續(xù)的，但是受限于數(shù)據(jù)源的采樣條件，在實(shí)際中這些軌跡點(diǎn)都是離散的，因此一條時空軌跡Tr通?？梢员硎緸?/p>

Tr={(t1,x1,y1),(t2,x2,y2),……,(ti,xi,yi)}

(1)

式中:軌跡點(diǎn)(ti,xi,yi)表示移動對象在任意ti時刻，都具有一個由經(jīng)緯度表示的位置(xi,yi)。

傳統(tǒng)的時空數(shù)據(jù)存儲通常將實(shí)體對象ID、時間和經(jīng)緯度數(shù)據(jù)分開存儲，以實(shí)體對象ID作為索引進(jìn)行時空數(shù)據(jù)的存儲和查詢。但是在時空搜索、時空碰撞和時空伴隨等大數(shù)據(jù)應(yīng)用場景中，需要在短時間內(nèi)(一般10 s以內(nèi))查詢一段時間范圍內(nèi)在某個區(qū)域出現(xiàn)的實(shí)體對象，如果對時間、經(jīng)度和緯度分別進(jìn)行查詢后再做過濾，查詢效率將受到嚴(yán)重影響。因此，需要針對大數(shù)據(jù)場景下的時空數(shù)據(jù)存儲及索引進(jìn)行優(yōu)化。

在軌跡數(shù)據(jù)中，采樣軌跡點(diǎn)具有離散性和隨機(jī)性，為了便于存儲與檢索，我們提出了時空網(wǎng)格索引，將時間、經(jīng)度和緯度這三個維度的數(shù)據(jù)利用時間片和空間網(wǎng)格索引算法進(jìn)行降維處理，將三個維度的數(shù)據(jù)降低為一個維度的時空網(wǎng)格數(shù)據(jù)，具體算法流程如下：

1)將時間分為十分鐘分片，時間戳t映射為小于等于t的最接近的十分鐘時間戳t′為

t′=f(t)=?t/600」×600

(2)

式中：?t/600」表示對t/600的結(jié)果向下取整。

若將時間分為五分鐘分片，則最接近的五分鐘時間戳t′為

t′=f(t)=?t/300」×300

(3)

2)將t′格式化為時間字符串，得到十分鐘粒度的時間片；

3)將經(jīng)緯度(x,y)使用Google S2空間索引算法轉(zhuǎn)換為S2網(wǎng)格，本文采用的是14級S2網(wǎng)格，其網(wǎng)格大小約0.32 km2；

4)將十分鐘粒度的時間片作為時空網(wǎng)格的時間域，S2網(wǎng)格作為時空網(wǎng)格的網(wǎng)格域，共同組成了時空網(wǎng)格，其格式為：時間域_網(wǎng)格域。時間域的格式為：yyyyMMddHHmm，網(wǎng)格域的格式為S2網(wǎng)格。

將時間、經(jīng)度和緯度三個維度的數(shù)據(jù)降低為一個維度的時空網(wǎng)格數(shù)據(jù)，并以時空網(wǎng)格數(shù)據(jù)做索引，可以方便地對軌跡數(shù)據(jù)進(jìn)行索引、存儲和壓縮。使用時空網(wǎng)格索引算法將軌跡中的某一點(diǎn)(ti,xi,yi)轉(zhuǎn)換為一維的時空網(wǎng)格得到TiGi，然后以TiGi作為key，移動對象ID作為value，組成Key-Value對存儲于Key-Value數(shù)據(jù)庫中的索引表中；將移動對象ID作為key，(ti,xi,yi)作為value，組成Key-Value對存儲于Key-Value數(shù)據(jù)庫中的數(shù)據(jù)表中，即可實(shí)現(xiàn)對任意時間和任意區(qū)域出現(xiàn)的移動對象及其軌跡進(jìn)行搜索的功能。

2 時空網(wǎng)格伴隨相似度算法

伴隨是指兩個或兩個以上的移動對象在一段限定的時間內(nèi)一起移動的過程，移動對象包括人、車或其他運(yùn)動對象，在這個過程中，以某個移動對象作為主對象，與主對象一起移動的其他對象作為關(guān)聯(lián)對象，則關(guān)聯(lián)對象在任意時刻一定位于主對象的地理位置的周圍。例如同乘一輛車的多個乘客、一起步行的多個伙伴等。

定義1：至少N個相關(guān)聯(lián)的移動對象，在一起運(yùn)動至少T時長，其中N和T是用戶自定義的閾值，且N>1，T≥30 min，則這N個移動對象在T時間內(nèi)形成的軌跡模式就叫做時空軌跡的伴隨模式。

基于時空網(wǎng)格的伴隨相似度算法指將所有移動對象的時空軌跡數(shù)據(jù)轉(zhuǎn)換為時空網(wǎng)格后，根據(jù)主移動對象的時空軌跡轉(zhuǎn)換后的時空網(wǎng)格，檢索數(shù)據(jù)庫中在相同或相鄰的時空網(wǎng)格中出現(xiàn)的其他關(guān)聯(lián)移動對象，并統(tǒng)計每個關(guān)聯(lián)移動對象出現(xiàn)的次數(shù)，再將每個移動對象出現(xiàn)的次數(shù)除以主移動對象的時空網(wǎng)格數(shù)就得到了基于時空網(wǎng)格的伴隨相似度。

定義2：主移動對象A在T1到Ti時間范圍內(nèi)，其對應(yīng)的時空網(wǎng)格序列為

TrA={T1G1,T2G2,……,TiGi}

(4)

式中：時空網(wǎng)格TiGi中的Ti代表時間域，Gi代表網(wǎng)格域。對于任意一個時空網(wǎng)格TiGi，它的“8-鄰域”計算規(guī)則為

1)把時空網(wǎng)格TiGi分隔為時間域Ti和網(wǎng)格域Gi；

2)計算出網(wǎng)格域Gi的八鄰域；

3)保持時間域Ti不變，將時間域和網(wǎng)格域Gi的八個鄰域網(wǎng)格組成八個時空網(wǎng)格，得到時空“8-鄰域”，如圖1所示。

圖1 時空8-鄰域

時空網(wǎng)格集合(TiGi1,TiGi2,TiGi3,TiGi4,TiGi5,TiGi6,TiGi7,TiGi8)為時空網(wǎng)格TiGi的時空八鄰域。

按照上述“8-鄰域”計算規(guī)則，將主移動對象A的時空網(wǎng)格序列進(jìn)行“8-鄰域”擴(kuò)域后得到新的時空網(wǎng)格序列為

NTrA={(NT1G11,NT1G12,NT1G13,NT1G14,T1G1,

NT1G15,NT1G16,NT1G17,NT1G18),

(NT2G21,NT2G22,NT2G23,NT2G24,T2G2,NT2G25,

NT2G26,NT2G27,NT2G28),

……,

(NTiGi1,NTiGi2,NTiGi3,NTiGi4,TiGi,NTiGi5,

NTiGi6,NTiGi7,NTiGi8)}

(5)

SGAS算法的規(guī)則為

1)將主移動對象A的時空網(wǎng)格序列TrA進(jìn)行“8-鄰域”擴(kuò)域后得到新的時空網(wǎng)格序列NTrA；

2)對于NTrA中的每一個時空網(wǎng)格集合

(NTi1Gi1,NTi2Gi2,NTi3Gi3,NTi4Gi4,TiGi,NTi5Gi5,NTi6Gi6,NTi7Gi7,NTi8Gi8)中的每個元素(即一個時空網(wǎng)格)，在數(shù)據(jù)庫中檢索其對應(yīng)的移動對象ID，同一個時空網(wǎng)格集合中出現(xiàn)的移動對象ID僅計算一次；

3)分別統(tǒng)計NTrA的所有時空網(wǎng)格中每個移動對象ID的出現(xiàn)次數(shù)

4)主移動對象A和關(guān)聯(lián)移動對象B的時空網(wǎng)格相似度SGAS定義為

(6)

其中，

式中：‖TrA‖表示時空網(wǎng)格序列TrA的元素個數(shù)。

3 時空耦合模式

基于時空網(wǎng)格的時空伴隨算法，是通過計算每個時空八鄰域網(wǎng)格中出現(xiàn)的移動對象ID，然后統(tǒng)計在所有的時空八鄰域網(wǎng)格中出現(xiàn)的移動對象ID的次數(shù)。在這個過程中，若某個移動對象出現(xiàn)的次數(shù)較少，或者僅在某些時空網(wǎng)格中存在，仍然會被統(tǒng)計到，為了減少伴隨結(jié)果中雜質(zhì)的干擾，提高伴隨結(jié)果的命中率，需要對伴隨的過濾邏輯進(jìn)行優(yōu)化。

根據(jù)定義1中伴隨模式的特征，具有伴隨關(guān)系的多個移動對象，其位置隨時間的變化規(guī)則相同；反之，若移動對象的位置隨時間的變化和主移動對象的不同，則該移動對象和主移動對象不具有伴隨關(guān)系。

因此時空耦合伴隨是指多個移動對象在時間和空間上同時發(fā)生關(guān)聯(lián)變化的模式，如圖2所示。

圖2 對象移動軌跡

假設(shè)采樣時刻為T1和T2，主移動對象A由T1G1運(yùn)動到T2G2，T1≠T2且G1≠G2，在T1時刻，對象A位于時空網(wǎng)格G1，時空網(wǎng)格T1G1的時空八鄰域中出現(xiàn)的移動對象可能和對象A具有伴隨關(guān)系，但是在T2時刻，仍然在網(wǎng)格G1中的，即在時空網(wǎng)格T2G1的時空八鄰域中出現(xiàn)的移動對象和對象A則不具有伴隨關(guān)系，因此在使用時空網(wǎng)格檢索數(shù)據(jù)庫時，需要加入排除條件，根據(jù)定義2的規(guī)則，時空網(wǎng)格T1G1的時空八鄰域?yàn)?/p>

(NT1G11,NT1G12,NT1G13,NT1G14,T1G1,

NT1G15,NT1G16,NT1G17,NT1G18)

排除條件為

(NT2G11,NT2G12,NT2G13,NT2G14,T2G1,

NT2G15,NT2G16,NT2G17,NT2G18)

將兩者通過NOT關(guān)系連接后即得到時空網(wǎng)格T1G1的檢索條件為

(NT1G11,NT1G12,NT1G13,NT1G14,T1G1,

NT1G15,NT1G16,NT1G17,NT1G18)

NOT

(NT2G11,NT2G12,NT2G13,NT2G14,T2G1,

NT2G15,NT2G16,NT2G17,NT2G18)

同理，當(dāng)對象A在T2時刻運(yùn)動至網(wǎng)格G2時，時空網(wǎng)格T2G2的時空八鄰域?yàn)?/p>

(NT2G21,NT2G22,NT2G23,NT2G24,T2G2,

NT2G25,NT2G26,NT2G27,NT2G28)

排除條件為

(NT1G21,NT1G22,NT1G23,NT1G24,T1G2,

NT1G25,NT1G26,NT1G27,NT1G28)

將兩者通過NOT關(guān)系連接后即得到時空網(wǎng)格T2G2的檢索條件為

(NT2G21,NT2G22,NT2G23,NT2G24,T2G2,

NT2G25,NT2G26,NT2G27,NT2G28)

NOT

(NT1G21,NT1G22,NT1G23,NT1G24,T1G2,

NT1G25,NT1G26,NT1G27,NT1G28)

需要注意的是，此處對于T1G1這個時空網(wǎng)格僅添加了一個排除的時空網(wǎng)格集合，在實(shí)際計算中，若主對象的軌跡中有多個時空網(wǎng)格不等于T1G1，則可以根據(jù)每一個時空網(wǎng)格添加一個排除的時空網(wǎng)格集合，排除時空網(wǎng)格集合的數(shù)量僅受限于底層數(shù)據(jù)庫所能支持的并發(fā)查詢能力。

是否符合排除條件，需要同時考慮時間域和空間域，即時間域和空間域均不相等，由于時間的單調(diào)遞增特性，按照本文前述的時間戳切片規(guī)則，不會存在相同的時間域，因此只需要考慮空間域是否相等即可。由于本文采用“8-鄰域”作為空間域，因此，判斷空間域是否相等只需要對標(biāo)識空間域的網(wǎng)格集合判斷是否相等，而兩個網(wǎng)格集合的比較分為三種情況。

1)當(dāng)兩個網(wǎng)格集合完全不重合時，如圖3所示，由于時間域已不相等，因此時空網(wǎng)格T1G1的排除條件是時間域T2和網(wǎng)格G1的“8-鄰域”組成的時空網(wǎng)格集合，時空網(wǎng)格T2G2的排除條件是時間域T1和網(wǎng)格G2的“8-鄰域”組成的時空網(wǎng)格集合。

圖3 兩個網(wǎng)格集合完全不重合

時空網(wǎng)格T1G1的排除條件是時間域T2和網(wǎng)格G1的“8-鄰域”組成的時空網(wǎng)格集合，也可以描述為時間域T2和網(wǎng)格G1的“8-鄰域”中除了網(wǎng)格G1的“8-鄰域”和網(wǎng)格G2的“8-鄰域”的交集之外的網(wǎng)格，可表示為：

時空網(wǎng)格T1G1的排除條件=T2·(CG1-CG1∩G2)

(7)

式中：CG1表示網(wǎng)格G1和它的“8—鄰域”網(wǎng)格集合；CG1∩G2表示網(wǎng)格G1和它的“8-鄰域”網(wǎng)格集合與網(wǎng)格G2和它的“8-鄰域”網(wǎng)格集合的交集。

由于兩個網(wǎng)格集合完全不重合，網(wǎng)格G1和它的“8-鄰域”與網(wǎng)格G2和它的“8-鄰域”的交集為空，因此網(wǎng)格G1的“8-鄰域”網(wǎng)格集合減去空集后仍然保持不變。時空網(wǎng)格T2G2的排除條件同理。

2)當(dāng)兩個網(wǎng)格集合部分重合時，如圖4所示，時空網(wǎng)格T1G1的排除條件是時間域T2和網(wǎng)格G1的“8-鄰域”中除了陰影部分的網(wǎng)格組成的時空網(wǎng)格集合，而時空網(wǎng)格T2G2的排除條件是時間域T1與網(wǎng)格G2的“8-鄰域”中除了陰影部分的網(wǎng)格組成的時空網(wǎng)格集合。

圖4 兩個網(wǎng)格集合部分重合

根據(jù)式(7)計算時空網(wǎng)格T1G1的排除條件，網(wǎng)格G1的“8-鄰域”需要減去網(wǎng)格G1和它的“8-鄰域”與網(wǎng)格G2和它的“8-鄰域”的交集，由于兩個網(wǎng)格集合部分重合，式(7)中的CG1∩G2即為圖4中的陰影部分，因此排除條件中網(wǎng)格G1的“8-鄰域”網(wǎng)格不包括陰影部分的網(wǎng)格。如果未對陰影部分的網(wǎng)格進(jìn)行特殊處理，直接將陰影部分的網(wǎng)格添加到排除條件中，若目標(biāo)恰好位于陰影部分的網(wǎng)格中，則會降低目標(biāo)的伴隨次數(shù)，進(jìn)而影響到目標(biāo)對象在伴隨結(jié)果中的排名。時空網(wǎng)格T2G2的排除條件同理。

3)當(dāng)兩個網(wǎng)格集合完全重合時，根據(jù)式(7)計算時空網(wǎng)格T1G1的排除條件，網(wǎng)格G1的“8-鄰域”需要減去網(wǎng)格G1和它的“8-鄰域”與網(wǎng)格G2和它的“8-鄰域”的交集，由于兩個網(wǎng)格集合完全重合，它們的交集仍然等于其中一個網(wǎng)格集合，即式(7)中的CG1=CG1∩G2，則CG1-CG1∩G2=?，即兩個網(wǎng)格集合完全重合時，需要排除的網(wǎng)格集合為空集，也就是說不需要添加排除網(wǎng)格集合。

綜上所述，時空網(wǎng)格T1G1排除條件中時空網(wǎng)格集合的計算可以歸納如下：

1)取出時空網(wǎng)格T1G1的網(wǎng)格域G1，計算“8-鄰域”，得到網(wǎng)格和鄰域集合CG1；

2)取出時空網(wǎng)格T2G2的網(wǎng)格域G2，計算“8-鄰域”，得到網(wǎng)格和鄰域集合CG2；

3)計算CG1和CG2的交集CG1∩G2；

4)計算排除網(wǎng)格集合為CG1-CG1∩G2；

5)與時間域T2結(jié)合得到排除的時空網(wǎng)格集合。

4 實(shí)驗(yàn)結(jié)果

本文時空網(wǎng)格數(shù)據(jù)存儲在時空庫集群系統(tǒng)中，該數(shù)據(jù)庫基于分布式數(shù)據(jù)庫HBase，利用HBase的協(xié)處理器框架實(shí)現(xiàn)移動對象ID和時空網(wǎng)格數(shù)據(jù)的相互索引，并結(jié)合高效的Bitmap位運(yùn)算機(jī)制實(shí)現(xiàn)時空網(wǎng)格的AND、OR和NOT連接關(guān)系計算，協(xié)處理器與Bitmap相互結(jié)合可以支撐億級時空數(shù)據(jù)查詢秒級響應(yīng)。在時空庫集群中，單個時空網(wǎng)格的查詢可達(dá)到毫秒級，再利用協(xié)處理器的并發(fā)特性，多個時空網(wǎng)格的查詢與連接關(guān)系計算均可在秒級完成，關(guān)于時空庫集群系統(tǒng)的更多細(xì)節(jié)問題本文不展開描述，本文中算法實(shí)現(xiàn)的效率與計算量方面在時空庫集群中不存在性能瓶頸，僅對比算法計算出的結(jié)果數(shù)據(jù)量變化情況。

實(shí)驗(yàn)選用某大數(shù)據(jù)系統(tǒng)，數(shù)據(jù)存儲集群包含5個存儲計算服務(wù)節(jié)點(diǎn)，單節(jié)點(diǎn)配置為CPU Intel(R) Xeon(R) Gold 5218 CPU @ 2.3GHz，256GB內(nèi)存，24×1.2TB SAS硬盤，操作系統(tǒng)為CentOS Linux 7.6，移動對象用戶數(shù)約兩千萬，數(shù)據(jù)存儲周期九十天，數(shù)據(jù)庫內(nèi)的時空網(wǎng)格數(shù)據(jù)量約三千億條。伴隨分析工具采用Java語言開發(fā)，該程序輸入?yún)?shù)為主對象ID和時間段，輸出數(shù)據(jù)為在輸入的時間段內(nèi)，和輸入的主對象ID具有伴隨關(guān)系的關(guān)聯(lián)對象ID及其伴隨相似度。

從數(shù)據(jù)集中選取兩個具有伴隨關(guān)系的移動對象，其中一個作為主對象，另一個作為目標(biāo)伴隨對象，測試從一批移動對象中找出和主對象具有伴隨關(guān)系的目標(biāo)對象。將軌跡數(shù)據(jù)按照時空網(wǎng)格數(shù)據(jù)規(guī)則進(jìn)行預(yù)處理后(注：數(shù)據(jù)預(yù)處理采用Flink實(shí)時流計算集群，預(yù)處理邏輯及實(shí)現(xiàn)不在本文描述范圍內(nèi))寫入到時空庫集群系統(tǒng)中，然后分別在不同時間分片(五分鐘時間片和十分鐘時間片)情況下使用不包括耦合條件和包括耦合條件兩種檢索邏輯從數(shù)據(jù)庫中檢索出所有相關(guān)聯(lián)的對象ID，根據(jù)每個相關(guān)聯(lián)對象出現(xiàn)的次數(shù)，使用SGAS算法計算出伴隨相似度，并根據(jù)相似度對關(guān)聯(lián)對應(yīng)進(jìn)行排序，目標(biāo)對象在結(jié)果集中的排序越靠前，其準(zhǔn)確性越高。

下面分別對十分鐘時間片的快速伴隨與耦合快速伴隨和五分鐘時間片的快速伴隨與耦合快速伴隨進(jìn)行測試，并對比不同時間片情況下伴隨結(jié)果數(shù)據(jù)量的變化情況。測試驗(yàn)證數(shù)據(jù)如表1所示。

表1 十分鐘時間分片的實(shí)驗(yàn)結(jié)果數(shù)據(jù)

從表1中的測試驗(yàn)證數(shù)據(jù)可以看出在十分鐘時間片的情況下，使用時空網(wǎng)格耦合伴隨增加排除條件后，結(jié)果集中關(guān)聯(lián)對象的數(shù)量均有大幅度的減少，數(shù)量平均下降69%，顯著降低了干擾項的數(shù)量，提高了目標(biāo)對象在結(jié)果集中的排名。

從表2中的測試驗(yàn)證數(shù)據(jù)可以看出在五分鐘時間片的情況下，使用時空網(wǎng)格耦合伴隨增加排除條件后，結(jié)果集中關(guān)聯(lián)對象的數(shù)量也有較大幅度的減少，數(shù)量平均下降73%，略優(yōu)于十分鐘時間分片。

表2 五分鐘時間分片的實(shí)驗(yàn)結(jié)果數(shù)據(jù)

從表3中的測試驗(yàn)證數(shù)據(jù)可以看出五分鐘時間片的測試結(jié)果均優(yōu)于十分鐘時間片的測試結(jié)果，主要原因是時間分片越小，目標(biāo)對象的軌跡形成的時空網(wǎng)格越多，根據(jù)耦合得到的排除條件就越多，因此可以排除更多的干擾結(jié)果。

表3 不同時間分片的結(jié)果數(shù)據(jù)量變化

5 結(jié) 語

本文提出了一種針對大數(shù)據(jù)場景下,根據(jù)移動通信終端與通信基站之間的信令數(shù)據(jù)快速計算移動對象的伴隨對象的方法，該方法首先通過將信令數(shù)據(jù)中的時間戳轉(zhuǎn)換為時間片作為時間域，使用S2空間索引算法將信令數(shù)據(jù)中的位置點(diǎn)網(wǎng)格化并作為網(wǎng)格域；然后，將時間域和網(wǎng)格域組合為時空網(wǎng)格，并對時空網(wǎng)格進(jìn)行索引存入分布式數(shù)據(jù)庫中。在進(jìn)行伴隨計算時，首先，查詢出主對象在執(zhí)行時間段內(nèi)的時空網(wǎng)格，對時空網(wǎng)格進(jìn)行“8-鄰域”擴(kuò)域計算，并利用耦合模式添加排除條件；然后，在數(shù)據(jù)庫中檢索添加排除條件后的時空網(wǎng)格序列，并統(tǒng)計結(jié)果數(shù)據(jù)中的關(guān)聯(lián)移動出現(xiàn)的次數(shù)；最后，計算出時空網(wǎng)格相似度，對結(jié)果以相似度排序輸出。通過對測試數(shù)據(jù)進(jìn)行驗(yàn)證表明，算法能有效減少伴隨結(jié)果集的對象數(shù)量，降低干擾項的數(shù)量，顯著提高目標(biāo)對象在伴隨結(jié)果集中的排名。

雖然本文提出的時空耦合算法有效地降低了伴隨結(jié)果集中干擾項的數(shù)量，但是僅對那些持續(xù)運(yùn)動且運(yùn)動距離較長的對象伴隨有效，當(dāng)對象的軌跡中有較長時間的停留時，仍然可能存在一些無法排除的干擾項，下一步工作重點(diǎn)是識別對象的運(yùn)動和停留狀態(tài)，分別針對不同的狀態(tài)進(jìn)行伴隨特征研究。