[發明專利]基于度量空間的支撐點并行枚舉方法及裝置

有效

• 申請號: 201810540034.8
• 申請日: 2018-05-30
• 公開（公告）號: CN108804383B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 毛睿;胡梓良;劉開南;陸敏華;陸克中;羅秋明;雷海軍;蔡曄;王毅;廖好;周池
• 申請（專利權）人: 深圳大學
• 主分類號: G06F17/10
• 分類號: G06F17/10;G06F9/50
• 代理公司: 深圳市恒申知識產權事務所(普通合伙) 44312
• 代理人: 袁文英

1.一種基于度量空間的支撐點并行枚舉方法，其特征在于，所述方法包括：

調用消息傳遞接口，將待計算數據分發到M個節點，每個節點分配到一份數據集，其中，M為正整數；

控制所述M個節點調用分叉函數，在每個節點內創建N個子進程，并將節點對應的數據集分配至N個子進程，使得每個子進程分配到一份子數據集，所述N為正整數，其中，每個節點都包含N個圖形處理器GPU；

控制節點內的子進程運行，通過所述子進程控制所述GPU對所述子進程對應的子數據集進行遍歷，對于遍歷到的查詢對象，基于預設的參考對象、查詢半徑及支撐點判斷所述查詢對象的三角不等性，得到所述查詢對象的三角不等性判斷結果；并由所述GPU根據所述查詢對象的三角不等性判斷結果，得到所述查詢對象的枚舉結果；

從所述M個節點的N個子進程獲取所述待計算數據的枚舉結果，并保存，其中，子進程接收其控制的GPU反饋的所述子進程對應的子數據集中各查詢對象的枚舉結果；

其中，利用以下三角不等性公式進行三角不等性判斷：

|d(q,p)-d(p,x)|r，d(q,p)+d(p,x)＝r

其中，d()表示距離函數，q表示遍歷到的查詢對象，p表示支撐點、x表示參考對象，r表示查詢半徑；

當所述查詢對象滿足所述三角不等性公式的任意一個不等式時，確定所述查詢對象的三角不等性判斷結果為：可直接查詢；

當所述查詢對象不滿足所述三角不等性的任意一個不等式時，確定所述查詢對象的三角不等性判斷結果為：不可直接查詢；

當無法確定所述查詢對象是否滿足所述三角不等性公式中的任意一個不等式時，則確定所述查詢對象的三角不等性判斷結果為：無法確定。

2.根據權利要求1所述的方法，其特征在于，所述由所述GPU根據所述查詢對象的三角不等性判斷結果，得到所述查詢對象的枚舉結果，具體包括：

對于三角不等性判斷結果為無法確定的查詢對象，所述GPU對所述查詢對象進行距離計算，并將所述查詢對象的距離計算次數加1，將所述查詢對象的最后的距離計算次數作為所述查詢對象的枚舉結果。

3.一種基于度量空間的支撐點并行枚舉裝置，其特征在于，所述裝置包括：

調用分配模塊，用于調用消息傳遞接口，將待計算數據分發到M個節點，每個節點分配到一份數據集，其中，M為正整數；

控制處理模塊，用于控制所述M個節點調用分叉函數，在每個節點內創建N個子進程，并將節點對應的數據集分配至N個子進程，使得每個子進程分配到一份子數據集，所述N為正整數，其中，每個節點都包含N個圖形處理器GPU；

遍歷枚舉模塊，包括控制判斷模塊和獲取保存模塊，所述控制判斷模塊控制節點內的子進程運行，通過所述子進程控制所述GPU對所述子進程對應的子數據集進行遍歷，對于遍歷到的查詢對象，基于預設的參考對象、查詢半徑及支撐點判斷所述查詢對象的三角不等性，得到所述查詢對象的三角不等性判斷結果；并由所述GPU根據所述查詢對象的三角不等性判斷結果，得到所述查詢對象的枚舉結果；

所述獲取保存模塊用于從所述M個節點的N個子進程獲取所述待計算數據的枚舉結果，并保存，其中，子進程接收其控制的GPU反饋的所述子進程對應的子數據集中各查詢對象的枚舉結果；

其中，所述控制判斷 模塊利用以下三角不等性公式進行三角不等性判斷：

|d(q,p)-d(p,x)|r，d(q,p)+d(p,x)＝r

其中，d()表示距離函數，q表示遍歷到的查詢對象，p表示支撐點、x表示參考對象，r表示查詢半徑；

當所述查詢對象滿足所述三角不等性公式的任意一個不等式時，確定所述查詢對象的三角不等性判斷結果為：可直接查詢；

當所述查詢對象不滿足所述三角不等性的任意一個不等式時，確定所述查詢對象的三角不等性判斷結果為：不可直接查詢；

當無法確定所述查詢對象是否滿足所述三角不等性公式中的任意一個不等式時，則確定所述查詢對象的三角不等性判斷結果為：無法確定。

4.根據權利要求3 所述的裝置，其特征在于，所述控制判斷模塊具體用于：

控制節點內的子進程運行，通過所述子進程控制所述GPU對所述子進程對應的子數據集進行遍歷，對于遍歷到的查詢對象，基于預設的參考對象、查詢半徑及支撐點判斷所述查詢對象的三角不等性，得到所述查詢對象的三角不等性判斷結果；對于三角不等性判斷結果為無法確定的查詢對象，由GPU對所述查詢對象進行距離計算，并將所述查詢對象的距離計算次數加1，將所述查詢對象的最后的距離計算次數作為所述查詢對象的枚舉結果。