趙慧慧 趙 凡 陳仁海 馮志勇

1(天津大學(xué)智能與計(jì)算學(xué)部 天津 300350)2(天津大學(xué)深圳研究院 廣東深圳 518000)3(天津大學(xué)國際工程師學(xué)院 天津 300350)

近年來，國家城市化進(jìn)程不斷加快，2維地理空間信息數(shù)據(jù)更新迅速，其中道路網(wǎng)絡(luò)數(shù)據(jù)不僅是路徑規(guī)劃、城市建設(shè)、位置服務(wù)及智能交通的基石，更為數(shù)字城市、智慧城市的發(fā)展奠定了基礎(chǔ)[1].在城市信息化浪潮與數(shù)據(jù)科學(xué)崛起的共同推動(dòng)下，智慧城市的發(fā)展不僅需要龐大的地理空間數(shù)據(jù)作為載體，更加需要高效的空間檢索技術(shù)推動(dòng)智慧城市的發(fā)展[2].地理空間大數(shù)據(jù)作為大數(shù)據(jù)的一個(gè)分支，正在全球范圍內(nèi)迅速崛起[3]，空間大數(shù)據(jù)的時(shí)代已經(jīng)來臨.

空間大數(shù)據(jù)無疑將重構(gòu)很多行業(yè)的商業(yè)思維和商業(yè)模式，其價(jià)值不言而喻[4].與此同時(shí)，隨著定位技術(shù)的發(fā)展，空間大數(shù)據(jù)的位置標(biāo)簽越發(fā)精確.例如，有了WiFi、衛(wèi)星定位、移動(dòng)通信蜂窩定位技術(shù)及其變速器、微陀螺、速度傳感器等多種多樣的微小傳感器的支持，才使得虛擬社交網(wǎng)絡(luò)系統(tǒng)(social network system, SNS)發(fā)展到真實(shí)世界與虛擬世界相融合的基于位置的社交網(wǎng)絡(luò)(location based social network, LBSN)，并成為互聯(lián)網(wǎng)企業(yè)的必爭之地.在人工智能領(lǐng)域，無人駕駛作為其行業(yè)最受關(guān)注的應(yīng)用之一，在其應(yīng)用中道路網(wǎng)絡(luò)數(shù)據(jù)是其必不可少的實(shí)現(xiàn)基礎(chǔ).例如，高精地圖需要個(gè)性化駕駛支持，包括各種駕駛行為建議，如最佳加速點(diǎn)及剎車點(diǎn)、最佳過彎速度等，以提高無人駕駛的舒適度[5].并且無人駕駛汽車可以通過本地計(jì)算來實(shí)時(shí)地對當(dāng)前路況做出反應(yīng)，而不用連接到高延遲的遠(yuǎn)程控制中心[6].在智能交通系統(tǒng)領(lǐng)域，信息采集設(shè)備的普及，每天都會(huì)采集海量的2維地理空間信息數(shù)據(jù)，這些數(shù)據(jù)極為寶貴[7].例如，通過對某個(gè)時(shí)間段某個(gè)路口采集到的車輛情況對該路口的車流量進(jìn)行分析，可以獲悉該路口的路況，向司機(jī)及時(shí)提醒道路的擁堵狀況等.在遙感領(lǐng)域，地理信息系統(tǒng)和定位導(dǎo)航等技術(shù)逐漸商業(yè)化公眾化之后，遙感數(shù)據(jù)觀測與服務(wù)也正在從政府主導(dǎo)的公益應(yīng)用向公眾與商業(yè)機(jī)構(gòu)主導(dǎo)的商業(yè)與公眾應(yīng)用擴(kuò)展[8].在日常生活中，人類所產(chǎn)生的數(shù)據(jù)有80%和空間位置有關(guān)[9]，具有互動(dòng)、非專業(yè)、實(shí)時(shí)、泛在、按需服務(wù)、SOA特征的新地理信息時(shí)代[10]必將是空間大數(shù)據(jù)(big geo-data)備受矚目的時(shí)代.

大數(shù)據(jù)時(shí)代科學(xué)研究是一個(gè)大科學(xué)、大需求、大數(shù)據(jù)、大計(jì)算、大發(fā)現(xiàn)的過程[11].而空間大數(shù)據(jù)是在城市基礎(chǔ)地理信息基礎(chǔ)上，將各個(gè)曾經(jīng)孤立的、服務(wù)內(nèi)容單一的，但具有城市管理功能的空間信息、動(dòng)態(tài)信息和公共信息等城市及信息聚合而成面向大眾的、跨領(lǐng)域的、跨系統(tǒng)的社會(huì)化服務(wù)信息[12].空間大數(shù)據(jù)作為大數(shù)據(jù)與地理信息數(shù)據(jù)的融合體，在信息時(shí)代扮演著重要的角色，已經(jīng)逐漸發(fā)展成為當(dāng)今社會(huì)最基本的信息服務(wù)之一.然而，面對海量的數(shù)據(jù)檢索時(shí)，單單依靠傳統(tǒng)的空間索引技術(shù)，頻繁的插入和刪除操作會(huì)增大2維地理空間信息數(shù)據(jù)地重疊率，數(shù)據(jù)存儲(chǔ)中存在許多彼此相似的數(shù)據(jù)塊[13]，從而導(dǎo)致查找路徑不唯一的情況增多，查詢效率變低.

如何在分布式存儲(chǔ)的模式下設(shè)計(jì)空間索引、提高檢索效率，是空間索引技術(shù)未來重要的發(fā)展方向.本文以空間索引技術(shù)為主線，總結(jié)空間大數(shù)據(jù)下空間索引技術(shù)的背景、研究現(xiàn)狀，分析不同索引類型的優(yōu)劣；重點(diǎn)討論每個(gè)時(shí)期空間索引技術(shù)的變化與技術(shù)創(chuàng)新；然后提出多層切片遞歸空間索引算法(multi-layer slice recursive, MSR)，并與當(dāng)前主流的空間索引技術(shù)基于R樹的批量加載算法(sort tile recursive， STR)、STR-網(wǎng)格混合算法(str-grid)及高效幾何范圍查詢算法(efficient geometric range query, EGRQ)進(jìn)行實(shí)驗(yàn)對比.實(shí)驗(yàn)結(jié)果表明，MSR算法不僅減少了道路網(wǎng)絡(luò)空間數(shù)據(jù)的重疊度，提高了檢索效率,而且可以很好地利用內(nèi)存空間，減少存儲(chǔ)空間的浪費(fèi).最后結(jié)合其面臨的機(jī)遇與挑戰(zhàn)，對2維地理空間信息數(shù)據(jù)做出展望.本文提供了實(shí)驗(yàn)數(shù)據(jù)以及實(shí)驗(yàn)代碼的GitHub鏈接[14]，以供其他研究人員研究.

