[發明專利]一種基于Spark的分布式時空對象鄰近查詢方法

在審

• 申請號: 202110024086.1
• 申請日: 2021-01-08
• 公開（公告）號: CN112699173A
• 公開（公告）日: 2021-04-23
• 發明（設計）人: 于雷;李宗鑫;周含笑;姜宇;劉源;王建勛;李墨野;董麗娜;王兆祥;邵文杰
• 申請（專利權）人: 哈爾濱航天恒星數據系統科技有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/2455
• 代理公司: 北京君恒知識產權代理有限公司 11466
• 代理人: 張林

1.一種基于Spark的分布式時空對象鄰近查詢方法，其特征在于：具體方法步驟如下：

步驟一，基于時空軌跡數據，以時間序列構建Cassandra時空存儲模型；

步驟二，采用SQL-Server降維法，建立時空數據索引；

步驟三，根據時空查詢范圍與鄰近數量k的數值，計算需要查找的索引網格集合；

步驟四，從步驟三中獲得的網格集合，結合Cassandra時空存儲模型進行分布式時空對象鄰近查詢，其中分區節點進行本地時空對象鄰近查詢，得到分區時空對象鄰近查詢結果；

步驟五，合并分區時空對象鄰近結果，全局時空對象鄰近按照與該點的歐氏距離遠近排序，得到查詢結果；

步驟六，結合時間與Cassandra存儲節點個數，構造QueryRDD彈性分布式數據集，并根據Cassandra存儲備份策略重排QueryRDD；

步驟七，QueryRDD與Cassandra時空索引表連接，然后進行時空數據存儲表連接，并根據時間范圍(ts，te)在服務端過濾不需要的數據，得到TrajectoryRDD；

步驟八，取出TrajectoryRDD的segments軌跡段集合，對每個分區的軌跡段集合計算每個分區距離目標空間點最近topK個時空對象；

步驟九，最后合并所有分區，得到topK個時空對象，并根據距離從近到遠選取topK個時空對象，得到輸出結果完成查詢搜索。

2.根據權利要求1所述的一種基于Spark的分布式時空對象鄰近查詢方法，其特征在于：在步驟一中，所述的構建Cassandra時空存儲模型的過程細化為：

步驟一一，構建分區鍵和聚簇鍵；

步驟一二，使用Murmurhash分區算法模型，將所有的時空軌跡數據根據rid的hash值，劃分到Cassandra分布式數據庫環上的各個節點上；

步驟一三，將空間地理位置，按照0.5的fraction分辨率劃分成若干個格子，并按照時間順序排列。

3.根據權利要求1所述的一種基于Spark的分布式時空對象鄰近查詢方法，其特征在于：

在步驟二中，所述的SQL-Server降維法并建立索引的過程，細化步驟如下：

步驟二一，獲取格子id；

步驟二二，經計算得到經度的空間索引和緯度的空間索引；

步驟二三，根據計算公式求得格子區域id；

步驟二四，建立了一個索引數據表，該表以空間維為一維，以時間維為另一維，建立出時空網格索引存儲模型。

4.根據權利要求1所述的一種基于Spark的分布式時空對象鄰近查詢方法，其特征在于：在步驟三中，所述的索引網格集合，是通過計算外擴時空網格的方式實現的，具體步驟細化為：

步驟三一，編輯時空對象鄰近算法的代碼程序描述；

步驟三二，設查詢空間點坐標(lat，lon)，時間范圍為[ts，te]，定義鄰近數量為k；

步驟三三，計算需要查找的索引網格集合。

5.根據權利要求1所述的一種基于Spark的分布式時空對象鄰近查詢方法，其特征在于：在步驟九中，所述的完成查詢搜索的過程，具體步驟細化為：

步驟九一，初始化優先級隊列priorQueue長度為K；

步驟九二，獲取分區便利迭代器it；

步驟九三，判斷集合it中是否還包含元素，若是則執行步驟九四，否則跳轉至步驟九六；

步驟九四，計算it對應數據st_data與目標空間點的歐氏距離distance；

步驟九五，將priorQueue插入(st_data,distance)對象，并返回步驟九三重新進行判斷，否則迭代溢出進行步驟九六；

步驟九六，將priorQueue轉化為List。

6.根據權利要求5所述的一種基于Spark的分布式時空對象鄰近查詢方法，其特征在于：在步驟八或九中，所述的取出TrajectoryRDD的segments軌跡段集合和合并所有分區的過程，主要引用mapPartitions算子實現，該算子的具體執行過程如下：

mapPartitions算子用于執行RDD每個分區按照迭代器的方式進行操作，類似一個分區內的批處理過程；

結合算法，mapPartitions執行的操作是獲取分區的迭代器，并計算與目標空間點的歐氏距離，最多選擇topK個時空對象數據加入分區結果集，分區結果集的時空數據按照距離由近到遠排序，此時的TrajSegDistRDD返回(segment，distance)的元組；

其中segment是時空數據，distance是該時空數據點與目標空間點的歐氏距離；mapPartitions需要傳遞iterator迭代器，故此處實現一個computeTopK的函數，用于在每個分區中計算topK數值。