[發(fā)明專利]移動(dòng)醫(yī)療的倒排泰森多邊形的分布式時(shí)空索引的代表點(diǎn)獲取方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201711372229.8
• 申請(qǐng)日: 2017-10-19
• 公開(kāi)（公告）號(hào): CN107958087A
• 公開(kāi)（公告）日: 2018-04-24
• 發(fā)明（設(shè)計(jì)）人: 季長(zhǎng)清;劉飛;高楊;吳銳;劉暢;汪祖民
• 申請(qǐng)（專利權(quán)）人: 大連大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G16H50/70
• 代理公司: 大連智高專利事務(wù)所(特殊普通合伙)21235
• 代理人: 畢進(jìn)

本申請(qǐng)為申請(qǐng)?zhí)?017109759923、申請(qǐng)日2017-10-19、發(fā)明名稱“移動(dòng)醫(yī)療的倒排泰森多邊形的分布式時(shí)空索引方法及應(yīng)用”的分案申請(qǐng)。

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)索引領(lǐng)域，涉及大數(shù)據(jù)處理與空間查詢算法應(yīng)用。

背景技術(shù)

隨著移動(dòng)通信和基于位置服務(wù)相關(guān)技術(shù)的快速發(fā)展，云計(jì)算、大數(shù)據(jù)、物聯(lián)網(wǎng)、移動(dòng)計(jì)算以及空間定位等技術(shù)也逐步成熟，而GPS、攝像頭、藍(lán)牙數(shù)據(jù)等也在不斷的增加，涌現(xiàn)了大量的空間數(shù)據(jù)，這使得各種空間數(shù)據(jù)或?qū)ο蟮拇鎯?chǔ)與處理中面臨著巨大的挑戰(zhàn)。

數(shù)據(jù)進(jìn)行大數(shù)據(jù)處理時(shí)，經(jīng)常會(huì)遇到運(yùn)算時(shí)間長(zhǎng)、時(shí)空數(shù)據(jù)查詢效率低的問(wèn)題。而傳統(tǒng)計(jì)算機(jī)的運(yùn)算體系因?yàn)橹恢С钟邢薜木€程，所以并行與分布式性能差，單機(jī)的計(jì)算資源常常有限(如受限于硬盤(pán)或內(nèi)存的大小，CPU單元計(jì)算能力不強(qiáng)等)而無(wú)法直接應(yīng)用。

索引對(duì)大規(guī)模數(shù)據(jù)訪問(wèn)效率有著重要的影響。新的空間索引方法需要引入到傳統(tǒng)的數(shù)據(jù)庫(kù)處理引擎中，從而出現(xiàn)了R-tree結(jié)構(gòu)。R-tree相當(dāng)于二維B+樹(shù)索引在多維數(shù)據(jù)環(huán)境下的擴(kuò)展。目前基于R-tree索引的來(lái)進(jìn)行最近鄰(Nearest Neighbor,NN)查詢的算法有很多，但這些方法都集中在單獨(dú)的計(jì)算機(jī)上單線程執(zhí)行任務(wù)。當(dāng)數(shù)據(jù)規(guī)模迅速增長(zhǎng)時(shí)，就要應(yīng)用分布式數(shù)據(jù)庫(kù)系統(tǒng)來(lái)進(jìn)行索引與數(shù)據(jù)查詢等處理了。

發(fā)明內(nèi)容

為了提高現(xiàn)有數(shù)據(jù)查詢方法索引效率，本發(fā)明提供如下方案：一種移動(dòng)醫(yī)療的倒排泰森多邊形的分布式時(shí)空索引方法，其步驟如下：