1 相關(guān)工作

2維地理空間信息數(shù)據(jù)是地理空間信息的重要組成部分.2維地理空間信息數(shù)據(jù)除了具有一般大數(shù)據(jù)體量(volume)大、類型多樣(variety)、處理速度(velocity)快、價(jià)值密度(value)低、真實(shí)性(veracity)高等特點(diǎn)外[15]，還具有其自身鮮明的特點(diǎn)，主要體現(xiàn)在：1)全樣本持續(xù)更新，數(shù)據(jù)呈現(xiàn)的是全樣本的、客觀的、過程的以及連續(xù)性的數(shù)據(jù)類型特點(diǎn)，數(shù)據(jù)資源更加全面、豐富、時(shí)效性更強(qiáng)；2)多維度，道路網(wǎng)絡(luò)數(shù)據(jù)不僅局限于點(diǎn)、線、面，向著更高維空間發(fā)展；3)多粒度多層次，道路網(wǎng)絡(luò)數(shù)據(jù)中碎片化、零散化、低效率的數(shù)據(jù)查詢和分析普遍存在.面對如此規(guī)模龐大并且復(fù)雜的2維地理空間信息數(shù)據(jù)，傳統(tǒng)的空間索引技術(shù)無法滿足大規(guī)模數(shù)據(jù)快速檢索和查詢等需求，此時(shí)，需要查詢效率高效的空間索引技術(shù).

空間索引結(jié)構(gòu)是一種輔助性數(shù)據(jù)結(jié)構(gòu)，它基于空間數(shù)據(jù)的位置、形狀以及對象之間的空間關(guān)系來組織空間數(shù)據(jù)結(jié)構(gòu)，目的是提高數(shù)據(jù)檢索及其他空間操作的效率.傳統(tǒng)的空間索引技術(shù)主要分為三大類，分別為基于網(wǎng)格的空間索引、基于樹結(jié)構(gòu)的空間索引、混合空間索引.

1) 基于網(wǎng)格的空間索引.基于網(wǎng)格的空間索引技術(shù)通過橫豎線條把空間區(qū)域劃分為若干個(gè)大小相同的網(wǎng)格，每個(gè)網(wǎng)格中包含空間對象，當(dāng)用戶查詢時(shí)，首先檢索出用戶查詢的空間對象所在網(wǎng)格，再從網(wǎng)格中定位到目標(biāo)空間對象的位置.網(wǎng)格空間索引的方式很簡單，當(dāng)數(shù)據(jù)分布均勻時(shí)，其空間查詢效率很高.但是網(wǎng)格的大小會(huì)影響到索引表的大小，如果網(wǎng)格太小，索引就會(huì)膨脹，不但查詢效率低，而且對索引表的維護(hù)費(fèi)用也會(huì)增加.目前有很多學(xué)者對此做出的分析和研究，提出了不同的解決方案.分別為基于規(guī)則網(wǎng)格劃分的空間索引、基于多級空間網(wǎng)格劃分的空間索引、自適應(yīng)層級網(wǎng)格化分空間索引.

2) 基于樹結(jié)構(gòu)的空間索引.在基于樹結(jié)構(gòu)的空間索引技術(shù)中，具有代表性的樹結(jié)構(gòu)分別是R樹與四叉樹空間索引.國內(nèi)典型的地理信息軟件如MapGIS與SuperMap，其空間索引技術(shù)采用的是四叉樹索引；國外比較著名的地理信息軟件如MapInfo公司的MapInfo，其空間索引技術(shù)采用的是R樹索引；以及國外Oracle公司的Oracle_Spatial組件采用四叉樹與R樹混合的空間索引技術(shù).

R樹是一種高度平衡樹，它是在B樹基礎(chǔ)上擴(kuò)展了多維空間.R樹索引技術(shù)的本質(zhì)是面向?qū)ο蟮姆指钏饕夹g(shù)，分割后的區(qū)域與每個(gè)結(jié)點(diǎn)相對應(yīng)，每個(gè)結(jié)點(diǎn)又與1個(gè)磁盤頁對應(yīng)，盡管磁盤存儲(chǔ)系統(tǒng)有效地提升了帶寬，但訪問延遲難以得到有效解決[16].R樹不但能控制樹的深度，而且還能采用最小外包矩形[17]表示空間實(shí)體，是最早支持多維空間存取的方法之一.該算法提高了空間數(shù)據(jù)檢索和空間操作的效率.

四叉樹是另一種常見的樹狀索引結(jié)構(gòu)，可分為點(diǎn)四叉樹和區(qū)域四叉樹，適用于點(diǎn)數(shù)據(jù)、區(qū)域數(shù)據(jù)以及高維空間數(shù)據(jù)的索引結(jié)構(gòu)建立.在四叉樹結(jié)構(gòu)中，空間要素標(biāo)識都記錄在外包絡(luò)矩形覆蓋的每個(gè)葉結(jié)點(diǎn)中，所以在內(nèi)存中的層次樹狀結(jié)構(gòu)的查詢效率較高.

3) 混合結(jié)構(gòu)空間索引.混合索引結(jié)構(gòu)汲取了各個(gè)索引結(jié)構(gòu)的長處，多種空間索引的融合也是空間索引技術(shù)發(fā)展的方向，其大致可以分為3類：基于網(wǎng)格與樹結(jié)構(gòu)的混合索引、基于多個(gè)樹結(jié)構(gòu)的混合索引以及圖與樹結(jié)構(gòu)的混合索引.

