[發(fā)明專利]基于位圖的軌跡編碼方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710402219.8
• 申請(qǐng)日: 2017-06-01
• 公開（公告）號(hào): CN107247761B
• 公開（公告）日: 2021-10-15
• 發(fā)明（設(shè)計(jì)）人: 張蕊;周悅淇;劉克中;徐寧
• 申請(qǐng)（專利權(quán)）人: 武漢理工大學(xué)
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/2453
• 代理公司: 武漢瀛卓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42255
• 代理人: 朱詩(shī)恩

本發(fā)明公開了一種基于位圖的軌跡編碼方法，包括在預(yù)設(shè)的劃分精度下，空間被劃分為多個(gè)近似網(wǎng)格形狀的子空間，每個(gè)網(wǎng)格空間得到一個(gè)唯一的標(biāo)識(shí)等步驟：本發(fā)明基于位圖技術(shù)，使用位圖數(shù)據(jù)結(jié)構(gòu)的最大優(yōu)點(diǎn)是節(jié)省存儲(chǔ)空間和高計(jì)算效率，數(shù)據(jù)庫(kù)使用位圖索引對(duì)值域基數(shù)較小和固定的字段建立索引，計(jì)算速度快、存儲(chǔ)空間小；位圖技術(shù)還能利用CPU指令集的優(yōu)化極大的提升計(jì)算效率；歷史軌跡數(shù)據(jù)包含的空間位置是固定的，但是空間坐標(biāo)的值域類型是浮點(diǎn)數(shù)，本發(fā)明通過設(shè)計(jì)編碼，使軌跡數(shù)據(jù)的查詢可以利用位圖技術(shù)的優(yōu)勢(shì)而實(shí)現(xiàn)高效的軌跡數(shù)據(jù)分析。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)大數(shù)據(jù)處理領(lǐng)域，具體為一種基于位圖的軌跡編碼方法。

背景技術(shù)

交通管理、氣象監(jiān)控、移動(dòng)計(jì)算等應(yīng)用需要管理大量的時(shí)空數(shù)據(jù)，隨著移動(dòng)設(shè)備的普及、公共監(jiān)管的發(fā)展和完善，移動(dòng)計(jì)算和基于位置的服務(wù)出現(xiàn)了發(fā)展熱潮，定位數(shù)據(jù)增長(zhǎng)、定位精度的提高為研究定位數(shù)據(jù)提供了數(shù)據(jù)基礎(chǔ)，也形成了海量的軌跡數(shù)據(jù)積累，例如，車輛GPS的日均數(shù)據(jù)量(采樣點(diǎn))在千萬(wàn)到億的數(shù)量級(jí)，軌跡數(shù)據(jù)的存儲(chǔ)體積達(dá)到了PB數(shù)量級(jí)，因此軌跡數(shù)據(jù)的分析查詢壓力大，需要可行高效的查詢方案。

位置數(shù)據(jù)的管理和查詢按場(chǎng)景可以分為實(shí)時(shí)查詢和歷史數(shù)據(jù)查詢兩類，在歷史軌跡查詢方案中，有一種是基于空間數(shù)據(jù)庫(kù)方案。現(xiàn)有的關(guān)系型數(shù)據(jù)庫(kù)可以基于空間查詢插件來(lái)實(shí)現(xiàn)管理空間數(shù)據(jù)的效果，但是，現(xiàn)有的拓展插件方案，例如PostGIS主要針對(duì)空間特征的計(jì)算和查詢，擅長(zhǎng)轉(zhuǎn)換為平面幾何關(guān)系的查詢，而像移動(dòng)設(shè)備產(chǎn)生的數(shù)據(jù)不僅帶有空間信息，還有時(shí)間信息，軌跡不是理想的可以簡(jiǎn)單轉(zhuǎn)換為用幾何數(shù)據(jù)類型描述的數(shù)據(jù)，拓展方案中實(shí)現(xiàn)的空間索引也缺少為時(shí)空類型的查詢問題的優(yōu)化，例如時(shí)空條件組合的范圍查詢，對(duì)時(shí)空數(shù)據(jù)的支持還不完善。

