本文選題：時空查詢　切入點：時空索引　出處：《中國地質(zhì)大學》2014年博士論文　論文類型：學位論文

【摘要】：現(xiàn)實世界是一個永恒變化的四維時空,每時每刻都在持續(xù)不斷地產(chǎn)生著大量的時空數(shù)據(jù)。時空數(shù)據(jù)可以幫助人類了解歷史、掌握現(xiàn)在、預(yù)測將來,有助于提高人類對四維時空中各種存在與狀態(tài)演變的洞察、感知與預(yù)測能力。如何有效地存儲和管理這些大規(guī)模的時空數(shù)據(jù)集,是以分布式協(xié)同、高性能計算、時空數(shù)據(jù)流處理為核心的新一代空間信息系統(tǒng)必須解決的關(guān)鍵技術(shù)問題之一。新一代空間信息系統(tǒng)中的四維時空數(shù)據(jù)庫問題剛剛引起關(guān)注,各種研究也剛剛開始,海量時空數(shù)據(jù)管理中還存在著諸如多層次時空緩存、四維時空數(shù)據(jù)快速檢索、調(diào)度等技術(shù)瓶頸問題,而高效時空索引是這些問題有效解決的基礎(chǔ)。在當前多核計算機已經(jīng)成為常規(guī)計算設(shè)備的情況下,時空數(shù)據(jù)庫領(lǐng)域亟需解決的關(guān)鍵科學技術(shù)問題之一,是如何在分布式多核計算環(huán)境中構(gòu)建合理的分布式時空索引架構(gòu)、降低時空索引的并發(fā)控制成本。 目前,時空索引的研究大多針對的是集中式索引,分布式時空索引和并行時空索引兩個方面的研究都較少,并且是作為兩個獨立的內(nèi)容進行研究的。未見直接針對分布式并行時空索引的一體化研究。為降低時空索引的并發(fā)控制成本,現(xiàn)有的研究成果多專注于并發(fā)控制算法本身,而缺乏對時空索引結(jié)構(gòu)本身的可并行化進行研究。常用的樹型時空索引的層次結(jié)構(gòu)不具并行性,不利于并行算法的實現(xiàn),存在并行計算瓶頸。在頻繁更新的時空數(shù)據(jù)庫中,并行時空索引的一體化與時空索引結(jié)構(gòu)并行化缺失的問題,嚴重阻礙了大數(shù)據(jù)時代時空數(shù)據(jù)庫中分布式并行緩存機制、并行預(yù)調(diào)度與調(diào)度機制、大規(guī)模時空分析等一系列問題的有效解決,成為該領(lǐng)域亟需解決的重大難題。因此,亟需設(shè)計具有可并行化結(jié)構(gòu)的時空索引方法,并對時空索引的分布式和并行化進行一體化研究。 為此,本文以國家高技術(shù)研究發(fā)展計劃(863計劃)“十二五”主題項目課題“實時GIS關(guān)鍵技術(shù)及軟件平臺”(2012AA121401)、“十一五”重點項目課題“三維空間數(shù)據(jù)管理系統(tǒng)與分析組件研發(fā)”(2008AA121602)和國家自然科學基金項目“地上下一體化三維動態(tài)廣義表空間索引方法”(41101368)相關(guān)研究成果為基礎(chǔ),對時空索引的分布式和并行化進行了一體化研究,提出了適合分布式并行計算環(huán)境的分布式并行時空索引DPSI多層次理論架構(gòu)；對時空索引結(jié)構(gòu)本身并行化機制進行了研究,提出了具有可并行化結(jié)構(gòu)、適用于DPSI局部索引的基于間隔關(guān)系算子的并行時空索引IPSI方法,突破了高維度下(本文主要針對四維時空)樹形索引的層次結(jié)構(gòu)對并行算法實現(xiàn)的局限性,在細化時空索引并行粒度的同時降低了并發(fā)控制開銷。設(shè)計實現(xiàn)了主從模式下的分布式并行時空索引MSDPSI和對等模式下的分布式并行時空索引PPDPSI。實驗表明,本文研究成果有效提升了分布式并行計算環(huán)境下并行時空索引性能。論文的主要研究工作如下：(1)綜述并剖析了與分布式并行時空索引技術(shù)相關(guān)的前人研究工作。本文首先探討了分布式并行時空索引的研究目標與意義,梳理了分布式并行時空索引的技術(shù)脈絡(luò),然后按其技術(shù)發(fā)展脈絡(luò),分別評述了集中式時空數(shù)據(jù)索引、并行時空數(shù)據(jù)索引和分布式時空數(shù)據(jù)索引等三類時空索引的發(fā)展現(xiàn)狀及存在問題。針對所存在的問題,提出了本文的主要研究內(nèi)容、研究方法和技術(shù)路線。同時,分析、討論了與時空索引相關(guān)的地學時空及其表達方法、時空對象的主要特征、時空查詢的分類等相關(guān)因素。(2)提出了多層次分布式并行時空索引架構(gòu)(DPSI),設(shè)計實現(xiàn)了主從模式和對等模式下的分布式并行時空索引方法。提出了DPSI的時空數(shù)據(jù)劃分方法以及基于此劃分的DPSI的形式化描述。DPSI的全局架構(gòu)支持主從和對等兩種模式。設(shè)計實現(xiàn)了主從模式下的DPSI (MSDPSI)和對等模式下的DPSI (PPDPSI)的查詢算法和更新維護算法。實驗表明,MSDPSI和PPDPSI都具備良好的分布式時空查詢性能。兩者比較而言,MSDPSI比PPDPSI具有更好的更新維護性能。但是,MSDPSI的網(wǎng)絡(luò)自治性和可擴展性弱于PPDPSI。隨著數(shù)據(jù)規(guī)模的增大,MSDPSI的主控服務(wù)器存在性能瓶頸。(3)提出了基于間隔關(guān)系算子的并行時空索引(IPSI)方法。對IPSI中的時空數(shù)據(jù)與間隔數(shù)據(jù)的表達方法進行了理論、系統(tǒng)研究,給出了時空數(shù)據(jù)到間隔數(shù)據(jù)的轉(zhuǎn)換關(guān)系�；谠撧D(zhuǎn)換關(guān)系,提出了時空查詢到可并行的間隔關(guān)系算子的轉(zhuǎn)換方法,實現(xiàn)了基于間隔關(guān)系算子的時空查詢表達,為基于間隔關(guān)系算子的并行時空索引和并行時空查詢奠定了理論基礎(chǔ)。研究提出了IPSI的算法原理和數(shù)據(jù)結(jié)構(gòu),設(shè)計實現(xiàn)了IPSI的更新算法和查詢算法。實驗結(jié)果表明,在多核并行計算環(huán)境下,IPSI具有優(yōu)良的查詢、更新性能。(4)基于DPSI設(shè)計開發(fā)了一個分布式并行時空數(shù)據(jù)引擎(DPSDE)和一個時空數(shù)據(jù)庫管理系統(tǒng)的原型系統(tǒng)。提出了分布式并行時空數(shù)據(jù)引擎(DPSDE)的系統(tǒng)架構(gòu),討論了該架構(gòu)中緩存、索引及調(diào)度策略之間的關(guān)系,設(shè)計并實現(xiàn)了基于該架構(gòu)的時空數(shù)據(jù)調(diào)度策略。基于DPSDE設(shè)計開發(fā)了一個時空數(shù)據(jù)庫管理原型系統(tǒng)。該原型系統(tǒng)已經(jīng)在多個城市級別的時空數(shù)據(jù)管理中使用,證明了DPSI的有效性和實用性。 分布式并行時空索引主要有兩個突破方向,一個是采用先進高效的并發(fā)控制技術(shù)實現(xiàn)索引的分布式并行特征,另一個就是盡量使索引本身成為可分布式并行結(jié)構(gòu),從而以盡可能少的并發(fā)控制成本實現(xiàn)盡可能多的分布式并行特征。本文的研究工作主要集中在第二個方面。在上述研究工作中,主要有以下創(chuàng)新性成果：(1)提出了多層次自適應(yīng)分布式并行時空索引DPSI架構(gòu)及算法 針對不同的網(wǎng)絡(luò)環(huán)境和并行計算環(huán)境大規(guī)模時空數(shù)據(jù)管理難點問題,設(shè)計提出了多層次的自適應(yīng)分布式并行時空索引DPSI架構(gòu)。該架構(gòu)將網(wǎng)絡(luò)計算資源分為全局網(wǎng)絡(luò)、網(wǎng)絡(luò)節(jié)點、CPU、內(nèi)核等多個層次。以并行間隔關(guān)系算子為底層構(gòu)建的DPSI架構(gòu),具備高效調(diào)度管理上至全局網(wǎng)絡(luò)下至并行計算內(nèi)核的能力,可以根據(jù)網(wǎng)絡(luò)節(jié)點的并行計算能力、承載數(shù)據(jù)量等信息自適應(yīng)地調(diào)整網(wǎng)絡(luò)節(jié)點動態(tài)選擇,充分發(fā)揮了分布式環(huán)境下單個節(jié)點的并行計算能力,提高了分布式并行時空索引整體性能。針對現(xiàn)有分布式時空索引大多只顧及到了網(wǎng)絡(luò)分布式特征,而往往忽略了網(wǎng)絡(luò)節(jié)點的并行計算能力的充分利用問題。在DPSI架構(gòu)下,進行了分布式并行一體化研究,提出了主從分布式并行時空索引MSDPSI方法和對等分布式并行時空索引PPDPSI方法。這兩種方法針對不同網(wǎng)絡(luò)環(huán)境,采取主從結(jié)構(gòu)和對等結(jié)構(gòu)分別構(gòu)建分布式全局索引,局部索引則采用IPSI方法,具備節(jié)點動態(tài)管理能力,將網(wǎng)絡(luò)的分布性與節(jié)點的并行計算能力有機整合,增強了分布式并行時空索引的自治性和可擴展性,提高了分布式并行時空索引的整體性能。(2)提出了基于間隔關(guān)系算子的并行時空索引IPSI方法 針對多核并行計算環(huán)境下樹形時空索引對細粒度并行計算的限制,提出了具有并行化結(jié)構(gòu)的基于間隔關(guān)系算子的并行時空索引IPSI方法。IPSI的時空查詢與并行間隔關(guān)系算子轉(zhuǎn)換方法將時空數(shù)據(jù)查詢轉(zhuǎn)化為可并行的間隔關(guān)系算子操作,然后將間隔數(shù)據(jù)集映射到可并行的不同維度的間隔點集平面。IPSI采用統(tǒng)一的二維平面元素求交運算實現(xiàn)各種間隔關(guān)系算子,從而在多核計算環(huán)境下以統(tǒng)一接口實現(xiàn)多種時空查詢。IPSI根據(jù)間隔點集平面遞歸三角化方法構(gòu)建不同維度的間隔數(shù)據(jù)虛擬二叉樹索引。該二叉樹只記錄葉子結(jié)點,減少了節(jié)點訪問次數(shù),提高了二叉樹索引查詢性能。同時,由于間隔數(shù)據(jù)的結(jié)束值恒大于或等于其開始值,間隔點集平面只需要考慮上三角區(qū)域而不用考慮整個平面范圍,這也大大縮減了平面元素求交計算量。基于多棵虛擬二叉樹構(gòu)建的IPSI,有效解決了時空數(shù)據(jù)耦合度高、可并行性差的問題,可充分發(fā)揮了多核并行計算優(yōu)勢,提高了并行時空索引性能。 本文的研究成果為分布式并行計算環(huán)境下的海量三維、四維或更高維的時空數(shù)據(jù)的快速檢索提供了可行、通用、高效的并行時空索引解決方案。后續(xù)研究將專注于分布式并行計算環(huán)境下時空索引的代價模型研究和時空數(shù)據(jù)安全問題研究。
[Abstract]:......
【學位授予單位】：中國地質(zhì)大學
【學位級別】：博士
【學位授予年份】：2014
【分類號】：P208

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 何珍文;鄭祖芳;劉剛;吳沖龍;;動態(tài)廣義表空間索引方法[J];地理與地理信息科學;2011年05期

2 鄭文武;李先緒;黃執(zhí)勤;;云計算中的并行計算技術(shù)分析[J];電信科學;2011年12期

3 劉義;陳犖;景寧;熊偉;;基于R-樹索引的Map-Reduce空間連接聚集操作[J];國防科技大學學報;2013年01期

4 張，

本文編號：1633188