網(wǎng)格與樹混合索引的典型是基于固定網(wǎng)格與四叉樹結(jié)合的空間索引機(jī)制.這種混合索引機(jī)制通過使用索引結(jié)點(diǎn)表和Hash技術(shù)管理類對象結(jié)點(diǎn)表，達(dá)到節(jié)省存儲(chǔ)空間的目的，因此有效地減少了磁盤讀取次數(shù)，顯著提高了空間查詢速度.空間對象與葉子結(jié)點(diǎn)出現(xiàn)了多對多的情況，但是相比之下，基于固定網(wǎng)格與四叉樹結(jié)合的空間索引機(jī)制，能夠使大面積空間對象重復(fù)減少；其不足之處在于算法的空間復(fù)雜度比較高，維護(hù)比較困難.

多個(gè)樹結(jié)構(gòu)的混合索引有很多，具代表性的是QR樹，首先利用四叉樹將數(shù)據(jù)庫的研究區(qū)域分割為多級子索引空間，然后將R樹索引應(yīng)用到各級中的每個(gè)子空間.這種混合索引機(jī)制的優(yōu)點(diǎn)是利用縮小的空間范圍提高了查詢效率，數(shù)據(jù)量越大索引效果越好.但是該方法沒有考慮到大空間對象對數(shù)據(jù)的影響，在檢索大范圍空間對象時(shí)，其檢索效率往往不高；索引占用的空間也比R樹大.

圖與樹的混合索引機(jī)制，一般將圖論的思想應(yīng)用在空間索引范疇上.基于MR-Tree空間索引的Voronoi圖改進(jìn)及其并行空間查詢方法，在MR-Tree索引基礎(chǔ)上，引進(jìn)了鄰近關(guān)系判斷，以替代范圍查詢中的冗余計(jì)算，有效地提高了分布式環(huán)境下的空間操作的效率.

國外研究空間索引的成果最早可追溯到20世紀(jì)70年代文獻(xiàn)[18]提出的四叉樹索引，這是一種樹狀數(shù)據(jù)結(jié)構(gòu)，在每個(gè)結(jié)點(diǎn)上會(huì)有4個(gè)子區(qū)塊，將數(shù)據(jù)空間均勻的劃分為4個(gè)象限，數(shù)據(jù)范圍可以是矩形或其他任意形狀.文獻(xiàn)[19]提出了KD樹(多維二叉搜索樹)，KD樹是每個(gè)點(diǎn)都為K維點(diǎn)的二叉樹，其在點(diǎn)的查找上有著與二叉樹一樣良好的性能.文獻(xiàn)[20]提出了KD樹的改進(jìn)——非同構(gòu)KD樹，降低了刪除的代價(jià).文獻(xiàn)[21]介紹了R樹這種處理高維空間存儲(chǔ)問題的數(shù)據(jù)結(jié)構(gòu).文獻(xiàn)[22]提出了網(wǎng)格的思想，通過網(wǎng)格劃分?jǐn)?shù)據(jù)空間，再利用網(wǎng)格地址檢索相應(yīng)磁盤頁.這一方法主要用于多維點(diǎn)，對于其他目標(biāo)并不適用.文獻(xiàn)[17]提出了最佳動(dòng)態(tài)R樹的變種——R*樹，R*樹和R樹一樣允許矩形的重疊，但在構(gòu)造算法上R*樹不僅考慮了索引空間的“面積”，而且還考慮了索引空間的重疊.文獻(xiàn)[23]利用Hilbert分形曲線，對N維空間數(shù)據(jù)進(jìn)行1維排序，進(jìn)而對樹結(jié)點(diǎn)進(jìn)行排序，為獲得較高的存儲(chǔ)利用率對排序后得到的結(jié)點(diǎn)集實(shí)施滯后分裂算法，這也形成了Hilbert R樹算法的核心.文獻(xiàn)[24]提出了R樹的變形樹STR樹.文獻(xiàn)[25]提出了一種連續(xù)K最近鄰查詢算法，將當(dāng)前參考點(diǎn)進(jìn)行迭代操作，使當(dāng)前參考點(diǎn)移動(dòng)到最近的分割點(diǎn).

國內(nèi)研究的空間索引技術(shù)起步于20世紀(jì)90年代，文獻(xiàn)[26]提出一種G樹的空間模型和動(dòng)態(tài)網(wǎng)格的操作算法.借鑒Windows NT等操作系統(tǒng)采用頁面來管理虛擬內(nèi)存的方式，設(shè)計(jì)實(shí)現(xiàn)了基于頁面的新的空間索引機(jī)制，有效地解決了N維空間數(shù)據(jù)的索引問題.但其結(jié)點(diǎn)的空間利用率相比其他索引樹而言偏低.文獻(xiàn)[27]提出了基于Hilbert空間排列的點(diǎn)特征二叉平衡排序樹動(dòng)態(tài)索引結(jié)構(gòu)和基于角點(diǎn)回溯的線特征索引結(jié)構(gòu)，為動(dòng)態(tài)內(nèi)存索引與磁盤索引提供了新的思路，并滿足GIS數(shù)據(jù)模型的要求.文獻(xiàn)[28]針對現(xiàn)有R樹索引不支持空間數(shù)據(jù)多尺度表達(dá)的問題，提出了一種用于空間數(shù)據(jù)多尺度表達(dá)的樹變形索引結(jié)構(gòu)，該算法在檢索多分辨率形式組織的空間數(shù)據(jù)時(shí)效果顯著.文獻(xiàn)[29]提出了基于線性四叉樹結(jié)構(gòu)的Voronoi圖反向膨脹生成算法.文獻(xiàn)[30]提出了基于MR-Tree空間索引的Voronoi圖改進(jìn)及其并行空間查詢方法.

以上描述的空間索引技術(shù)及其變體，是針對不同應(yīng)用、不同類型及不同需求的空間數(shù)據(jù)對象，在某些領(lǐng)域有其自身的優(yōu)勢，但換另一種數(shù)據(jù)結(jié)構(gòu)也許在查詢效率上就稍遜一籌了.

