[發(fā)明專利]一種適應(yīng)顯示導(dǎo)向型可視化分析的快速的空間索引方法

有效

• 申請?zhí)枺?/td>: 202110647685.9
• 申請日: 2021-06-10
• 公開（公告）號: CN113268557B
• 公開（公告）日: 2023-08-04
• 發(fā)明（設(shè)計(jì)）人: 陳犖;劉澤邦;馬夢宇;楊岸然;吳燁;賈慶仁;熊偉;歐陽雪
• 申請（專利權(quán)）人: 中國人民解放軍國防科技大學(xué)
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/22;G06F16/26
• 代理公司: 北京中索知識產(chǎn)權(quán)代理有限公司 11640
• 代理人: 秦國鵬

本發(fā)明屬于地理矢量數(shù)據(jù)技術(shù)領(lǐng)域，具體為一種適應(yīng)顯示導(dǎo)向型可視化分析的快速的空間索引方法，包括步驟一：首先參考瓦片地圖技術(shù)，基于四叉樹剖分方法對全球地理范圍進(jìn)行遞歸劃分設(shè)計(jì)了TQ?tree結(jié)構(gòu)，TQ?tree中每個(gè)節(jié)點(diǎn)代表特定且規(guī)律的空間范圍，并對節(jié)點(diǎn)進(jìn)行編碼，實(shí)現(xiàn)節(jié)點(diǎn)與空間范圍間的映射關(guān)系；步驟二：接著提出TQ?tree?generation算法(TQTG)，將矢量要素索引項(xiàng)按要求插入樹節(jié)點(diǎn)中構(gòu)建TQ?tree，該算法構(gòu)建索引的速度快并且索引結(jié)構(gòu)簡單，其結(jié)構(gòu)合理，在使用的過程中，生成的索引結(jié)構(gòu)簡單、構(gòu)建速度快、內(nèi)存占用少，并且能大幅提升顯示導(dǎo)向型可視化分析的效率，可作為億級以上大規(guī)模地理矢量數(shù)據(jù)實(shí)時(shí)可視化分析的數(shù)據(jù)組織支撐。

技術(shù)領(lǐng)域

本發(fā)明涉及地理矢量數(shù)據(jù)技術(shù)領(lǐng)域，具體為一種適應(yīng)顯示導(dǎo)向型可視化分析的快速的空間索引方法。

背景技術(shù)

地理矢量數(shù)據(jù)在城市規(guī)劃、土地利用、環(huán)境因素分析等諸多領(lǐng)域都發(fā)揮著重要的作用，可視化分析是一種理解和分析矢量數(shù)據(jù)的重要手段，通過可視化分析對矢量數(shù)據(jù)進(jìn)行理解和分析，將矢量數(shù)據(jù)的分析結(jié)果以可視化的形式呈現(xiàn)出來，讓用戶以易于理解的方式獲取分析結(jié)果(Keim?D?et?al.,2008)。在我們的前期工作中，提出顯示導(dǎo)向型地理矢量數(shù)據(jù)可視化分析方法，對大規(guī)模地理矢量數(shù)據(jù)的可視化分析可實(shí)現(xiàn)實(shí)時(shí)響應(yīng)的性能(Ma?etal.,2018,2020)。該方法以屏幕顯示效果為計(jì)算目標(biāo)，其核心在于以屏幕顯示像素為計(jì)算單元，對像素對應(yīng)的一定地理空間范圍進(jìn)行檢索從而生成像素值，檢索效率決定了可視化分析的效率。為了提升檢索效率需要對矢量數(shù)據(jù)進(jìn)行組織，當(dāng)矢量數(shù)據(jù)規(guī)模急劇增長時(shí)，如何對大規(guī)模地理矢量數(shù)據(jù)進(jìn)行高效的組織管理并適應(yīng)快速檢索的需求是顯示導(dǎo)向型方法亟需解決的問題。

空間索引技術(shù)是解決海量數(shù)據(jù)快速檢索、查詢和訪問的重要手段，索引技術(shù)的效率是決定數(shù)據(jù)服務(wù)的關(guān)鍵因素。傳統(tǒng)常用的空間索引方法有格網(wǎng)索引(J.Nievergelt?etal.,1984；K.Y.Whang?et?al.,1991)、KD-樹索引(Bentley,1975)、四叉樹索引(Finkel?RAet?al.,1974)和R-樹索引(Guttman,1984)以及上述索引的改進(jìn)、聯(lián)合和變種等，這些索引方法在點(diǎn)、線、面的索引中各自有著自己的應(yīng)用特點(diǎn)，在實(shí)際應(yīng)用中也對應(yīng)這不同的場景(F.C.Com?et?al.,2008)。隨著計(jì)算機(jī)硬件和分布式技術(shù)的發(fā)展，分布式存儲系統(tǒng)被廣泛應(yīng)用于空間數(shù)據(jù)的組織與管理(H.Tan?et?al.,2012；A.Aji?et?al.,2013；A.Eldawy?et?al.,2015；J.Yu?et?al.,2016)。分布式索引可以認(rèn)為是傳統(tǒng)索引理論在分布式環(huán)境下的重新實(shí)現(xiàn)，其顯著提高了數(shù)據(jù)的檢索效率，通過并行數(shù)據(jù)劃分和并行空間查詢，格網(wǎng)索引(A.Ajiet?al.,2013)、四叉樹索引(J.Feng?et?al.,2014)、R-樹索引(P.Lu?et?al.,2014)等傳統(tǒng)的串行空間索引算法在并行環(huán)境中得到了實(shí)現(xiàn)。

然而當(dāng)前空間索引技術(shù)主要側(cè)重于實(shí)現(xiàn)特定的場景應(yīng)用：平衡樹索引結(jié)構(gòu)保證了查詢性能卻帶來了較大的構(gòu)建與更新代價(jià)，非平衡樹結(jié)構(gòu)保證了構(gòu)建與更新效率，卻難以處理聚集分布模式下產(chǎn)生的數(shù)據(jù)傾斜問題。采用分布式技術(shù)雖然提升了索引的檢索效率，但是增加了集群內(nèi)部節(jié)點(diǎn)之間的通信協(xié)議和通信開銷，索引結(jié)構(gòu)更加復(fù)雜(Weng?et?al.,2016)，同時(shí)分布式存儲系統(tǒng)的索引機(jī)制必須充分考慮分布式系統(tǒng)的整體框架和數(shù)據(jù)的組織存儲方式，使得索引構(gòu)建的開銷較大，無法在數(shù)據(jù)組織和可視化分析兩方面同時(shí)達(dá)到較高的效率。

為了解決以上問題，兼顧數(shù)據(jù)組織效率和可視化分析效率，本文提出了一種適應(yīng)顯示導(dǎo)向型可視化分析的快速的空間索引方法。

發(fā)明內(nèi)容

本部分的目的在于概述本發(fā)明的實(shí)施方式的一些方面以及簡要介紹一些較佳實(shí)施方式。在本部分以及本申請的說明書摘要和發(fā)明名稱中可能會做些簡化或省略以避免使本部分、說明書摘要和發(fā)明名稱的目的模糊，而這種簡化或省略不能用于限制本發(fā)明的范圍。

鑒于現(xiàn)有空間索引技術(shù)中存在的問題，提出了本發(fā)明。