[發明專利]面向海量軌跡點數據的時空索引構建方法

有效

• 申請號: 201710270989.1
• 申請日: 2017-04-24
• 公開（公告）號: CN107220285B
• 公開（公告）日: 2020-01-21
• 發明（設計）人: 陳昭;王磊;刁博宇;徐勇軍
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 11280 北京泛華偉業知識產權代理有限公司
• 代理人: 王勇

本發明涉及一種面向海量軌跡點數據的并行時空索引構建方法，以軌跡點數據文件作為索引單元，降低了索引的存儲消耗，使索引結構具有高度的可擴展性；同時使用了希爾伯特曲線對數據文件進行劃分，相比其他的多維到一維映射的方式，希爾伯特曲線因其優秀的空間填充特性使得劃分效果更良好，能夠降低數據傾斜發生的概率。

技術領域

本發明涉及信息檢索領域，特別涉及一種面向海量軌跡點數據的時空索引構建方法。

背景技術

隨著科學技術的發展，當今世界已進入大數據時代。數據規模的快速增長，使得大數據需要具備全局表達力，時空大數據因其能夠體現時間、空間以及對象之間的關聯關系，成為了重要的大數據之一。然而，時空大數據之間相對復雜的關系及其動態演化的特性，也帶來了檢索查詢的困難。軌跡點數據就屬于時空大數據，其具體是指，在時空環境下，通過對移動對象運動過程的采樣所獲得的數據信息。近年來，衛星、無線網絡，以及定位設備高速發展，大量移動物體的軌跡點數據呈急速增長的趨勢，對于軌跡點數據的索引構建及優化查詢成為了近年來的熱門研究。

Hadoop是當下流行的一種分布式計算框架，適用于各類大規模數據的計算處理場景，具有廣泛的應用基礎，目前已有一些基于該框架及其生態軟件提出的時空索引方法，如基于HBase的Q樹時空索引、基于HBase的網格R樹混合時空索引等。現有的時空索引構建方法，大多將數據記錄條作為索引單元，這種方式導致存儲消耗大且索引構建效率較低，無法滿足不同類型的時空大數據快速增長的需求。

發明內容

本發明的目的是提供一種面向海量軌跡點數據的時空索引構建方法，該方法能夠克服上述現有技術的缺陷，在分布式環境下并行構建軌跡點數據的時空索引，效率較高；并且以數據文件作為索引單元，使索引結構具有靈活的擴展性。

本發明采用的技術方案如下：一種面向海量軌跡點數據的時空索引構建方法，包括以下步驟：

步驟1)、將軌跡點數據存儲在軌跡點數據文件中；

步驟2)、以所述步驟1)中的軌跡點數據文件為索引單元構建索引樹。

優選的，所述步驟1)中的軌跡點數據至少包含時間信息和二維位置信息。

優選的，所述步驟2)進一步包括：

步驟21)、將所述軌跡點數據文件劃分到至少一個計算單元中；

步驟22)、所述計算單元基于空間索引結構構建時空索引。

優選的，當所述計算單元為多個并行計算單元時，所述步驟21)中對軌跡點數據文件的劃分為有序劃分。

優選的，利用空間填充曲線實現所述步驟21)的有序劃分。

優選的，所述空間填充曲線為希爾伯特曲線。

優選的，所述步驟21)進一步包括：

步驟211)計算用于表征所述軌跡點數據文件的二維空間信息的二維希爾伯特值；

步驟212)根據所述步驟211)中計算得出的二維希爾伯特值計算用于表征所述軌跡點數據文件的三維空間信息的三維希爾伯特值；

步驟213)根據所述步驟212)中計算得出的三維希爾伯特值對所述軌跡點數據文件進行劃分。

優選的，所述步驟22)中的空間索引結構是R*樹結構。

優選的，可基于MapReduce或Spark編程框架實現對所述多級時空索引樹的構建。

根據本發明的另一個方面，提供一種基于上述方法構建的索引樹對軌跡點數據進行查詢的方法，包括：

步驟a)、遍歷所述索引樹的根節點，取得根節點列表；