本文提出的MSR算法首先對地圖數(shù)據(jù)劃分切片，然后在單一切片內(nèi)聚類對比，在相鄰切片內(nèi)進(jìn)行聚類以此保證數(shù)據(jù)間擁有最大程度的空間鄰接性；其次，按照一定范圍構(gòu)建葉子結(jié)點(diǎn)類并處理離散值；最后自下而上遞歸生成MSR樹.MSR算法能夠很好地處理數(shù)據(jù)密度高畸變的空間區(qū)域并且不會(huì)出現(xiàn)磁盤浪費(fèi)的情況.這是因?yàn)镸SR算法減少了矩形框的重疊率，查找路徑不唯一的情況很大程度減少，所以其查詢效率較高.通過與當(dāng)前主流的空間索引技術(shù)STR算法、STR-網(wǎng)格混合算法(STR_GRID) 及EGRQ算法進(jìn)行實(shí)驗(yàn)對比，驗(yàn)證了本文提出的算法的良好性能.

2 MSR算法相關(guān)知識

在本節(jié)中，首先介紹基于2維地理空間信息數(shù)據(jù)的空間索引機(jī)制在構(gòu)建過程中涉及的概念，然后介紹一種基于R樹的批量加載算法——STR算法、一種混合空間索引機(jī)制STR-網(wǎng)格算法及EGRQ算法.

2.1 基本定義

基于地圖數(shù)據(jù)的空間索引機(jī)制主要是針對優(yōu)化道路網(wǎng)絡(luò)數(shù)據(jù)查詢而建立的空間索引結(jié)構(gòu)，其中2維空間道路網(wǎng)絡(luò)數(shù)據(jù)查詢主要包括2個(gè)方式：點(diǎn)查詢和區(qū)域查詢.點(diǎn)查詢就是在索引結(jié)構(gòu)中找到距離目標(biāo)點(diǎn)最近的空間對象，而區(qū)域查詢是找到給定區(qū)域中的所有空間對象，所以區(qū)域查詢更加復(fù)雜.

定義1.空間數(shù)據(jù).空間數(shù)據(jù)是用來表示空間對象的位置、大小、形狀及其分布特征諸多方面信息的數(shù)據(jù).它可以是點(diǎn)、線、面以及高維的多面體等，比如地圖上常見的建筑物、道路、城市.

定義2.最小外包矩形[31].最小外包矩形(mini-mum bounding rectangle， MBR)是指以2維坐標(biāo)表示的若干2維形狀(例如點(diǎn)、直線、多邊形)的最大范圍，即以給定的2維形狀各頂點(diǎn)中的最大橫坐標(biāo)、最小橫坐標(biāo)、最大縱坐標(biāo)、最小縱坐標(biāo)定下邊界的矩形.最小外包矩形是最小外接框(minimum bounding box， MBB)的2維形式.

定義3.R樹[32].R樹是用來做空間數(shù)據(jù)存儲(chǔ)的樹狀結(jié)構(gòu).例如給地理位置、矩形和多邊形這類多維數(shù)據(jù)創(chuàng)建索引.

其核心思想是聚合距離相近的結(jié)點(diǎn)并在樹結(jié)構(gòu)的上一層將其表示為這些結(jié)點(diǎn)的最小外包矩形，這個(gè)最小外包矩形就成為上一層的一個(gè)結(jié)點(diǎn).葉子結(jié)點(diǎn)上的每個(gè)矩形都代表一個(gè)對象[33]，結(jié)點(diǎn)都是對象的聚合，并且越往上層聚合的對象就越多.也可以把每一層看作是對數(shù)據(jù)集的近似，葉子結(jié)點(diǎn)層是最細(xì)粒度的近似，與數(shù)據(jù)集相似度100%，越往上層越粗糙.

定義4.聚類[34].聚類是將數(shù)據(jù)集中的數(shù)據(jù)根據(jù)各自的特征分成不同的簇，簇間盡可能相異，簇內(nèi)盡可能相似.

聚類是數(shù)據(jù)挖掘中的一種無先驗(yàn)條件的無監(jiān)督分析方法.早期傳統(tǒng)的聚類查詢算法主要關(guān)注于獲得精確的聚集統(tǒng)計(jì)值[35].

2.2 STR算法的構(gòu)建過程

STR算法主要是應(yīng)用于區(qū)域查詢而構(gòu)建的樹型索引結(jié)構(gòu)算法，它基于排序思想構(gòu)建的R樹可以達(dá)到近乎100%的空間利用率.STR算法中假設(shè)2維空間有N個(gè)對象的最小外包矩形(MBR)，每個(gè)R樹結(jié)點(diǎn)的最大容量為M，STR算法的基本思想為：按MBR中心點(diǎn)的X坐標(biāo)對其排序，等分為S組，并使每一組中包含M×S個(gè)空間對象，在每一組中用MBR中心點(diǎn)的y坐標(biāo)進(jìn)行排序，每M個(gè)MBR形成1個(gè)新的結(jié)點(diǎn)，并將新結(jié)點(diǎn)的MBR作為下一次遞歸的輸入，自下而上生成整棵R樹.

2.3 STR-網(wǎng)格混合算法

STR-網(wǎng)格混合算法首先通過對空間區(qū)域進(jìn)行劃分，縮小研究范圍，達(dá)到提高檢索效率的目的.基本思想是通過橫豎線條把空間區(qū)域劃分為若干個(gè)相同大小的網(wǎng)格，每個(gè)網(wǎng)格代表1個(gè)存儲(chǔ)桶，將落在該網(wǎng)格中的空間對象放入對應(yīng)的存儲(chǔ)桶中.之后根據(jù)桶中的空間對象的多少，繼續(xù)劃分網(wǎng)格，直至每個(gè)子網(wǎng)格中的空間對象個(gè)數(shù)滿足閾值，最后對每個(gè)子網(wǎng)格中的空間對象按照STR算法再進(jìn)行組織索引.當(dāng)用戶進(jìn)行查詢操作時(shí)，首先檢索出用戶查詢的空間對象所在網(wǎng)格，然后再通過STR算法從網(wǎng)格中定位到所需空間對象的位置.

2.4 EGRQ算法

高效幾何范圍查詢算法EGRQ，采用安全KNN計(jì)算、多項(xiàng)式擬合技術(shù)以及R樹索引，來提高空間對象的查詢效率.

