一、空間連接定義

隨著全球定位系統(tǒng)和移動互聯(lián)設備的普及，海量的空間數(shù)據(jù)也隨之產(chǎn)生。空間連接（Spatial Join）運算是一類最常用的空間數(shù)據(jù)分析算子，具有廣泛的應用場景。例如統(tǒng)計地鐵站周圍500米的POI，幫助店主合理選擇商鋪選址；從同一個數(shù)據(jù)集中分析空間相鄰的同伴關系，輔助警方偵察；查詢河流周圍的居民區(qū)和農(nóng)田，在汛期排除洪水隱患；查找去過疫區(qū)的人群，方便疫情防控等。

下面給出空間連接的定義：給定空間對相集合R和S以及空間謂詞θ，計算并輸出所有空間對象二元組（r,?s），滿足r∈R，s∈S，且r和s滿足空間謂詞θ，形式化定義如下。

?(1)

空間謂詞θ可以分為三類。

1）空間拓撲：如intersects(相交)、contains（包含）等；

2）空間距離：即distance，表示空間對象s與r的空間距離小于等于設定閾值δ，由定義（1）派生出distance連接的定義如下。

?(2)

3）空間k最近鄰：即kNN（k Nearest Neighbors），表示空間對象s是數(shù)據(jù)集S中與r距離最近的k個空間對象之一，由定義（1）派生出kNN連接的定義如下。

?(3)

另外，空間對象可分為三種類型：點（Point）、線（LineString）、面（Polygon）。點是最簡單的空間對象，線和面是復雜空間對象，其空間運算相對耗時。為了簡化計算，一般用空間對象的最小邊界矩形MBR（MinimumBounding Rectangle）進行空間運算，得到近似結果，然后對近似結果進一步提純過濾，得到最終的精確解。

空間連接運算是基于空間索引實現(xiàn)的，空間索引能夠通過快速過濾來提高查詢效率，基于空間索引的空間連接的運算過程如下：

1）構建空間索引。對集合S中所有空間對象s，利用s.mbr構建空間索引I。

2）循環(huán)查詢。對集合R中的每個空間對象r，用r查詢索引I中與其滿足空間謂詞θ的所有空間對象s，并將二元組（r,s）加入結果集。

空間索引不止一種，選取合理的空間索引對提高空間連接運算的性能至關重要。為了驗證空間索引對空間連接運算性能的影響，本文首先在第2節(jié)中介紹幾種最常用的空間索引。然后在第3節(jié)進行實驗對比，分別以空間索引、空間對象類型、空間連接謂詞為變量，分析影響空間連接運算性能的因素。

二、空間索引

空間索引一般是基于數(shù)據(jù)結構中的樹來實現(xiàn)的。在索引樹上，一個節(jié)點對應一個矩形的空間范圍，父節(jié)點的空間范圍包含所有子節(jié)點的空間范圍。空間對象依據(jù)其MBR，存儲在樹的對應節(jié)點上。在查詢時，首先依據(jù)查詢對象的MBR遍歷樹上與該MBR相交的所有節(jié)點，并收集節(jié)點上存儲的空間對象作為一個候選結果集，最后再根據(jù)空間謂詞θ做進一步過濾，保留滿足空間謂詞的候選對象，組成最終的結果集。下面分別介紹三種最常用的空間索引：Quadtree索引、KDtree索引和Rtree索引，且設定用數(shù)據(jù)集S構建索引，然后用數(shù)據(jù)集R中的空間對象r查詢空間索引。

2.1?Quadtree索引

Quadtree[1]索引是一棵四叉樹，支持所有空間對象類型。Quadtree將集合S的全局空間范圍G遞歸地劃分成4子空間，直到子空間內(nèi)的空間對象數(shù)量小于等于設定的閾值α，并對四個子空間分別編號0、1、2、3，如圖1（a）所示（α?= 1）。然后用四叉樹結構組織所有子空間，如圖1（b）所示，樹的根節(jié)點對應空間范圍G，一個節(jié)點對應一個子空間。對數(shù)據(jù)集S中的空間對象s，將其存儲在包含s.mbr的最小子空間對應的節(jié)點中，當s是空間點時，s與s.mbr空間上等價，所有空間點均存儲在葉子節(jié)點中，如圖1所示。

圖1 Quadtree索引

在查詢時，使用r.mbr近似表示空間對象r，查找Quadtree中與r.mbr相交的節(jié)點，然后判斷節(jié)點中的所有空間對象s是否與r存在空間相交關系。圖1中，紅色的矩形表示r.mbr，該矩形在Quadtree上遍歷的節(jié)點標記為紅色，然后找到葉子節(jié)點233上與其相交的一個空間點s，最后再判斷r和s的相交關系。通過空間索引，可以快速過濾掉與查詢框r.mbr不相交的節(jié)點，加快遍歷查詢效率。