通過移動(dòng)設(shè)備的GPS傳感器或者專用定位方案(例如船舶自動(dòng)識(shí)別系統(tǒng)AIS)，它們產(chǎn)生的位置采樣點(diǎn)，與獨(dú)立的位置點(diǎn)不同，具有時(shí)序關(guān)系和空間特征，在管理上也適合應(yīng)用于軌跡模型進(jìn)行數(shù)據(jù)挖掘，分析交通運(yùn)輸中的規(guī)律特征，提出路線推薦等應(yīng)用，而軌跡在常規(guī)的數(shù)據(jù)庫(kù)系統(tǒng)中沒有對(duì)應(yīng)的數(shù)據(jù)類型，但對(duì)軌跡數(shù)據(jù)的查詢和存儲(chǔ)有專門設(shè)計(jì)的索引技術(shù)和系統(tǒng)方案，例如SETI和TrajStore，另外，軌跡數(shù)據(jù)的提取與軌跡分析算法缺乏統(tǒng)一的環(huán)境支持，限制了海量軌跡數(shù)據(jù)的分析應(yīng)用。

Hadoop、Spark是興起的大規(guī)模數(shù)據(jù)計(jì)算分析的分布式計(jì)算方案，基于分布式計(jì)算實(shí)現(xiàn)大規(guī)模時(shí)空數(shù)據(jù)的分析是當(dāng)前的熱門問題，例如SpatialHadoop、GeoSpark是基于分布式計(jì)算平臺(tái)實(shí)現(xiàn)空間數(shù)據(jù)分析的方案，它們實(shí)現(xiàn)的分布式索引方案能夠支持點(diǎn)、多邊形等空間類型數(shù)據(jù)的并行計(jì)算和查詢，但是軌跡數(shù)據(jù)的查詢、計(jì)算需求與常規(guī)的空間數(shù)據(jù)不同，它們支持的數(shù)據(jù)結(jié)構(gòu)缺少對(duì)軌跡查詢問題的直接支持。而另一方面，也有研究基于分布式平臺(tái)實(shí)現(xiàn)的例如軌跡的kNN查詢方案，但是方案往往受限于解決個(gè)別的軌跡問題。

發(fā)明內(nèi)容

本發(fā)明的目的是為了克服上述不足提供一種基于位圖的軌跡編碼方法。

本發(fā)明基于位圖的軌跡編碼方法，包括以下步驟：

第1步：在預(yù)設(shè)的劃分精度下，空間被劃分為多個(gè)近似網(wǎng)格形狀的子空間，每個(gè)網(wǎng)格空間得到一個(gè)唯一的標(biāo)識(shí)；

第2步：將一條軌跡拆分成連續(xù)的軌跡段，逐個(gè)對(duì)所述軌跡段進(jìn)行遍歷，分別計(jì)算出與第1步中得到的網(wǎng)格空間中有共同位置關(guān)系的網(wǎng)格空間，從而得到所述軌跡對(duì)應(yīng)的一組網(wǎng)格標(biāo)識(shí)序列；

第3步：將第2步中得到的所述一組網(wǎng)格標(biāo)識(shí)序列，進(jìn)行去除重復(fù)項(xiàng)處理；

第4步：將第3步中進(jìn)行去除重復(fù)項(xiàng)處理后的一組網(wǎng)格編碼序列轉(zhuǎn)換為一個(gè)位圖格式數(shù)據(jù)。

所述第2步具體包括以下步驟：

第21步：對(duì)于一個(gè)所述軌跡段，找出屬于該軌跡段的所有軌跡點(diǎn)，若軌跡點(diǎn)之間間隔超出劃分網(wǎng)格空間時(shí)設(shè)置的最大距離，則插入補(bǔ)充點(diǎn)使新的軌跡段能被區(qū)域包圍；