[發(fā)明專利]面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法

有效

• 申請?zhí)枺?/td>: 201710270989.1
• 申請日: 2017-04-24
• 公開（公告）號: CN107220285B
• 公開（公告）日: 2020-01-21
• 發(fā)明（設(shè)計(jì)）人: 陳昭;王磊;刁博宇;徐勇軍
• 申請（專利權(quán)）人: 中國科學(xué)院計(jì)算技術(shù)研究所
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 11280 北京泛華偉業(yè)知識產(chǎn)權(quán)代理有限公司
• 代理人: 王勇

1.一種面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，包括以下步驟：

步驟1)、將軌跡點(diǎn)數(shù)據(jù)存儲為若干個軌跡點(diǎn)數(shù)據(jù)文件，所述軌跡點(diǎn)數(shù)據(jù)至少包含時間信息和二維位置信息；

步驟2)、獲取每個軌跡點(diǎn)數(shù)據(jù)文件包含的軌跡點(diǎn)數(shù)據(jù)的時空取值范圍；

步驟3)、以所述軌跡點(diǎn)數(shù)據(jù)文件為索引單元構(gòu)建索引樹；

其中所述索引樹是通過下面步驟構(gòu)建的：

1)葉子節(jié)點(diǎn)的構(gòu)建：每個葉子節(jié)點(diǎn)包含了至少一個索引單元，以及可以框住上述所有索引單元的最小時空矩形；所述最小時空矩形是指其所包含的所有軌跡點(diǎn)數(shù)據(jù)文件的時空取值范圍；

2)非葉子節(jié)點(diǎn)的構(gòu)建：每個非葉子節(jié)點(diǎn)包含了其子節(jié)點(diǎn)的指針數(shù)組以及可以框住其所有子節(jié)點(diǎn)的最小時空矩形；

3)索引子樹根節(jié)點(diǎn)的構(gòu)建：每個計(jì)算單元上的索引子樹根節(jié)點(diǎn)，包含了其子節(jié)點(diǎn)的指針數(shù)組以及可以框住該根節(jié)點(diǎn)所有子節(jié)點(diǎn)的最小時空矩形，如果索引子樹根節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則包含了該計(jì)算單元上的所有軌跡點(diǎn)數(shù)據(jù)文件的時空取值范圍；

4)索引樹根節(jié)點(diǎn)的構(gòu)建：每個索引樹根節(jié)點(diǎn)包含了所有計(jì)算單元上軌跡點(diǎn)數(shù)據(jù)文件的記錄路徑以及可以框住該根節(jié)點(diǎn)所有子節(jié)點(diǎn)的最小時空矩形。

2.根據(jù)權(quán)利要求1所述的面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，其特征在于，所述步驟3)進(jìn)一步包括：

步驟31)、將所述軌跡點(diǎn)數(shù)據(jù)文件劃分到至少一個計(jì)算單元中；

步驟32)、所述計(jì)算單元基于空間索引結(jié)構(gòu)構(gòu)建時空索引。

3.根據(jù)權(quán)利要求2所述的面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，其特征在于，當(dāng)所述計(jì)算單元為多個并行計(jì)算單元時，所述步驟31)中對軌跡點(diǎn)數(shù)據(jù)文件的劃分為有序劃分。

4.根據(jù)權(quán)利要求3所述的面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，其特征在于，利用空間填充曲線實(shí)現(xiàn)所述步驟31)的有序劃分。

5.根據(jù)權(quán)利要求4所述的面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，其特征在于，所述空間填充曲線為希爾伯特曲線。

6.根據(jù)權(quán)利要求5所述的面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，其特征在于，所述步驟31)進(jìn)一步包括：

步驟311)計(jì)算用于表征所述軌跡點(diǎn)數(shù)據(jù)文件的二維空間信息的二維希爾伯特值；

步驟312)根據(jù)所述步驟311)中計(jì)算得出的二維希爾伯特值計(jì)算用于表征所述軌跡點(diǎn)數(shù)據(jù)文件的三維空間信息的三維希爾伯特值；

步驟313)根據(jù)所述步驟312)中計(jì)算得出的三維希爾伯特值對所述軌跡點(diǎn)數(shù)據(jù)文件進(jìn)行劃分。

7.根據(jù)權(quán)利要求3至6中任一項(xiàng)所述的面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，其特征在于，所述步驟32)中的空間索引結(jié)構(gòu)是R*樹結(jié)構(gòu)。

8.根據(jù)權(quán)利要求3至6中任一項(xiàng)所述的面向海量軌跡點(diǎn)數(shù)據(jù)的時空索引構(gòu)建方法，其特征在于，可基于MapReduce或Spark編程框架實(shí)現(xiàn)對所述索引樹的構(gòu)建。

9.一種利用如權(quán)利要求1至8中任一項(xiàng)構(gòu)建的索引樹對軌跡點(diǎn)數(shù)據(jù)進(jìn)行查詢的方法，包括：

步驟a)、遍歷所述索引樹的根節(jié)點(diǎn)，取得根節(jié)點(diǎn)列表；

步驟b)、查詢所述步驟a)取得的根節(jié)點(diǎn)列表，取得子節(jié)點(diǎn)列表；

步驟c)、并行遍歷步驟b)中取得的子節(jié)點(diǎn)列表，取得軌跡點(diǎn)數(shù)據(jù)文件列表。

10.根據(jù)權(quán)利要求9所述的方法，其特征在于，該方法可基于MapReduce或Spark編程框架實(shí)現(xiàn)。