[發明專利]一種基于位置的移動數據存儲系統

有效

• 申請號: 201811654923.3
• 申請日: 2018-12-29
• 公開（公告）號: CN109815303B
• 公開（公告）日: 2020-10-13
• 發明（設計）人: 廖清;丁燁;漆舒漢;蔣琳;王軒
• 申請（專利權）人: 哈爾濱工業大學（深圳）
• 主分類號: G06F16/29
• 分類號: G06F16/29
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 麥小嬋;郝傳鑫

本申請涉及一種基于位置的移動數據存儲系統及其優化方法，在預設的負載和存儲預算的情況下，根據查詢范圍及存儲系統中的原始數據，生成用于查詢的多個候選副本，并使用查詢成本評估模塊對上述多個副本構成的副本集合進行評估，并從中選擇出一個成本最低或接近最低的副本集合。該系統用于實現對基于位置的移動大數據分布式存儲系統的寬查詢范圍性能的優化，并在此基礎上提出了貪婪算法及線性規劃舍入算法進一步對存儲系統的性能進行進一步的發掘。

技術領域

本發明涉及移動通信領域，具體涉及了一種基于位置的移動數據存儲系統。

背景技術

隨著數據采集能力的發展，通過數以億計的電子設備，例如手機、平板電腦、車載GPS導航及多種類型的傳感器，采集人或物的巨量位置的移動數據變得更加簡單。但是，存儲這些位置的移動數據帶來了兩個挑戰：1)怎么有效的處理大量的地理位置移動數據的查詢；2)如何降低存儲服務的成本。

位置移動數據通常具有三個共同點:

1.所有的數據都具有三個核心屬性：目標ID、時間戳和位置信息；

2.這些數據庫的查詢通常在通過特定的空間范圍和時間范圍信息進行查詢；

3.在處理空間-時間范圍查詢時，特別當查詢到的結果特別多時即寬查詢范圍時，主流的大數據存儲和管理系統不適合存儲和處理這些位置移動數據。因為，這些系統不能根據時間和空間的臨近性物理地聚類記錄，這會導致主流系統觸發非常多的低效率的隨機讀取。

為了解決隨機讀取多的問題，TrajStore和PIST通過根據時間-空間代理來共同定位數據，并使用相對較大的分區，但TrajStore和PIST不是采用分布式構架的系統，都不能擴展為TB量級；CloST和SpatialHadoop是兩個基于Hadoop的系統，旨在提供可擴展的分布式存儲和并行查詢處理的大型基于位置的移動數據系統；SATO是一個空間數據分區框架，可以快速分析和分區空間數據，并能夠提供一個大小可變的查詢處理的最有空間分區策略。

BLOT系統，是一種系統級的抽象，表示那些用于存儲基于位置的大型移動數據的專用存儲系統。上述的TrajStore、PIST、CloSTridium、SpatialHadoop和SATO都可以視為BLOT系統的具體例子。附圖1展示了BLOT系統中的管理數據和查詢數據的過程。

在BLOT系統中存儲了大量的基于位置的移動數據，每條記錄都以下面的格式進行存儲：(OID，TIME，LOC，A₁，……，A_m)。其中：OID為目標ID，TIME為時間戳，LOC是目標ID在某個時間點上所處的位置，A₁……A_m是根據數據庫應用場景變化的通用屬性。我們將前三個屬性成為核心屬性，其他屬性稱為公共屬性。

BLOT系統通過核心屬性將大數據集分割成相對較小的分區。例如，在TrajStore和CloST中，記錄先按照位置(LOC)進行分區，之后再按照時間進行分區。同一分區中的記錄一起被存儲在一個存儲單元中，該存儲單元為順序讀取進行了優化。通常，存儲單元大于一個磁盤頁的，從數百KB到及兆字節。在BLOT系統中，記錄通常是按順序訪問的，因此可以有效的處理較寬的時間-空間的范圍查詢；存儲單元的數量走狗小，這樣我們可以方便的維護分區索引。

數據分區可以存儲任何格式的記錄，通常將每個分區都存儲為CSV文件，每行指定一個記錄。該格式雖然易于處理，但存儲利用率很低。對于大型數據集，尤其是使用云存儲時，使用上述方法的成本較高。為了減小存儲的大小，BLOT系統使用各種壓縮技術對分區中的記錄進行編碼：1)使用二進制格式代替文本格式；2)應用通用的壓縮算法對整個分區進行壓縮；2)以列方式管理數據，然后應用列向編碼方案(如增量編碼和運行長度編碼)。