2.2KDtree索引

KDtree[2]索引是一棵二叉樹，僅支持空間點對象。QQ號買賣在構建索引時，首先使用集合S中第一個空間點s1的構建根節(jié)點root，根節(jié)點包含空間點s1和標簽odd，odd是個布爾值，true表示該節(jié)點用s1.x進行空間劃分，false表示用s1.y，KDtree中父節(jié)點和子節(jié)點的odd相反，即交替地使用x和y值進行空間劃分。對于后續(xù)的空間點si（i>1），以root節(jié)點為當前節(jié)點，遞歸地執(zhí)行以下步驟：

1）判斷當前節(jié)點是否為葉子節(jié)點，若是執(zhí)行步驟2），若不是執(zhí)行步驟3）；

2）設當前節(jié)點中存儲的空間點是s，odd = true時根據(jù)s.x的值將當前節(jié)點對應的空間范圍一分為二生成兩個子節(jié)點，反之根據(jù)s.y的值進行劃分。然后根據(jù)si.x（或si.y）與s.x（或s.y）的大小關系，將si保存到對應子節(jié)點上，子節(jié)點的odd值與當前節(jié)點相反；

3）利用步驟2）中描述的判斷方法，得到子節(jié)點，并將其設為當前節(jié)點，然后執(zhí)行步驟1）。

圖2 KDtree索引

在構建好的KDtree索引中，每個空間點對應一個節(jié)點（葉子或非葉子節(jié)點），如圖2所示。查詢時，用r.mbr遍歷樹上所有與之相交的節(jié)點，然后摘取節(jié)點上的空間點s并判斷r與s是否空間相交。在圖2中，紅色矩形表示r.mbr，它在KDtree上遍歷的節(jié)點用紅色標記。

2.3Rtree索引

Rtree[3]索引是一棵多叉樹，支持所有空間對象。Rtree構建索引的思想是空間聚類，對集合S中的所有空間對象聚類，生成n個聚類，然后自底向上遞歸地對n份聚類進一步執(zhí)行聚類，直到n?= 1。Rtree中一個節(jié)點對應一個聚類，與Quadtree和KDtree不同的是，Rtree同一級別的節(jié)點之前可以存在重疊，這保證了一個空間對象僅屬于一個Rtree的葉子節(jié)點，即Rtree中所有空間對象之存儲在葉子節(jié)點中，如圖3所示。

圖3Rtree索引

下面介紹一種JTS[5](JavaTopology Suite)實現(xiàn)的一種Rtree索引——STRtree[4]。該索引的構建步驟如下：

1)初始化集合C = {c1,c2,c3,..,cn},?ci是僅包含一個空間對象si的空間聚類，ci.mbr?=?si.mbr，n是集合S中的空間對象數(shù)量。

2）STRtree有一個閾值m，表示一個非葉子節(jié)點所包含的最大子節(jié)點數(shù)量。γ = ?n/m?表示集合C需要被劃分成γ個聚類。如果γ?= 1，說明n≤?m，則將集合C聚類成一個根節(jié)點Root，ci是Root的子節(jié)點，構建索引完成。如果γ?> 1，則執(zhí)行步驟3）。

3）ε?= ?sqrt(γ)?表示每個聚類在x和y方向上劃分的份數(shù)。對集合C按照ci.mbr.minx在x方向遞增排序，然后將其在x方向上平均地劃分為ε份聚類，然后對每份結果在y方向上按照ci.mbr.miny排序并平均地劃分成ε份聚類，兩次劃分生成大于等于γ份的聚類，γ≤?k?<?n，集合C中的聚類是集合C’中聚類的子節(jié)點。用C’替換C，然后執(zhí)行步驟2）。

在查詢時，同樣用r.mbr遍歷STRtree中與之相交的節(jié)點，并收集葉子節(jié)點上存儲的所有空間對象s，然后判斷r和s是否空間相交。遍歷過程如圖3中紅色節(jié)點所示。

三、實驗分析

為了驗證不同空間索引在空間連接運算中的性能，我們利用真實的空間數(shù)據(jù)對不同空間索引、不同空間對象類型和不同空間連接運算做了對比實驗，總結出了不同空間索引的適用場景。

3.1 實驗數(shù)據(jù)和實驗環(huán)境

我們使用OSM（Open Street Map）提供的部分全球空間數(shù)據(jù)作為實驗數(shù)據(jù)，如表1所示。實驗環(huán)境是8核CPU、16GB內(nèi)存的個人電腦。

