[發明專利]一種面向空間數據的高效空間k核挖掘方法

有效

• 申請號: 202011148132.0
• 申請日: 2020-10-23
• 公開（公告）號: CN112445838B
• 公開（公告）日: 2022-03-22
• 發明（設計）人: 王瀟楊;劉玉峰;陳晨;聶坤;孫仁杰;張夢琪;吳艷萍
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/22;G06F16/29
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 劉靜

1.一種面向空間數據的高效空間k核挖掘方法，其特征在于，所述空間k核需要滿足三個條件：兩個頂點之間的距離不大于距離閾值r；每個頂點至少有k個鄰居；是極大的，即它的任何超圖都不能滿足前面兩個條件；該方法包括以下步驟：

步驟一，運用四叉樹框架，對帶有地理位置的空間數據集不斷進行四等劃分，直到數據集中每個點都位于所劃分的矩形區域內；

步驟二，遍歷數據集內頂點，以頂點為圓心，距離閾值r為半徑，畫一個圓；將該圓的外切矩形作為頂點的上界，其內接矩形作為頂點的下界，得到頂點的上界和下界；

步驟三，結合邊界修剪策略生成空間圖：定義為頂點的上界值，r為頂點的下界值；頂點到區域的距離，為頂點到區域四個頂點的距離，如果四叉樹中某個區域與頂點的最小距離大于上界值時，需要刪除該區域；如果該區域與頂點的最大距離小于等于下界值時，則該區域內的所有點都可以直接放入該頂點的鄰居集合中；如果該區域與頂點的最小距離大于下界值且最大距離小于等于上界值時，需要進一步計算區域內所包含的點與該頂點之間的距離大小；處理完所有的頂點后，如果兩個點之間的距離小于給定距離閾值r，那么它們之間將會用一條邊相連接，從而生成空間圖；

步驟四，在空間圖上進行空間k核的挖掘，包括：運用核分解技術，計算空間圖中頂點鄰居的數量，并且不斷地刪除鄰居數量小于k的頂點，直到空間圖中所有的頂點其鄰居的數量都大于等于k，最終得到空間k核；輸出所有滿足條件的空間k核，即被挖掘的內聚子圖。

2.根據權利要求1所述的一種面向空間數據的高效空間k核挖掘方法，其特征在于，所述步驟二包括：在步驟一劃分區域內，以頂點為圓心，距離閾值r為半徑，畫一個圓；將該圓的外切矩形作為頂點的上界，其邊長為2r×2r；將該圓的內接矩形作為頂點的下界，其邊長為

3.根據權利要求1所述的一種面向空間數據的高效空間 k核挖掘方法，其特征在于，所述步驟三中具體的修剪策略包括：

(a)如果被劃分的區域為空，那么就刪除該區域；

(b)如果區域不為空，但是與頂點的最小距離大于其上界值，那么仍然刪除該區域；

(c)如果區域與頂點的最大距離小于等于下界值，則可以直接將該區域內的頂點直接插入到頂點的鄰居集合中；

(d)如果區域與頂點的最大距離小于等于上界值，但是最小距離大于下界值，那么需要進一步計算區域內的頂點與該頂點的距離，從而判斷其是否小于等于距離閾值r。

4.一種服務器，所述服務器包括處理器和存儲器，所述存儲器中存儲有至少一條指令、至少一段程序、代碼集或指令集，所述至少一條指令、所述至少一段程序、所述代碼集或指令集由所述處理器加載并執行以實現如權利要求1至3任一項所述的方法。

5.一種計算機可讀存儲介質，所述存儲介質中存儲有至少一條指令、至少一段程序、代碼集或指令集，所述至少一條指令、所述至少一段程序、所述代碼集或指令集由處理器加載并執行以實現如權利要求1至3任一項所述的方法。