STR算法、STR-網(wǎng)格混合算法和EGRQ算法都有其固定的缺陷.STR算法不能很好地處理數(shù)據(jù)高畸變的空間區(qū)域，其查詢性能低效.STR-網(wǎng)格混合算法首先通過網(wǎng)格對空間區(qū)域進(jìn)行劃分，然后再在每個(gè)網(wǎng)格中構(gòu)造STR樹.當(dāng)網(wǎng)格對空間區(qū)域進(jìn)行劃分時(shí)，將空間區(qū)域劃分為多個(gè)子空間，這種劃分方式全憑經(jīng)驗(yàn).如果對空間區(qū)域劃分時(shí)出現(xiàn)網(wǎng)格劃分過細(xì)的情況，則會(huì)導(dǎo)致耗費(fèi)磁盤存儲(chǔ)空間和搜索時(shí)間過長，磁盤存儲(chǔ)冗余大，造成磁盤浪費(fèi)，內(nèi)存利用率低；如果網(wǎng)格劃分過大，則該方法不能很好地處理數(shù)據(jù)密度高畸變的空間區(qū)域，導(dǎo)致其查詢效率降低.本文提出的MSR算法能夠很好地處理以上問題.

3 MSR算法的設(shè)計(jì)與實(shí)現(xiàn)

在對2維地理空間信息數(shù)據(jù)研究過程中發(fā)現(xiàn)，隨著空間對象的增多，空間對象的MBR之間的重疊現(xiàn)象會(huì)不斷加大.目前針對2維空間對象(點(diǎn)、線、面)的查找方式多以相交、距離等判定方法，這種方法導(dǎo)致空間對象之間的MBR重疊數(shù)量加大，使查詢過程中無用路徑的數(shù)量變多，從而影響查詢效率.本文提出的MSR算法從優(yōu)化空間對象之間的MBR重疊數(shù)量這一角度出發(fā)，根據(jù)空間鄰接性法則交叉搜索相鄰切片中的空間對象，同時(shí)使用空間聚類方法修正單維度排序所造成位置分布過于稀疏的問題，以自下而上的方式生成空間索引樹型結(jié)構(gòu).

本文采用的空間對象是全國道路網(wǎng)絡(luò)數(shù)據(jù)，圖1是北京市道路網(wǎng)絡(luò)數(shù)據(jù)的MBR的效果展示圖.可以看出，空間區(qū)域中MBR重疊現(xiàn)象嚴(yán)重.如果在數(shù)據(jù)量龐大的、復(fù)雜的、形狀多種多樣的全國道路網(wǎng)絡(luò)數(shù)據(jù)中查詢目標(biāo)數(shù)據(jù)，合理、高效的空間存儲(chǔ)索引結(jié)構(gòu)是簡化檢索路徑、縮短檢索時(shí)間最有效的方法.

Fig. 1 Road network MBR renderings圖1 道路網(wǎng)絡(luò)MBR效果圖

Fig. 2 MSR algorithm framework圖2 MSR算法框架

3.1 MSR算法概述

MSR結(jié)構(gòu)一共包含3種結(jié)點(diǎn)：根結(jié)點(diǎn)、子結(jié)點(diǎn)和葉子結(jié)點(diǎn).根結(jié)點(diǎn)和子結(jié)點(diǎn)主要存儲(chǔ)孩子結(jié)點(diǎn)的位置，葉子結(jié)點(diǎn)主要存儲(chǔ)空間經(jīng)緯度信息.MSR算法構(gòu)造的空間索引樹框架圖如圖2所示，其中2維地理空間數(shù)據(jù)在第1維度排序且切分后形成的數(shù)據(jù)集表示為FD(first division)切片，SD(second division)切片表示2維地理空間數(shù)據(jù)在第2維度排序后形成的數(shù)據(jù)集.經(jīng)過FD切片和SD切片操作形成數(shù)據(jù)集.至此，MSR構(gòu)建完成.

下面介紹MSR算法的整體流程：

輸入：2維地理空間信息數(shù)據(jù)中的r個(gè)空間對象，每個(gè)結(jié)點(diǎn)的最大容量為N；

輸出：包含r個(gè)空間對象的MSR空間索引樹.

1) 計(jì)算所有2維地理空間信息數(shù)據(jù)的MBR，對樹結(jié)點(diǎn)的各項(xiàng)信息做初始化操作；

3) 對每個(gè)切片中空間對象按照第2維度進(jìn)行排序；

4) 按照排序后的結(jié)果尋找一個(gè)未聚類的對象作為初始化類C；

5) 考慮到空間對象的鄰接性和空間對象的分布情況，根據(jù)初始類的MBR中心點(diǎn)位置向四周一定的范圍內(nèi)設(shè)定搜索框S；

6) 計(jì)算搜索框S包含的當(dāng)前切片和相鄰切片中所有的空間對象，得出命中對象列表H，其長度為L；

7) 如果命中個(gè)數(shù)L≥N-1，在命中列表中尋找距離類中心最近的空間對象，將結(jié)果歸到類中，更新類大小和類中心，知道滿足結(jié)點(diǎn)容量；

8) 如果命中個(gè)數(shù)L

9) 按照步驟4)～8)，每2個(gè)切片為1組，遍歷全部切片，最后1個(gè)切片也按照上述原則構(gòu)造；

10) 按照步驟1)～9)，自下至上，遞歸構(gòu)建，最終生成根結(jié)點(diǎn).至此，整棵MSR樹構(gòu)造完成.

圖3展示了MSR樹的生成過程實(shí)例，對空間區(qū)域中編號為1～10的空間對象求出其MBR.然后進(jìn)行第1維數(shù)據(jù)排序和切分操作，其結(jié)果為：1，4，2，6，7，5和8，9，3，10，再對每個(gè)切片進(jìn)行第2維排序操作，其結(jié)果為：1，2，5，4，7，6和3，9，8，10.最后按照MSR算法取2個(gè)切片中的數(shù)據(jù)聚類為矩形框11，12，13，14和15，16，這樣第1層葉子結(jié)點(diǎn)就生成了，接下來就是不斷地執(zhí)行遞歸操作,直到生成根結(jié)點(diǎn).

Fig. 3 MSR tree generation process圖3 MSR樹生成過程

3.2 MSR算法描述

在本節(jié)中，我們給出MSR構(gòu)造算法生成的偽代碼，MSR構(gòu)造算法的算法描述如下所示：

