[發明專利]一種基于不確定數據集的雙色反最鄰近查詢的方法及裝置

有效

• 申請號: 201010613841.1
• 申請日: 2010-12-24
• 公開（公告）號: CN102541922A
• 公開（公告）日: 2012-07-04
• 發明（設計）人: 林欣;周凌琛;吳琴;呂釗;陳鵬;陳超
• 申請（專利權）人: 華東師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 隆天國際知識產權代理有限公司 72003
• 代理人: 吳世華;馮志云

技術領域

本發明涉及時空數據庫(Spatio-Temporal?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的距離。即：?在雙色最近鄰查詢中有A、B兩類點。其中查詢點屬于A類點，而被查詢點屬于B類點。一個數據對象r被認為是查詢對象q的反最近鄰，當且僅當B類對象中任一對象p與q之間的距離大于r與q之間的距離，即?

雙色反最近鄰通常涉及到一個數據結構，名為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查詢的方法。?