使用Spark來(lái)構(gòu)建基于倒排Voronoi圖索引，3維空間中給定兩個(gè)醫(yī)療相關(guān)數(shù)據(jù)集R和S，R是醫(yī)療資源數(shù)據(jù)集，其包括位置數(shù)據(jù)集，S為患者數(shù)據(jù)集，其包括位置數(shù)據(jù)，把這兩個(gè)數(shù)據(jù)集上傳到HDFS中，Spark按默認(rèn)機(jī)制進(jìn)行分片，部分mappers同時(shí)并行運(yùn)行，在Spark任務(wù)中使用默認(rèn)的reducer，在啟動(dòng)map函數(shù)之前，使用預(yù)聚類算法得到一個(gè)區(qū)域的醫(yī)療資源的代表點(diǎn)p，并加載到每個(gè)map的主存中；

在每一個(gè)map處理進(jìn)程中，它將依次利用TextInputFormat來(lái)讀取輸入的分片，TextInputFormat以流的方式將文件讀取數(shù)據(jù)到Mapper的實(shí)例中；

計(jì)算每一個(gè)醫(yī)療資源數(shù)據(jù)r對(duì)象，患者數(shù)據(jù)s對(duì)象與代表點(diǎn)p之間的距離，并將r，s分配給最接近的代表點(diǎn)P，在算法中，每個(gè)對(duì)象的醫(yī)療資源最接近的代表點(diǎn)都被聚集在一個(gè)Voronoi單元格中，它將產(chǎn)成m個(gè)Voronoi單元格，程序在執(zhí)行時(shí)輸出<VCm，List(P_i)>對(duì)，mapper輸出原始數(shù)據(jù)集到最靠近的分區(qū)的每一個(gè)對(duì)象r、s及其分區(qū)VC_m的id；將mapper輸出到Spark的文件系統(tǒng)。

Voronoi圖將一個(gè)空間劃分為多個(gè)不相交的多邊形，在每個(gè)多邊形中的某一個(gè)點(diǎn)的最近鄰均位于該點(diǎn)所在的Voronoi單元格內(nèi)，圖中的每個(gè)多邊形稱為與點(diǎn)p相關(guān)聯(lián)的Voronoi單元格，點(diǎn)p所在的單元格內(nèi)的任何點(diǎn)都是p的最近鄰。

倒排Voronoi索引包含兩個(gè)部分：主索引，包括所有的聚類中心；第二索引，包括儲(chǔ)存在每個(gè)分區(qū)VC的對(duì)像隊(duì)列。

代表點(diǎn)的獲取方法，確定內(nèi)部聚類點(diǎn)與相鄰點(diǎn)，將內(nèi)部聚類點(diǎn)的數(shù)據(jù)聚類，聚類后選出聚類中心進(jìn)行索引，所需數(shù)據(jù)為與內(nèi)部聚類點(diǎn)連接的相鄰點(diǎn)，以這個(gè)內(nèi)部聚類點(diǎn)為圓心，包含相鄰的聚類中心點(diǎn)建立圓，以這個(gè)圓為外接圓的三角形作為Delaunay三角形，本方法中將兩個(gè)不同的內(nèi)部聚類點(diǎn)分別建立Delaunay三角形，這兩個(gè)Delaunay三角形以相鄰點(diǎn)為共同點(diǎn)建立Delaunay三角網(wǎng)，將數(shù)據(jù)對(duì)象分割為幾個(gè)大分區(qū)，選擇其中一聚類代表點(diǎn)成為代表點(diǎn)，被劃分的每個(gè)對(duì)象以被聚類在一個(gè)Voronoi單元中，每個(gè)Voronoi網(wǎng)格中含有對(duì)象id。

Voronoi圖由VD(p)＝{V(p₁),V(p₂),...,V(p_m)}，其中：VD(p)是關(guān)于P的Voronoi圖合集，V(p₁)是p1的Voronoi圖，給出的與所有的點(diǎn)相關(guān)聯(lián)的集合，被稱為p產(chǎn)生的遵循距離函數(shù)Dist()的Voronoi圖，這里每個(gè)p點(diǎn)的Voronoi圖一定包括比其他任何點(diǎn)更接近q的所有點(diǎn)，因而一個(gè)查詢點(diǎn)q的近鄰是閉合的Voronoi圖；