算法1.多層切片遞歸算法.

輸入：當(dāng)前切片Tilec和相鄰切片Tilea,搜索框B;

輸出：MSR空間索引樹;

過程：MSR(Tilec,Tilea,B)→MSR空間索引樹.

①GET_search_List(Tilec,Tilea,B)→Hlist;

② Letcluster←C;*將當(dāng)前切片的首個(gè)未聚類的數(shù)據(jù)初始化為新的類*

③ ifHlist.length≥N-1*根據(jù)命中數(shù)據(jù)的大小分別處理*

GET_clustering(Hlist,C);

else ifN2-1≤Hlist.length≤N-1

Cluster←Hlist;

elseOutlierlistappendHlist;

④ End if

⑤MSRinsert(Nodelist,Outlierlist)→Nodelist;

⑥TreeNodeConstructor(Nodelist)→Nodelist;

⑦ ifNodelist.length>1*執(zhí)行遞歸操作，直到生成根結(jié)點(diǎn)*

LetTilec←Tilea;

LetTilea←Tilea.next;

MSR(Tilec,Tilea,B)→MSRTree;

⑧ End if

⑨ Output(Nodelist).*輸出整棵樹*

在MSR構(gòu)造算法中，搜索框是以類的矩形框向四周以一定距離為半徑進(jìn)行搜索的空間范圍，同時(shí)每次聚類操作結(jié)束后都要把已完成聚類的空間對象進(jìn)行標(biāo)記，以免重復(fù)利用.在聚類過程內(nèi)部，要注意每次添加數(shù)據(jù)后需要實(shí)時(shí)更新類的大小和中心點(diǎn)，對于命中空間對象個(gè)數(shù)的使用規(guī)則是參考了R樹結(jié)點(diǎn)容量的性質(zhì)，即每個(gè)結(jié)點(diǎn)包含[m,N]個(gè)數(shù)據(jù)，其中一般m=N2.

3.3 MSR樹的更新和檢索

MSR樹的查找和STR類似，自下而上逐漸將下層的數(shù)據(jù)矩形抽象到高層的正方形，即對下層數(shù)據(jù)矩形有正方形化的趨勢.檢索算法從樹的根結(jié)點(diǎn)開始，它將所有與查詢區(qū)域存在交疊的結(jié)點(diǎn)的子結(jié)點(diǎn)查出，然后將這些子結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)檢查它們與查詢區(qū)域是否存在交疊，直到找到葉子結(jié)點(diǎn)的空間對象.MSR算法通過判斷MBR與查詢窗口是否相交，如果相交則遍歷所有孩子結(jié)點(diǎn)繼續(xù)判斷，直至獲取到葉子結(jié)點(diǎn)的空間對象信息.

MSR樹的更新和R樹類似，對于搜索路徑上的每個(gè)結(jié)點(diǎn)，遍歷其中的最小外包矩形(MBR)，如果搜索到1個(gè)葉子結(jié)點(diǎn)，則比較搜索框與它的最小外包矩形和數(shù)據(jù)，如果該葉子結(jié)點(diǎn)在搜索框中，則把葉子結(jié)點(diǎn)加入搜索結(jié)果.添加操作如果遇到結(jié)點(diǎn)溢出則分裂，分裂的方法和R樹相同，都是更新相關(guān)的一條路徑上的信息，并且為了盡可能少出現(xiàn)結(jié)點(diǎn)溢出的現(xiàn)象，在進(jìn)行實(shí)驗(yàn)時(shí)，會(huì)為每個(gè)結(jié)點(diǎn)設(shè)置多余空間作為緩沖區(qū).

4 實(shí)驗(yàn)與結(jié)果

在本節(jié)中，通過使用本文構(gòu)建的一種針對 2維地理空間信息數(shù)據(jù)進(jìn)行多層切片遞歸的空間索引樹構(gòu)造算法MSR，然后再利用不同量級以及不同城市的地圖數(shù)據(jù)測試MSR算法性能,并且與傳統(tǒng)的STR算法[36]、STR-網(wǎng)格混合索引(STR_GRID)算法[12]以及EGRQ算法[37]進(jìn)行實(shí)驗(yàn)對比.在硬件方面，實(shí)驗(yàn)設(shè)備為聯(lián)想Y700-15ISK電腦，搭載的是Windows10操作系統(tǒng)，基本配置為i7-6700HQ 4核處理器,處理速度為主頻2.6 GHz超頻至3.2 GHz，256 GB固態(tài)硬盤+1TB機(jī)械硬盤，RAM的容量為16 GB.

4.1 數(shù)據(jù)集和算法性能度量

本文分別使用北京市道路網(wǎng)數(shù)據(jù)、天津市道路網(wǎng)數(shù)據(jù)和全國道路網(wǎng)數(shù)據(jù)構(gòu)造MSR算法、STR算法、STR-網(wǎng)格混合索引算法(STR_GRID)以及EGRQ算法這4種算法的空間索引結(jié)構(gòu)，以區(qū)域查詢耗時(shí)作為衡量算法優(yōu)劣的指標(biāo)，詳細(xì)的道路網(wǎng)絡(luò)數(shù)據(jù)信息如表1所示：

Table 1 The Data of Experiment表1 實(shí)驗(yàn)數(shù)據(jù)

通過表1可以得到，北京市的道路數(shù)量為84 543條，全國路網(wǎng)數(shù)據(jù)量為2 668 904條，其數(shù)據(jù)量非常巨大，天津市的道路數(shù)量最小.圖4展示了北京市的道路網(wǎng)絡(luò)圖.城市道路具有鮮明的特點(diǎn)，其形狀多種多樣，數(shù)據(jù)由2維的經(jīng)緯度坐標(biāo)組成.圖4以北京市的城市交通路網(wǎng)數(shù)據(jù)為例，繪制北京市道路網(wǎng)絡(luò)圖，其中顏色較深(藍(lán)色)的道路為雙向路，顏色較淺(紅色)的為單向路，效果如圖4所示：

Fig. 4 Beijing road network renderings圖4 北京市道路網(wǎng)絡(luò)效果圖

4.2 實(shí)驗(yàn)和結(jié)果

