一種基於不確定數據集的雙色反最鄰近查詢的方法及裝置的製作方法
2023-05-05 00:54:11
專利名稱：一種基於不確定數據集的雙色反最鄰近查詢的方法及裝置的製作方法
技術領域：
本發明涉及時空資料庫(Spatio-kmporal DataBase, STDB)中基於位置服務 (Location-based Database, LBS)信息查詢的技術領域，具體地說是查詢點位置確定，被查詢點位置不確定時，求解查詢點的反最近鄰的方法。
背景技術：
時空資料庫在20世紀80年代末開始受到人們的重視，現已成為資料庫領域中備受關注的前沿方向。時空數據查詢作為時空資料庫基本操作，研究內容已經相當豐富，主要涉及最近鄰查詢(Nearest-Neighbor Queries)，範圍查詢(Range Queries)，連續查詢 (Continuous Queries)等等。反最近鄰查詢(Reverse Nearest-NeighborQueries)是最近鄰查詢的延伸，其計算結果是以給定點為最近鄰的數據結點。反最近鄰查詢(RNN)有廣泛的應用領域，比如企業決策、文獻管理、地理信息系統等等。目前反最近鄰查詢主要分為兩大類單色(monochromatic)反最近鄰查詢和雙色 (bichromatic)反最近鄰查詢。在單色反最近鄰查詢中，所有的查詢點和被查詢點屬於同一種類S。因此，一個數據對象r被認為是查詢對象q的反最近鄰，若且唯若數據集中任一對象P與q間的距離大於r與q的距離。即酬⑷-{reSjVpGS: dist(r,q) < dist{,%p)}。在雙
色最近鄰查詢中有A、B兩類點。其中查詢點屬於A類點，而被查詢點屬於B類點。一個數據對象r被認為是查詢對象q的反最近鄰，若且唯若B類對象中任一對象ρ與q之間的距離大於 r 與 q 之間的距離，即 RNN(q) = [r e 5 I Vp e .4 dist{r,q) < dist(r,p)}。雙色反最近鄰通常涉及到一個數據結構，名為Voronoi Cell (即VC，維絡諾單元)。VC是Voronoi Diagram的基本單元。給定點q的VC (即VC (q))是根據給定二維點集S建立的唯一凸多邊形。所有該二維空間中位於VC(q)內部的點與q的距離都小於點與 S中除q外其他任何點的距離。在時空資料庫中，常用的索引結構是R-Tree以及在其基礎上派生出的各種樹形結構。R-Tree是一種類似於B-Tree的高度平衡樹，實現完全動態索引，不需要人工定時更新。本發明用到的索引結構即為R-Tree。在人們享受各種位置服務的同時，個人位置信息洩露的隱私威脅也漸漸成為一個嚴重的問題，引起研究者們的注意。位置隱私指的是防止其他人以任何方式獲知對象過去、 現在的位置。為保護用戶位置隱私，用戶位置信息通常需要不同情況的空間匿名，使攻擊者不能夠獲得用戶的具體位置信息。用戶位置信息空間匿名的方法大致分為兩種，即離散匿名和連續匿名。離散匿名即用一個空間區域來表示用戶的真實的精確位置，在此區域中用戶在若干個點分別以不同概率出現，所有出現概率的和為1 ；連續匿名是指在匿名區域內每一個位置出現的概率相同。2009 年 Muhammad 在 TKDE 發表文章!Probabilistic ReverseNearest Neighbor Queries onUncertain Data中提出了基於不確定數據集的反最近鄰可能性查詢，該方法實現了離散匿名情況下的單色不確定反最近鄰查詢。文中形象的說明了不確定性RNN查詢的應用場景，而且提出了多種R-Tree (R型樹)剪枝策略。這項時空數據反最近鄰查詢和不確定數據集交叉領域的目前最先進的研究成果僅僅解決了單色RNN下離散匿名的場景問題， 並不能解決單色、雙色和離散、連續等場景下RNN查詢的問題。
發明內容
針對現有技術中的缺陷，本發明的目的是提供一種基於不確定數據集的雙色反最鄰近查詢的方法以及相應的裝置。根據本發明的一個方面，提供基於不確定數據集的雙色反最鄰近查詢的方法，包括步驟a.確定查詢對象的興趣範圍，其中，所述查詢對象出於第一類結點；b.將與所述興趣範圍有交集的匿名框確定為備選匿名框；c.根據備選匿名框生成結果集。根據本發明的另一個方面，還提供基於不確定數據集的雙色反最鄰近查詢的裝置，包括裝置第一確定裝置，其用於確定查詢對象的興趣範圍，其中，所述查詢對象出於第一類結點；第二確定裝置，其用於將與所述興趣範圍有交集的匿名框確定為備選匿名框； 第一生成裝置，其用於根據備選匿名框生成結果集。為了克服現有技術僅解決了單色RNN查詢在離散匿名中的應用，本發明提供被查詢點離散、連續匿名情況下雙色RNN查詢的方法。本發明解決其技術問題所採用的技術方案，是結合VC，根據被查詢對象匿名區域在VC中的部分稱為查詢點RNN的可能性(ρ )，來判斷被查詢區域是否是查詢點的RNN。本發明的有益效果是，能夠達到較高的查準率和時間效率，並且能夠靈活設置閾值P，來根據不同的可能性取得查詢結果。與背景技術相比，本發明有以下優點(1)、完成了雙色不確定性數據集上的RNN查詢；(2)、把匿名方式從離散拓展到了離散和連續兩種方式。
通過閱讀參照以下附圖對非限制性實施例所作的詳細描述，本發明的其它特徵、 目的和優點將會變得更明顯圖1示出根據本發明的第一實施例的，基於不確定數據集的雙色反最鄰近查詢的方法的流程圖；圖2示出根據本發明的第二實施例的，基於不確定數據集的雙色反最鄰近查詢的方法的流程圖；圖3示出根據本發明的第三實施例的，基於不確定數據集的雙色反最鄰近查詢的裝置的結構圖；圖4示出根據本發明的第三實施例的，基於不確定數據集的雙色反最鄰近查詢的方法的原理圖；以及圖5示出根據本發明的第三實施例的，基於不確定數據集的雙色反最鄰近查詢的方法的原理圖。
具體實施方式
參考圖1、圖2，本發明提供了一種基於不確定性數據集的雙色反向最近鄰查詢算法(Bichromatic Reverse Nearest-Neighbors queriesbased on Uncertain Dataset， B-RNNUD)。它基於不確定性數據集，將被查詢點做一定程度上的匿名，用以保護用戶信息， 並以查詢點q同類結點建立voronoi cell即VC(q)及其MBR，方便過濾被查詢對象的MBRi， 過濾後與VC有交集的MBRi將會被計算成為q的RNN的可能性pi，若P i大於既定閾值 P，則納入結果集，否則丟棄。該算法主要用於戰略決策系統等保護用戶位置隱私的前提下的反最近鄰查詢。圖1示出根據本發明的第一實施例的，基於不確定數據集的雙色反最鄰近查詢的方法的流程圖。具體地，在本實施例中，首先執行步驟S210，確定查詢對象的興趣範圍，其中，所述查詢對象出於第一類結點。然後執行步驟S211，將與所述興趣範圍有交集的匿名框確定為備選匿名框。最後執行步驟S212，根據備選匿名框生成結果集。圖2示出根據本發明的第二實施例的，基於不確定數據集的雙色反最鄰近查詢的方法的流程圖。具體地，在本實施例中，首先執行步驟S220，確定所述查詢對象的Voronoi Cell。然後執行步驟S221，根據所述Voronoi Cell確定所述興趣範圍。然後執行步驟S222， 遍歷第二類結點的R-Tree，查詢與所述興趣範圍有交集的匿名框。然後執行步驟S223，依次計算各個所述備選匿名框與所述Voronoi Cell相交部分面積與其總面積之比，並將結果記錄為第一比值。然後執行步驟S2M，判斷所述第一比值是否大於第一閾值。進一步地， 若所述步驟S2M的判斷結果是肯定的，即，則接下來進入步驟S225繼續執行；若所述步驟 S2M的判斷結果是否定的，S卩，則結束本流程。最後執行步驟S225，將與所述第一比值相對應的所述備選匿名框納入所述結果集。在本實施例的一個優選例中，所述步驟S220包括步驟「遍歷所述第一類結點的 R-Tree，查詢所述查詢對象的若干個最近鄰結點」、步驟「以所述查詢對象為起點，豎直向上為方向建立方向向量，沿逆時針方向旋轉，每掃描到一個所述查詢對象的最近鄰結點，就畫出所述查詢對象與最近鄰結點間的中垂線」、以及步驟「掃描一周在最後一個所述最近鄰結點和第一個所述最近鄰結點之間再掃描，確定所述Voronoi Cell」。在本實施例的另一個優選例中，所述步驟S221包括步驟「分別找出維絡諾單元所有頂點中縱坐標最小的點，縱坐標最大的點，橫坐標最小的點，橫坐標最大的點，分別設為 Hl,H2,ffl, W2 ；以經過Hl，H2並且平行於χ軸的兩條直線和經過Wl，W2並且平行於y軸的兩條直線圍成的矩形作為該維絡諾單元的最小邊界矩形，即MBR(VC(q)) 」。在本實施例的一個變化例中，所述步驟S223可以變化為步驟「依次計算各個所述備選匿名框與所述Voronoi Cell相交部分內部離散點成為RNN(q)的可能性之和，並將結果記錄為第一和值」，相應地，所述步驟S2M變化為步驟「判斷所述第一和值是否大於第二閾值」，所述步驟S225變化為步驟「將與所述第一和值相對應的所述備選匿名框納入所述結果集」。圖3示出根據本發明的第三實施例的，基於不確定數據集的雙色反最鄰近查詢的裝置的結構圖。具體地，在本實施例中，所述控制裝置4包括第一確定裝置41，其用於確定查詢對象的興趣範圍，其中，所述查詢對象出於第一類結點；第二確定裝置42，其用於將與所述興趣範圍有交集的匿名框確定為備選匿名框；第一生成裝置43，其用於根據備選匿名框生成結果集。
優選地，所述第一確定裝置41包括第三確定裝置411，其用於確定所述查詢對象的Voronoi Cell ；第四確定裝置412，其用於根據所述Voronoi Cell確定所述興趣範圍。優選地，所述第二確定裝置42包括第四處理裝置421，其用於遍歷第二類結點的 R-Tree，查詢與所述興趣範圍有交集的匿名框。優選地，所述第一生成裝置43包括第五處理裝置431，其用於依次計算各個所述備選匿名框與所述Voronoi Cell相交部分面積與其總面積之比，並將結果記錄為第一比值；第一判斷裝置432，其用於判斷各個所述第一比值是否大於第一閾值；第六處理裝置 433，其用於當所述第一比值大於第一閾值時，將與所述第一比值相對應的所述備選匿名框納入所述結果集。在本實施例的一個優選例中，所述第三確定裝置411包括第一處理裝置，其用於遍歷所述第一類結點的R-Tree，查詢所述查詢對象的若干個最近鄰結點；第二處理裝置， 其用於以所述查詢對象為起點，豎直向上為方向建立方向向量，沿逆時針方向旋轉，每掃描到一個所述查詢對象的最近鄰結點，就畫出所述查詢對象與最近鄰結點間的中垂線；第三處理裝置，其用於掃描一周在最後一個所述最近鄰結點和第一個所述最近鄰結點之間再掃描，確定所述Voronoi Cell。在本實施例的另一個優選例中，所述第四確定裝置412包括裝置的具體內容為 分別找出維絡諾單元所有頂點中縱坐標最小的點，縱坐標最大的點，橫坐標最小的點，橫坐標最大的點，分別設為Hl，H2，ffl, W2;以經過Hl，H2並且平行於χ軸的兩條直線和經過Wl，W2並且平行於y軸的兩條直線圍成的矩形作為該維絡諾單元的最小邊界矩形，即 MBR(VC(q))。在本實施例的一個變化例中，所述第五處理裝置431可以變化為第七處理裝置， 其用於依次計算各個所述備選匿名框與所述Voronoi Cell相交部分內部離散點成為 RNN(q)的可能性之和，並將結果記錄為第一和值；相應地，所述第一判斷裝置432可以變化為第二判斷裝置，其用於判斷各個所述第一和值是否大於第二閾值，所述第六處理裝置433 變化為第八處理裝置，其用於當所述第一和值大於第二閾值時，將與所述第一和值相對應的所述備選匿名框納入所述結果集。進一步地，圖4以及圖5共同示出根據本發明的第三實施例的，基於不確定數據集的雙色反最鄰近查詢的方法的原理圖。本領域技術人員理解，優選地，本發明解決其技術問題所採用的技術方案是一種基於不確定性數據集的反最近鄰查詢方法。在用戶數據適當二維匿名的情況下，查詢確定點q的RNN。利用VC(q)，得出興趣範圍MBR，然後查詢在此 MBR中的用戶匿名區域，計算候選區域與VC(q)的交集成為RNN(q)的可能性，以此來計算 RNN(q)。結合圖4、圖5所示實施例，其具體方法描述如下第一步遍歷索引A類結點的R型樹，查詢q的k個最近鄰(即距離q點最近的前 k 個 A 類點，nearest neighbors,簡稱 NN)；第二步以q為起點，豎直向上為方向建立方向向量，沿逆時針方向旋轉，每掃描到一個q的kNN(設為點pi)，就畫出q與pi間的中垂線。掃描一周在最後一個pn和第一個PO之間再掃描，確定最終的q點的維絡諾單元VC(q)，即圖4中11，12，13，14四條直線確定的一個四邊形；第三步計算q的維絡諾單元的最小邊界矩形MBR(VC(q))，即圖5中虛線矩形；
第四步遍歷B類對象的R型樹，查詢與MBR(VC (q))有交集的匿名框R0，. . .，Rm， 即圖5中的R0，...，R7;第五步依次計算R0，. . .，Rm與VC(q)相交部分面積與其總面積之比(連續匿名)，或相交部分內部離散點成為RNN (q)的可能性之和，記錄結果Pi』 ；第六步將ρ i』與之前設定的閾值P作對比，高於P的情況納入結果集，否則丟
棄，算法結束。以上對本發明的具體實施例進行了描述。需要理解的是，本發明並不局限於上述特定實施方式，本領域技術人員可以在權利要求的範圍內做出各種變形或修改，這並不影響本發明的實質內容。
權利要求
1.一種基於不確定數據集的雙色反最鄰近查詢的方法，其特徵在於a.確定查詢對象的興趣範圍，其中，所述查詢對象出於第一類結點；b.將與所述興趣範圍有交集的匿名框確定為備選匿名框；c.根據備選匿名框生成結果集。
2.根據權利要求1所述的方法，其特徵在於，所述步驟a包括如下步驟 al.確定所述查詢對象的維絡諾單元；a2.根據所述維絡諾單元確定所述興趣範圍。
3.根據權利要求2所述的方法，其特徵在於，所述步驟al包括如下步驟all.遍歷索引所述第一類結點的R型樹，查詢所述查詢對象的若干個最近鄰結點； al2.以所述查詢對象為起點，豎直向上為方向建立方向向量，沿逆時針方向旋轉，每掃描到一個所述查詢對象的最近鄰結點，就畫出所述查詢對象與最近鄰結點間的中垂線；al3.掃描一周在最後一個所述最近鄰結點和第一個所述最近鄰結點之間再掃描，確定所述維絡諾單元。
4.根據權利要求2或3所述的方法，其特徵在於，所述步驟a2包括如下步驟all'.分別找出維絡諾單元所有頂點中縱坐標最小的點，縱坐標最大的點，橫坐標最小的點，橫坐標最大的點，分別設為Hl，H2，Wl，W2 ；al2'.以經過H1，H2並且平行於χ軸的兩條直線和經過W1，W2並且平行於y軸的兩條直線圍成的矩形作為該維絡諾單元的最小邊界矩形，即MBR(VC(q))。
5.根據權利要求1至4中任一項所述的方法，其特徵在於，所述步驟b包括如下步驟 bl.遍歷第二類結點的R型樹，查詢與所述興趣範圍有交集的匿名框。
6.根據權利要求1至5所述的方法，其特徵在於，所述步驟c包括如下步驟cl.依次計算各個所述備選匿名框與所述維絡諾單元相交部分面積與其總面積之比， 並將結果記錄為第一比值；c2.判斷各個所述第一比值是否大於第一閾值；c3.若所述第一比值大於第一閾值，則將與所述第一比值相對應的所述備選匿名框納入所述結果集。
7.根據權利要求1至5所述的方法，其特徵在於，所述步驟c包括如下步驟cl'.依次計算各個所述備選匿名框與所述維絡諾單元相交部分內部離散點成為 RNN (q)的可能性之和，並將結果記錄為第一和值；c2'.判斷各個所述第一和值是否大於第二閾值；c3'.若所述第一和值大於第二閾值，則將與所述第一和值相對應的所述備選匿名框納入所述結果集。
8.一種基於不確定數據集的雙色反最鄰近查詢的裝置，其特徵在於，包括如下裝置 第一確定裝置，其用於確定查詢對象的興趣範圍，其中，所述查詢對象出於第一類結佔.^ \\\ 第二確定裝置，其用於將與所述興趣範圍有交集的匿名框確定為備選匿名框； 第一生成裝置，其用於根據備選匿名框生成結果集。
9.根據權利要求8所述的裝置，其特徵在於，所述第一確定裝置包括如下裝置 第三確定裝置，其用於確定所述查詢對象的維絡諾單元；第四確定裝置，其用於根據所述維絡諾單元確定所述興趣範圍。
10.根據權利要求9所述的裝置，其特徵在於，所述第三確定裝置包括如下裝置 第一處理裝置，其用於遍歷所述第一類結點的R型樹，查詢所述查詢對象的若干個最近鄰結點；第二處理裝置，其用於以所述查詢對象為起點，豎直向上為方向建立方向向量，沿逆時針方向旋轉，每掃描到一個所述查詢對象的最近鄰結點，就畫出所述查詢對象與最近鄰結點間的中垂線；第三處理裝置，其用於掃描一周在最後一個所述最近鄰結點和第一個所述最近鄰結點之間再掃描，確定所述維絡諾單元。
11.根據權利要求9或10所述的裝置，其特徵在於，所述第四確定裝置包括如下裝置 cll'.分別找出維絡諾單元所有頂點中縱坐標最小的點，縱坐標最大的點，橫坐標最小的點，橫坐標最大的點，分別設為Hl，H2，Wl，W2 ；cl2'.以經過H1，H2並且平行於χ軸的兩條直線和經過W1，W2並且平行於y軸的兩條直線圍成的矩形作為該維絡諾單元的最小邊界矩形，即MBR(VC(q))。
12.根據權利要求8至11中任一項所述的裝置，其特徵在於，所述第二確定裝置包括如下裝置第四處理裝置，其用於遍歷第二類結點的R型樹，查詢與所述興趣範圍有交集的匿名框。
13.根據權利要求8至12所述的裝置，其特徵在於，所述第一生成裝置包括如下裝置 第五處理裝置，其用於依次計算各個所述備選匿名框與所述維絡諾單元相交部分面積與其總面積之比，並將結果記錄為第一比值；第一判斷裝置，其用於判斷各個所述第一比值是否大於第一閾值； 第六處理裝置，其用於當所述第一比值大於第一閾值時，將與所述第一比值相對應的所述備選匿名框納入所述結果集。
14.根據權利要求8至12所述的裝置，其特徵在於，所述第一生成裝置包括如下裝置 第七處理裝置，其用於依次計算各個所述備選匿名框與所述維絡諾單元相交部分內部離散點成為RNN (q)的可能性之和，並將結果記錄為第一和值；第二判斷裝置，其用於判斷各個所述第一和值是否大於第二閾值； 第八處理裝置，其用於當所述第一和值大於第二閾值時，將與所述第一和值相對應的所述備選匿名框納入所述結果集。
全文摘要
本發明提供基於不確定數據集的雙色反最鄰近查詢的方法，包括步驟a.確定查詢對象的興趣範圍，其中，所述查詢對象出於第一類結點；b.將與所述興趣範圍有交集的匿名框確定為備選匿名框；c.根據備選匿名框生成結果集。還提供相應的裝置。本發明提供的基於不確定性數據集的反最近鄰查詢方法，在用戶數據適當二維匿名的情況下，查詢確定點q的RNN。利用VC(q)，得出興趣範圍MBR，然後查詢在此MBR中的用戶匿名區域，計算候選區域與V℃(q)的交集成為RNN(q)的可能性，以此來計算RNN(q)。本發明完成了雙色不確定性數據集上的RNN查詢；把匿名方式從離散拓展到了離散和連續兩種方式。
文檔編號G06F17/30GK102541922SQ20101061384
公開日2012年7月4日 申請日期2010年12月24日 優先權日2010年12月24日
發明者呂釗, 吳琴, 周凌琛, 林欣, 陳超, 陳鵬 申請人:華東師範大學