仇阿根

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

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

仇阿根

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

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

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

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

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

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

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

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

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)存計(jì)算的空間數(shù)據(jù)近似查詢處理方法[J].測(cè)繪學(xué)報(bào)，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

測(cè)繪地理信息公益性行業(yè)科研專項(xiàng)(201512032)；測(cè)繪地理信息公益性行業(yè)科研專項(xiàng)(201512027)；中國(guó)測(cè)繪科學(xué)研究院基本科研業(yè)務(wù)費(fèi)(7771614)；國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFC0803108)

2017-10-26

仇阿根(1976—)，男，2017年6月畢業(yè)于武漢大學(xué)，獲工學(xué)博士學(xué)位(指導(dǎo)教師：劉紀(jì)平研究員)，研究方向?yàn)檎乩硇畔⒎?wù)與地理空間大數(shù)據(jù)技術(shù)。

E-mail：qiuag@casm.ac.cn