在本節(jié)中，首先通過使用MSR空間索引結(jié)構(gòu)，對生成樹的過程中葉結(jié)點(diǎn)的矩形框進(jìn)行效果展示.如圖5所示，道路網(wǎng)絡(luò)數(shù)據(jù)為北京市道路網(wǎng)絡(luò)數(shù)據(jù)，圖5中展示了2種算法的差異，MSR算法構(gòu)造的矩形框多為正方形，而不是STR算法構(gòu)造的長方形.

Fig. 5 Effect of MSR on the lower node of Beijing road network data圖5 MSR算法在北京市道路網(wǎng)數(shù)據(jù)下葉結(jié)點(diǎn)效果展示

其次，通過實(shí)現(xiàn)傳統(tǒng)的STR算法、STR-網(wǎng)格混合算法(STR_GRID)以及EGRQ算法作為對比實(shí)驗(yàn)用來驗(yàn)證MSR算法的優(yōu)越性能，其中EGRQ算法的結(jié)果是以2為底取對數(shù)后的實(shí)驗(yàn)結(jié)果.本文分別從查詢窗口大小、樹的層次以及查詢個(gè)數(shù)來測試3種算法的性能，其中樹的層次即為樹的層數(shù)，指的是每層結(jié)點(diǎn)中MBR的重疊數(shù)量.本實(shí)驗(yàn)中，在市級規(guī)模的道路網(wǎng)路數(shù)據(jù)中以0.1的差值作為經(jīng)緯度網(wǎng)格單元的劃分標(biāo)準(zhǔn)，在全國道路網(wǎng)絡(luò)數(shù)據(jù)中以1的差值作為劃分標(biāo)準(zhǔn).

圖6所示實(shí)驗(yàn)數(shù)據(jù)為北京市道路網(wǎng)絡(luò)數(shù)據(jù)，當(dāng)查詢數(shù)目為5 000時(shí)，EGRQ算法查詢性能最差，查詢時(shí)間取對數(shù)后的結(jié)果為11 s；STR_GRID的查詢時(shí)間為10.3 s；其次是傳統(tǒng)的STR算法，其查詢時(shí)間為10 s；MSR算法性能最優(yōu)，其查詢時(shí)間為9.4 s.

Fig. 6 Comparison of query results under Beijing road network data圖6 北京市道路網(wǎng)數(shù)據(jù)下的查詢結(jié)果比較

圖7所示實(shí)驗(yàn)數(shù)據(jù)是天津市道路網(wǎng)絡(luò)數(shù)據(jù)，雖然STR_GRID的查詢性能略優(yōu)于MSR算法，但是2種算法的查詢性能差異并不是很明顯.出現(xiàn)這種現(xiàn)象的原因如下：STR_GRID是將所有的空間對象劃分到各個(gè)網(wǎng)格中，每次構(gòu)建STR樹時(shí)，只是構(gòu)建每個(gè)網(wǎng)格中包含的空間對象，所以其查詢時(shí)間相對較低.MSR算法并沒有進(jìn)行劃分網(wǎng)格的操作，在構(gòu)建STR樹時(shí)，面向的是所有的空間對象，所以其查詢時(shí)間相對較高，但這種現(xiàn)象是很少出現(xiàn)的，尤其是面對大量的空間對象時(shí)，MSR算法性能優(yōu)于STR_GRID.并且STR-網(wǎng)格算法有著固有的缺陷，該算法首先通過網(wǎng)格對空間區(qū)域進(jìn)行劃分，然后再在每個(gè)網(wǎng)格中構(gòu)造STR樹.當(dāng)網(wǎng)格對空間區(qū)域進(jìn)行劃分時(shí)，將空間區(qū)域劃分為多個(gè)子空間，這種劃分方式全憑經(jīng)驗(yàn).如果對空間區(qū)域劃分時(shí)，出現(xiàn)網(wǎng)格劃分過細(xì)的情況，則會(huì)導(dǎo)致耗費(fèi)磁盤存儲(chǔ)空間和搜索時(shí)間過長，磁盤存儲(chǔ)冗余大，造成磁盤浪費(fèi)，內(nèi)存利用率低；如果網(wǎng)格劃分過細(xì)，則該方法不能很好地處理數(shù)據(jù)密度高畸變的空間區(qū)域.而MSR算法能夠很好地處理數(shù)據(jù)密度高畸變的空間區(qū)域并且不會(huì)出現(xiàn)磁盤浪費(fèi)的情況.并且MSR算法的查詢性能優(yōu)于傳統(tǒng)的STR算法和EGRQ算法.所以，綜上所述，MSR算法具有最優(yōu)的查詢及存儲(chǔ)性能.

Fig. 7 Comparison of query results under Tianjin road network data圖7 天津市道路網(wǎng)數(shù)據(jù)下的查詢結(jié)果比較

通過圖6和圖7可知，除了EGRQ算法的查詢性能差異明顯以外，其他3種算法在地市級的道路網(wǎng)絡(luò)數(shù)據(jù)中的查詢效率相差不大，3種算法的折線圖走勢差異很平緩，尤其是當(dāng)查詢數(shù)目為1 000時(shí)，3種算法的查詢時(shí)間基本相當(dāng)，所以猜想是道路數(shù)據(jù)量導(dǎo)致查詢算法性能差異不明顯的現(xiàn)象.

將4種算法運(yùn)用到全國道路網(wǎng)絡(luò)數(shù)據(jù)中，通過增加構(gòu)造空間索引結(jié)構(gòu)的數(shù)據(jù)量，得到的索引結(jié)構(gòu)的查詢結(jié)果圖如圖8所示：

Fig. 8 Comparsion of query results under national road network data圖8 全國道路網(wǎng)數(shù)據(jù)下的查詢結(jié)果比較

圖8所示的查詢結(jié)果驗(yàn)證了猜想的正確性，空間對象數(shù)據(jù)量的增大對空間索引的性能要求更加苛刻.從圖8中可以看到同為純樹型結(jié)構(gòu)的STR算法和MSR算法查詢效果差距較大.當(dāng)查詢數(shù)目為5 000時(shí)，EGRQ算法通過以2為底取對數(shù)后的查詢時(shí)間為13 s；STR算法的查詢時(shí)間為29.9 s，STR_GRID算法的查詢時(shí)間為16.2 s，MSR算法的查詢時(shí)間為14 s.在這4種算法中，MSR算法的查詢時(shí)間最小，EGRQ算法查詢時(shí)間最大.圖8展示的實(shí)驗(yàn)結(jié)果再次驗(yàn)證了本文所提出的MSR算法在查詢性能及存儲(chǔ)性能的優(yōu)越性.

