[發明專利]一種適用于高維散亂點云的索引查詢方法

在審

• 申請號: 201410301833.1
• 申請日: 2014-06-27
• 公開（公告）號: CN104050283A
• 公開（公告）日: 2014-09-17
• 發明（設計）人: 劉仁義;張豐;杜震洪;陳明;宣偉浩;郭綠奕
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 張法高

1.一種適用于高維散亂點云的索引查詢方法，其特征在于包括如下步驟：

1）根據給定的n維包含m個點的散亂點云數據構建點集P＝{p₁,?p₂,?...?,?p_m}，點集中任意一點p_i的坐標為(a_i1,?a_i2,?...?,?a_in)，存于邏輯主節點；

2）一個邏輯主節點配套n個邏輯子節點，邏輯主節點將點集P中每一個點p₁,?p₂,?...?,?p_m的id及其第j維坐標信息(a_1j,?a_2j,?...?,?a_mj)分別發送至編號為j的邏輯子節點，各邏輯子節點接收后根據各點第j維坐標的大小順序建立B⁺樹索引，其中j＝1,?2,?...?,?n；

3）對于n維查詢區域R＝((s₁,?t₁),?(s₂,?t₂),?...?,?(s_n,?t_n))，邏輯主節點將其在第j維上的投影(s_j,?t_j)分別發送至編號為j的邏輯子節點，邏輯子節點接收后基于之前創建的B⁺樹索引查找位于范圍(s_j,?t_j)之內的點，并將點的id返回給邏輯主節點；

4）邏輯主節點計算所有邏輯子節點返回的點id的交集，該交集即為高維散亂點云針對范圍R的查詢結果。

2.根據權利要求1所述的一種適用于高維散亂點云的索引查詢方法，其特征在于步驟2）、步驟3）和步驟4）所述的n個邏輯子節點在物理上可部署于數量少于n個的機器上，即一臺機器可部署多個邏輯子節點程序。

3.根據權利要求1所述的一種適用于高維散亂點云的索引查詢方法，其特征在于步驟3）所述邏輯子節點查找位于范圍(s_j,?t_j)之內點的方法為：獲取關鍵字s_j在B+樹索引中的位置，再順著連接B+樹葉子節點的雙向鏈表向右掃描，直到關鍵字大于t_j為止，掃描所及的葉子節點對應位于范圍(s_j,?t_j)之內的點。

4.根據權利要求1所述的一種適用于高維散亂點云的索引查詢方法，其特征在于步驟4）所述邏輯主節點計算n個邏輯子節點返回點id交集的方法為：獲取返回點個數最少的邏輯子節點返回的點id集合K，對于其中的每一個點id，判斷它是否也在其它邏輯子節點返回的點id集合中出現；只要有一個邏輯子節點返回的點id集合不包含這個點id，就將它從K中刪除，繼續判斷K中下一個點id；K中每一個點id都經過如此判斷之后，最終剩下的點id即為n個邏輯子節點返回點id的交集。