仇阿根

中國測繪科學(xué)研究院，北京 100830

基于分布式內(nèi)存計算的空間數(shù)據(jù)近似查詢處理方法

仇阿根

中國測繪科學(xué)研究院，北京 100830

地理數(shù)據(jù)交互式可視化與空間分析等是地理信息系統(tǒng)(Geographic Information System,GIS)應(yīng)用的重要功能，而現(xiàn)有的地理空間數(shù)據(jù)庫與地理數(shù)據(jù)服務(wù)標準難以滿足實時數(shù)據(jù)可視化及空間分析的要求。根源在于空間數(shù)據(jù)庫中地理要素的查詢結(jié)果是精確、唯一的；查詢時間和數(shù)據(jù)量只與要素本身相關(guān)；查詢時地理要素無法根據(jù)條件動態(tài)生成。而在實際應(yīng)用中，地理要素可以是近似的、變化的；查詢時間和數(shù)據(jù)量可以作為查詢約束條件；地理要素可以根據(jù)查詢條件動態(tài)生成。

為此，本文提出以空間近似查詢結(jié)果表達地理要素，即通過頂點采樣實時生成要素并報告近似誤差，實現(xiàn)查詢時間和數(shù)據(jù)量的靈活控制?；诖耍岢隽撕Ａ靠臻g數(shù)據(jù)集的多分辨率表達模型，設(shè)計了以分布式內(nèi)存計算、頂點樹型層次結(jié)構(gòu)、加權(quán)廣度遍歷算法為基礎(chǔ)的空間近似查詢處理方法，實現(xiàn)了基于關(guān)系數(shù)據(jù)庫的空間近似查詢引擎，形成了基于空間近似查詢的網(wǎng)絡(luò)GIS架構(gòu)，解決了網(wǎng)絡(luò)GIS的交互式可視化與空間分析的功能與性能問題。具體研究內(nèi)容如下：

(1) 基于分布式內(nèi)存計算的空間近似查詢理論。總結(jié)了近似查詢與分布式計算的基礎(chǔ)理論，根據(jù)地理要素的特點、地理數(shù)據(jù)交互式可視化與空間分析的需求，針對空間查詢數(shù)據(jù)量難以有效控制的問題，定義了面向交互式可視化的空間近似查詢，提出了多分辨率表達模型。通過遞歸細分、數(shù)據(jù)采樣、應(yīng)用處理、誤差計算等步驟建立表達模型，并將計算密集型任務(wù)分布化，提供了誤差與數(shù)據(jù)量可控的空間近似查詢基礎(chǔ)算法與數(shù)據(jù)結(jié)構(gòu)。

(2) 地理要素近似誤差計算與頂點層次結(jié)構(gòu)構(gòu)建方法?；谶f歸細分與誤差計算的多分辨率表達模型，將地理要素數(shù)據(jù)分布式內(nèi)存計算處理，建立頂點樹型層次結(jié)構(gòu)，形成了地理要素的多分辨率表達。面向數(shù)據(jù)可視化，將地理要素數(shù)據(jù)遞歸細分系數(shù)設(shè)為2，提出了地理要素頂點層次結(jié)構(gòu)的構(gòu)建方法與存儲模型，設(shè)計實現(xiàn)了顧及誤差條件的空間索引等。

(3) 地理要素近似查詢算法。以加權(quán)廣度優(yōu)先算法為基礎(chǔ)，提出了時間/數(shù)據(jù)量約束、誤差約束的地理要素窗口近似查詢處理算法，包括時間/數(shù)據(jù)量約束條件下樹型層次結(jié)構(gòu)的加權(quán)廣度優(yōu)先遍歷，在查詢過程中使用近似查詢約束條件與空間范圍約束條件，進行聯(lián)合剪枝以提高效率的方法；在關(guān)系模型的基礎(chǔ)上，研究查詢條件與空間連接的特點運用多維索引以提高效率的方法。

(4) 地理要素頂點層次結(jié)構(gòu)動態(tài)更新算法。根據(jù)地理要素連續(xù)更新的特點，提出了基于最小化代價函數(shù)的頂點層次更新算法。以關(guān)系模型下頂點層次結(jié)構(gòu)為基礎(chǔ)，研究代價最小的頂點層次結(jié)構(gòu)局部更新方法，分析頂點序列的插入、刪除、修改等操作的計算復(fù)雜度及I/O復(fù)雜度，研究不同的頂點層次結(jié)構(gòu)構(gòu)建參數(shù)對于動態(tài)化更新算法的影響。

(5) 海岸線數(shù)據(jù)實證研究。提出了基于空間近似查詢引擎的網(wǎng)絡(luò)GIS架構(gòu)，開發(fā)了地理數(shù)據(jù)交互式可視化原型系統(tǒng)。針對OpenStreetMap海岸線數(shù)據(jù)，建立了海岸線數(shù)據(jù)的頂點層次化數(shù)據(jù)庫，實現(xiàn)了地理要素的交互式可視化，并對試驗結(jié)果進行了對比分析，驗證了網(wǎng)絡(luò)GIS架構(gòu)的可行性及空間近似查詢處理方法的實用性。

In-memory Distributed Computing Based Approximate Query Processing on Spatial Data

QIU A’gen

Chinese Academy of Surveying and Mapping，Beijing 100830，China

his doctoral degree from Wuhan University on June 2017，majors in government geographic information services and geospatial big data technologies.

仇阿根.基于分布式內(nèi)存計算的空間數(shù)據(jù)近似查詢處理方法[J].測繪學(xué)報，2017,46(12)：2044.

10.11947/j.AGCS.2017.20170602.

QIU A’gen.In-memory Distributed Computing Based Approximate Query Processing on Spatial Data[J]. Acta Geodaetica et Cartographica Sinica,2017,46(12):2044. DOI:10.11947/j.AGCS.2017.20170602.

P208

D

1001-1595(2017)12-2044-01

測繪地理信息公益性行業(yè)科研專項(201512032)；測繪地理信息公益性行業(yè)科研專項(201512027)；中國測繪科學(xué)研究院基本科研業(yè)務(wù)費(7771614)；國家重點研發(fā)計劃(2016YFC0803108)

2017-10-26

仇阿根(1976—)，男，2017年6月畢業(yè)于武漢大學(xué)，獲工學(xué)博士學(xué)位(指導(dǎo)教師：劉紀平研究員)，研究方向為政府地理信息服務(wù)與地理空間大數(shù)據(jù)技術(shù)。

E-mail：qiuag@casm.ac.cn