表1 實驗數(shù)據(jù)集

數(shù)據(jù)集	點（Point）	線（LineString）	面（Polygon）
數(shù)據(jù)量	50萬條	20萬條	20萬條
文件大小	5.47MB	62.1MB	57.5MB

3.2 實驗結果

實驗的變量有三種：空間索引、空間對象類型、空間連接運算。統(tǒng)計的實驗數(shù)據(jù)有空間索引的構建時長和空間連接的運算時長。另外，實驗中調(diào)用的空間索引都是JTS[5]實現(xiàn)的。

圖4展示了構建空間索引的耗時情況。取STRtree的閾值m?= 10，從圖中可看出，不管對于哪種空間對象類型，構建STRtree索引的耗時最短，因為STRtree每個節(jié)點的子節(jié)點數(shù)量最大，所以節(jié)點數(shù)量最少，樹的深度最小，則構建索引時的遞歸層數(shù)也最小。KDtree索引僅支持空間點，由于是二叉樹，且每個節(jié)點僅存儲一個空間點，KDtree的節(jié)點個數(shù)最多，樹的深度最深，因此其構建時間最長。Quadtree是四叉樹，其構建索引時間介于KDtree和STRtree之間，且遠大于STRtree。

圖4 空間索引的構建性能

圖5展示了空間拓撲連接的實驗性能，謂詞θ?=?intersects。圖中x軸下標的格式為S-R，例如Point-LineString表示對Point數(shù)據(jù)集構建空間索引，然后用LineString數(shù)據(jù)集中的空間對象查詢空間索引。對空間點構建Quadtree索引，用數(shù)據(jù)集LineString和Polygon去查詢時，計算耗時非常長，分別達到了8714毫秒和13424毫秒，說明Quadtree索引并不適用于空間點。為了驗證這一點，我們將兩個數(shù)據(jù)集互換位置，做了對比實驗，當用LineString或Polygon數(shù)據(jù)集構建Quadtree索引，用Point數(shù)據(jù)集查詢時，計算耗時縮短1~2個數(shù)量級，如圖5右邊所示。從總體來看，KDtree索引適合為空間點構建索引，Quadtree和STRtree適合為線和面構建索引。Quadtree構建索引時間長，查詢耗時短，STRtree構建索引時間短，查詢耗時長，若以構建索引時間與查詢計算時間之和作為評價指標，Quadtree性能優(yōu)于STRtree。

圖5 空間拓撲連接性能

圖6展示了空間距離連接運算（δ?= 100米）的性能，在空間距離連接時，將r.mbr向外擴展δ的距離生成擴展最小邊界矩形r.embr(δ)，用r.embr(δ)查詢空間索引，然后判斷空間對象s與r的距離distance(r,?s)是否小于等于δ。圖6中的實驗結果變化趨勢與圖5中類似。需要注意的是，在空間距離連接中，Quadtree和STRtree的性能差異相較圖5中變小了，說明STRtree在空間距離變化過程中性能更加穩(wěn)定。另外，相同數(shù)據(jù)集之間的空間距離連接要比圖5中的空間拓撲連接的耗時更短。主要原因是，雖然空間拓撲連接的結果要比空間距離連接的結果少，但是判斷兩個空間對象r和s的空間intersects關系（等價于distance(r,?s) = 0）要比判斷distance(r,?s) ≤?δ更耗時。

圖6 空間距離連接性能

圖7展示了kNN連接運算的性能（k?= 10），只有STRtree索引支持kNN查詢。當Point數(shù)據(jù)集與其它數(shù)據(jù)集做kNN連接時，計算耗時較低且交換數(shù)據(jù)集時性能變化不大，因為點是最簡單的空間對象，所以點與其它空間對象距離的計算復雜度最低。當LineString和Polygon做kNN連接時，其耗時相對較長且交換數(shù)據(jù)集時性能相差一倍，可以看出，為LineString構建STRtree索引比為Polygon構建索引性能更好， STRtree索引更適用于空間線。

圖7 基于STRtree索引的空間k最近鄰連接性能

四、總結

本文介紹了空間連接運算的定義和基于空間索引的空間連接運算方法。同時，本文介紹了3種常用的樹結構的空間索引和各自的特點。最后，本文做了對比分析實驗，以驗證不同空間索引對不同空間對象的支持情況和性能差異，以便在不同的空間連接運算場景下，選擇適當?shù)目臻g索引，實現(xiàn)高效的查詢和計算。

總結

以上是生活随笔為你收集整理的JUST技术：空间连接运算与空间索引的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。