[發明專利]一種空間數據庫中分組反向輪廓查詢方法

有效

• 申請號: 201410007699.4
• 申請日: 2014-01-07
• 公開（公告）號: CN103778198B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: 高云君;柳晴;苗曉曄;陳璐;趙靖文;秦旭
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天正專利事務所有限公司33201
• 代理人: 王兵,黃美娟

1.一種空間數據庫中分組反向輪廓查詢方法：其特征在于該方法的步驟如下：

步驟（1）：根據分組反向輪廓查詢本身的特性以及用戶的需求選用一個合適的數據庫管理系統；

步驟（2）：開發一個空間數據庫引擎，能與步驟1）中選用的數據庫管理系統平臺交互，并選用空間數據庫索引技術；

步驟（3）：開發一個用于分組反向輪廓查詢的分組引擎；

步驟（4）：在步驟（2）中構建的空間數據庫和步驟（3）中構建的分組引擎的基礎上實現各組全局輪廓計算引擎，包括第一層和第二層全局輪廓計算；

步驟（5）：開發一個全局輪廓比較引擎，對步驟（4）中得到的結果進行驗證；

步驟（6）：對步驟（5）中的結果進行分組，以得到最終的查詢結果。

2.根據權利要求1所述的一種空間數據庫中分組反向輪廓查詢方法，其特征在于：所述的步驟（1）中選用支持基本的SQL查詢的數據庫管理系統平臺。

3.根據權利要求1所述的一種空間數據庫中分組反向輪廓查詢方法，其特征在于：所述的步驟（2）中的空間數據庫引擎是構建在應用層和數據庫層之間的中間件，所述的中間件與步驟（1）中選用的數據庫管理系統相互配合，接受上層查詢引擎的命令并轉化為SQL語句在數據庫管理系統中運行，空間數據庫索引一般選用R樹。

4.根據權利要求1所述的一種空間數據庫中分組反向輪廓查詢方法，其特征在于：所述的步驟（3）中的分組引擎根據對象原有的屬性對其進行分組，需考慮兩種情況：

3.1）該結點是中間索引結點，不做任何操作，因為中間結點所包含的對象可能來自不同組；

3.2）該結點是數據索引結點，那么將其分到相應的組中。

5.根據權利要求1所述的一種空間數據庫中分組反向輪廓查詢方法，其特征在于：所述的步驟（4）中計算各組全局輪廓的方法如下：

4.1）初始化一個最小堆，并將根結點放入堆，該最小堆根據R樹索引結點到查詢點的最小距離進行排序；初始化兩個對象集合，一個用來保存第一層全局輪廓，另外一個用來保存第二層全局輪廓；

4.2）如果最小堆為空，則過濾算法結束，返回兩個對象集合，即第一層和第二層全局輪廓；否則取出堆頂元素；

4.3）計算取出的堆頂元素被該組當前已經找到的第一層和第二層全局輪廓點所全局控制的次數；對于R樹索引結點被全局控制的次數，需考慮兩種情況：

a）該結點是中間索引結點，這種狀況下根據其被全局控制的次數分為兩種情況：

i）該中間結點最多只被一個該組第一層全局輪廓點所全局控制，那么將其索引孩子結點都加入到最小堆中，并跳到4.2）；

ii）該中間結點被多個該組第一層全局輪廓點所全局控制，那么對于其孩子結點不做任何操作，并跳到4.2）；

b）該結點是數據索引結點，這種狀況下根據其被全局控制的次數分為三種情況：

i）該數據結點沒有被任何一個當前已找到的該組第一層全局輪廓點所全局控制，那么將該數據索引結點加入到第一層全局輪廓結果列表中并跳到4.2）；

ii）該數據結點被一個當前已找到的該組第一層全局輪廓點和第二層全局輪廓點所全局控制，那么將該數據索引結點加入到第二層全局輪廓結果列表中并跳到4.2）；

iii）該數據結點被多個當前已找到的該組第一層和第二層全局輪廓點所全局控制，那么對于該數據索引結點不做任何操作，并跳到4.2）。

6.根據權利要求1所述的一種空間數據庫中分組反向輪廓查詢方法，其特征在于：所述的步驟（5）中全局輪廓比較方法如下：

5.1）初始化一個對象集合，用來保存最終結果；

5.2）取出一個第一層全局輪廓點，計算出該點的查詢窗口，以進行下一步精煉；該查詢窗口的中心點是相應的第一層全局輪廓點，查詢點q則作為該查詢窗口的一個頂點；如果所有組的第一層全局輪廓都已經精煉完，則算法結束；否則，繼續操作5.3）；

5.3）遍歷與5.2）中取出的第一層全局輪廓點同一組的第一層全局輪廓點，如果該查詢窗口包含其它該組第一層全局輪廓點，那么該點不是最終結果并跳轉到5.2）；

5.4）遍歷與5.2）中取出的第一層全局輪廓點同一組的第二層全局輪廓點，如果該查詢窗口包含其它該組第二層全局輪廓點，那么該點不是最終結果；否則該點是最終結果，加入到最終結果對象集合；并跳轉到5.2）。

7.根據權利要求1所述的一種空間數據庫中分組反向輪廓查詢方法，其特征在于：所述的步驟（6）中對步驟（5）中得到的結果根據其所在組進行整理，以得到每一組的反向輪廓。