[發明專利]一種Voronoi Diagram與虛擬網格結合的高效空間最近鄰查詢方法

有效

• 申請號: 201310470050.1
• 申請日: 2013-10-10
• 公開（公告）號: CN103559209A
• 公開（公告）日: 2014-02-05
• 發明（設計）人: 張重生
• 申請（專利權）人: 河南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 鄭州聯科專利事務所(普通合伙) 41104
• 代理人: 劉建芳;李伊寧

技術領域

本發明涉及一種最近鄰查詢方法，尤其涉及一種使用Voronoi?Diagram與虛擬網格結合的索引結構的高效空間最近鄰查詢方法。?

背景技術

近年來，隨著智能手機的普及，人們越來越多地使用手機進行定位、查找、瀏覽和分享信息；越來越多的設施如餐館、商店、電影院等的地理位置可以利用手機中的電子地圖來獲取。這種面向智能手機用戶的基于地理位置信息的服務已經被人們廣泛接受。隨著信息技術的不斷發展，這類基于地理位置信息的應用和服務也會越來越多。?

在這些應用和服務中，較為常見的基于地理位置信息的服務是搜索用戶當前位置附近的、滿足用戶所定義的關鍵詞的設施。在這類應用中，如何高效處理用戶當前地理位置的空間查詢，即空間關鍵詞查詢，是一項重要的研究課題。由于大量用戶通過移動終端在同一時間發起查詢，并且期望在很短的時間內得到答案，因此，并發查詢量大、查詢實時性要求高是當前基于地理位置信息的服務應用面臨的主要挑戰。?

如何提高空間最近鄰的查詢效率，是空間關鍵詞查詢和很多基于地理位置信息的服務應用中面臨的一個基礎且十分重要的關鍵問題。?在查找查詢位置的空間最近鄰時，現有的方法通常都借助于R-Tree類型的索引結構。而R-Tree類型的索引是基于磁盤的數據結構，使用R-Tree搜索查詢點在空間中的鄰域的時間復雜度是O(log?N)，其中N為數據點的總數，需要花費大量的查詢時間；并且，找到查詢點在空間中的鄰域之后，現有的方法必須查看所有與該鄰域相交的劃分區域即最小邊界矩形中的點，以從中找出查詢點的空間最近鄰，這樣又進一步增加了計算的開銷。?

發明內容

本發明的目的是提供一種Voronoi?Diagram與虛擬網格結合的高效空間最近鄰查詢方法，適用于大規模均勻分布的二維數據集，能夠將空間最近鄰查詢的時間復雜度從O(log?N)降低到O(1),提高空間最近鄰查詢的效率。?

本發明采用下述技術方案：?

一種Voronoi?Diagram與虛擬網格結合的高效空間最近鄰查詢方法，包括以下步驟：?

A:使用Voronoi?Diagram劃分二維空間中的數據點，形成N個Voronoi?Cell，N為數據點個數，每個Voronoi?Cell為一個凸多邊形且僅包含1個數據點；?

B:使用虛擬網格將二維空間劃分為若干個等大的正方形網格單元，確定網格單元的邊長，并對虛擬網格進行編號；?

C:設計計算虛擬網格單元和Voronoi?Cell之間的對應關系的方法，并將該對應關系存儲在一個哈希表中；?

D:計算查詢點位置所在的網格單元，并確定查詢點位置所對應的網格單元的編號；?

E:根據步驟D中計算出的網格單元編號，在步驟C中所建立的存儲網格單元與Voronoi?Cell對應關系的哈希表中，查找查詢點位置所在的網格單元所對應的Voronoi?Cell，并從中計算選擇距離查詢點位置最近的數據點返回給用戶。?

所述的步驟B包括以下步驟：?

B1:使用虛擬網格將二維空間劃分為若干個等大的正方形網格單元，通過公式（1）確定網格單元的邊長，其中，l為網格單元邊長，d為空間中所有兩點之間距離的最小值，ξ=10^-9；?

B2:令R為數據集中的所有數據點所構成的最小邊界矩形，以R的左下角的頂點(x₀,y₀)為出發點，建立虛擬網格，并從坐標(x₀,y₀)所在的網格單元開始，從左到右、自下而上遞增地對網格單元進行編號；計算坐標點(x,y)所在的網格單元編號的公式為：?