圖8的實(shí)驗(yàn)結(jié)果中，STR_GRID查詢效果比STR算法效果好很多.為了找到這種現(xiàn)象出現(xiàn)的原因，本文分別統(tǒng)計(jì)了北京市、天津市及全國的道路網(wǎng)絡(luò)數(shù)據(jù)在STR算法中每層樹結(jié)點(diǎn)中的最小外包矩形框重疊個(gè)數(shù)，如圖9所示.

從圖9中可以很明顯地發(fā)現(xiàn),地市級的道路網(wǎng)絡(luò)數(shù)據(jù)和全國道路網(wǎng)絡(luò)數(shù)據(jù)在STR樹型空間索引結(jié)構(gòu)的構(gòu)造過程中矩形框的重疊量存在巨大差異，尤其是在樹的第1層，STR算法的MBR重疊量為108137E6，但是本文提出的MSR算法的MBR重疊量為700 123，這種差異幾乎是指數(shù)級別的差距.這種現(xiàn)象出現(xiàn)的原因歸結(jié)于數(shù)據(jù)結(jié)構(gòu)的構(gòu)建原理，這是不可避免的現(xiàn)象，這也是學(xué)術(shù)界在數(shù)據(jù)結(jié)構(gòu)的構(gòu)建問題上，體現(xiàn)出的一種技術(shù)瓶頸.這是2種數(shù)據(jù)的查詢時(shí)間相差很大的根本原因.

Fig. 9 STR algorithm overlay map圖9 STR算法的重疊量展示圖

最后在實(shí)驗(yàn)的基礎(chǔ)上，又分別統(tǒng)計(jì)STR算法和MSR算法在全國道路網(wǎng)數(shù)據(jù)下，樹型空間索引結(jié)構(gòu)在樹構(gòu)造過程中每層樹結(jié)點(diǎn)中的最小外包矩形框重疊個(gè)數(shù)，結(jié)果如圖10所示：

Fig. 10 STR tree and MSR tree layer overlay display圖10 STR樹和MSR樹各層重疊量展示圖

如圖10所示，全國道路網(wǎng)絡(luò)數(shù)據(jù)量巨大，通過對全國道路網(wǎng)絡(luò)數(shù)據(jù)構(gòu)建空間索引結(jié)構(gòu)時(shí)，樹結(jié)構(gòu)每一層中，STR算法和MSR算法首先都根據(jù)空間對象的最小外包矩形構(gòu)建樹型結(jié)構(gòu).很明顯地看出，樹結(jié)構(gòu)第1層的最小外包矩形重疊數(shù)據(jù)差距巨大，如圖10所示MSR算法的最小外接矩形框重疊數(shù)量比STR算法少了近30多萬個(gè).當(dāng)進(jìn)行檢索操作時(shí)，由于檢索過程中存在檢索路徑不唯一的情況，從而導(dǎo)致檢索效率很低.本文提出的MSR算法能夠很大程度上減少最小外包矩形的重疊數(shù)量，而最小外包矩形的重疊數(shù)量，嚴(yán)重影響查詢時(shí)間，MSR算法能夠很好地解決這種現(xiàn)象，這是算法執(zhí)行性能優(yōu)越性的體現(xiàn).

然而由于STR_GRID和EGRQ算法并不是純樹型的索引結(jié)構(gòu)，所以圖10展示了STR算法和MSR算法的MBR的重疊數(shù)量.STR_GRID在劃分網(wǎng)格這一步驟中，由于其算法在空間區(qū)域內(nèi)對道路網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行切分，通過網(wǎng)格拆分龐大的道路網(wǎng)絡(luò)數(shù)據(jù)，這種方法減少了每個(gè)網(wǎng)格中道路的數(shù)據(jù)量，因此STR_GRID也比STR算法的查詢效率高.但是由于網(wǎng)格索引固有的弊端，比如網(wǎng)格的大小會(huì)影響到索引表的大小，如果網(wǎng)格太小，索引就會(huì)膨脹.網(wǎng)格過小不能很好地處理數(shù)據(jù)高畸變的空間區(qū)域，不但查詢效率低，而且浪費(fèi)內(nèi)存空間.本文提出的MSR算法能夠很好地處理數(shù)據(jù)密度高畸變的空間區(qū)域并且不會(huì)出現(xiàn)磁盤浪費(fèi)的情況.

本節(jié)在這3種不同的影響因素即數(shù)據(jù)規(guī)模、構(gòu)建樹的層數(shù)以及查詢數(shù)目的前提下，通過對這4種算法即STR算法、STR_GRID、EGRQ算法以及MSR算法進(jìn)行實(shí)驗(yàn)對比，結(jié)果均顯示MSR算法不僅減少了最小外包矩形框的重疊數(shù)量，提高了查詢效率，而且又可以很好地利用內(nèi)存空間，減少存儲(chǔ)空間的浪費(fèi).

5 總 結(jié)

本文提出了一種對2維地理空間信息數(shù)據(jù)進(jìn)行多層切片遞歸的空間索引樹構(gòu)造算法MSR.首先對地圖數(shù)據(jù)劃分切片，然后在單一切片內(nèi)聚類對比，在相鄰切片內(nèi)進(jìn)行聚類以此保證數(shù)據(jù)間擁有最大程度的空間鄰接性；其次，按照一定范圍構(gòu)建葉子結(jié)點(diǎn)類并處理離散值；最后自下而上遞歸生成MSR樹.實(shí)驗(yàn)結(jié)果表明，MSR算法不僅減少了最小外包矩形框的重疊數(shù)量，提高了查詢效率，而且又可以很好地利用內(nèi)存空間，減少存儲(chǔ)空間的浪費(fèi)，優(yōu)于目前主流的空間索引算法STR算法、STR_GRID及EGRQ算法.