QML：一種混合空間索引結(jié)構(gòu)

崔棟，溫巧燕，張華，王華偉

（北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876）

1 引言

物聯(lián)網(wǎng)設(shè)備會生成大量的地理空間數(shù)據(jù)，為了有效地訪問和處理此類數(shù)據(jù)，數(shù)據(jù)庫管理員通常會采用基于樹的索引結(jié)構(gòu)來提高數(shù)據(jù)分析和事務(wù)性工作負(fù)載性能[1]。為了提升數(shù)據(jù)庫的讀寫性能，整個索引通常會保存在內(nèi)存中。但當(dāng)數(shù)據(jù)量達(dá)到PB級別以上時，樹形索引結(jié)構(gòu)會急速變大，進(jìn)而嚴(yán)重侵占系統(tǒng)資源。研究表明，在商用內(nèi)存數(shù)據(jù)庫中，索引占用了全部內(nèi)存空間的55%[2]?，F(xiàn)有的索引結(jié)構(gòu)在空間大數(shù)據(jù)環(huán)境下面臨存儲空間占用高和查詢I/O 次數(shù)多的問題。

機(jī)器學(xué)習(xí)算法的引入從根本上改變索引結(jié)構(gòu)。2018 年，Kraska 等[1]在SIGMOD 會議上首次提出了學(xué)習(xí)索引的概念。他們將機(jī)器學(xué)習(xí)方法應(yīng)用于索引結(jié)構(gòu)中，在降低索引空間代價的同時提升了索引查詢性能。緊隨其后，學(xué)者從一維數(shù)據(jù)結(jié)構(gòu)和多維數(shù)據(jù)結(jié)構(gòu)中開展了研究工作。其中，一維索引的研究主要有FITing-Tree[3]、AlEX[4]、PGM-index[5]、XIndex[6]、Dabble[7]等，多維索引的研究主要有ZM 索引[8]、ML-Index 索引[9]、LISA索引[10]和Flood 索引[11]等?？臻g數(shù)據(jù)庫主要使用的是多維索引。

2019 年，Wang 等[8]在多維空間數(shù)據(jù)上使用Z順序曲線進(jìn)行投影降維構(gòu)建了支持范圍查詢的ZM索引。ZM 索引不支持K近鄰（KNN,K-nearest neighbor）查詢，也不支持插入和刪除操作。2020 年，Davitkova 等[9]為了支持KNN 查詢，基于iDistance方法構(gòu)建了ML-Index 索引，但是沒有解決插入和刪除的問題。同年，Li 等[10]和Nathan 等[11]在SIGMOD 會議上分別提出了LISA 索引和Flood 索引。LISA 索引支持了索引的插入和刪除操作，在一定程度上優(yōu)化了效率，但是LISA 索引并不適用于頻繁大規(guī)模更新的空間數(shù)據(jù)集。Flood 索引相比于之前的索引大幅度優(yōu)化了存儲，提高了查詢性能，但是只支持只讀工作負(fù)載，不支持插入等操作。

本文使用四叉樹索引結(jié)構(gòu)對空間數(shù)據(jù)進(jìn)行均勻快速的劃分，使用Z順序曲線進(jìn)行數(shù)據(jù)降維。為了使生成的QML 索引更符合數(shù)據(jù)的分布特征以支持快速的更新和查詢操作，本文提出了動態(tài)數(shù)據(jù)分段算法DDSA。該算法生成的數(shù)據(jù)段符合線性和二次曲線分布，這2 種分布更接近現(xiàn)實(shí)數(shù)據(jù)情況。本文在此基礎(chǔ)上使用分段線性函數(shù)和二階多項(xiàng)式函數(shù)擬合多維空間數(shù)據(jù)構(gòu)建QML 索引，并實(shí)現(xiàn)了范圍查詢和KNN 查詢。實(shí)驗(yàn)結(jié)果表明QML 索引存儲比R*-tree[12]等減少33%，更新效率提升40%～80%，查詢效率與最優(yōu)樹形索引相近。QML 索引數(shù)據(jù)更新的時間復(fù)雜度僅為O(1)，優(yōu)于LISA 索引。本文的主要貢獻(xiàn)如下。

1) 提出了QML，這是一種新的混合空間索引結(jié)構(gòu)，在保證索引查詢和更新性能的同時，降低存儲空間，是利用數(shù)據(jù)分布規(guī)律來構(gòu)建空間索引的一種新的嘗試。

2) 提出了適用于學(xué)習(xí)索引的動態(tài)數(shù)據(jù)分段算法DDSA，該算法能夠根據(jù)局部數(shù)據(jù)分布特征選取不同的多項(xiàng)式函數(shù)進(jìn)行擬合。

3) 設(shè)計(jì)并實(shí)現(xiàn)了基于QML 的范圍查詢算法和KNN 查詢算法，并通過真實(shí)數(shù)據(jù)集的測試證明QML 提供了與最優(yōu)樹形索引結(jié)構(gòu)相近的（點(diǎn)查詢性能更好）查詢性能和更新性能，大幅降低了存儲空間。

2 相關(guān)工作

空間索引是為多維數(shù)據(jù)訪問設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)。大多數(shù)空間索引是空間驅(qū)動或數(shù)據(jù)驅(qū)動的結(jié)構(gòu)[13]?？臻g驅(qū)動的結(jié)構(gòu)（如固定網(wǎng)格索引[14]）將空間分解為單元格，并根據(jù)幾何準(zhǔn)則映射數(shù)據(jù)對象。數(shù)據(jù)驅(qū)動的結(jié)構(gòu)（如R-tree[15]）將數(shù)據(jù)對象劃分為簇，并通過其最小外接矩形（MBR,minimum bounding rectangle）劃分空間。此外，UB-tree[16]是Z順序曲線[17]和B+tree 的組合，是一個平衡樹，數(shù)據(jù)對象按Z階存儲。實(shí)際數(shù)據(jù)具有一定的分布特點(diǎn)，但是傳統(tǒng)的數(shù)據(jù)索引結(jié)構(gòu)沒有利用這一特點(diǎn)，因此不能發(fā)揮數(shù)據(jù)最大的作用。

由文獻(xiàn)[18-22]可知，學(xué)習(xí)索引可以充分利用數(shù)據(jù)的分布規(guī)律，在提升查詢性能的同時降低空間消耗。ZM 索引[8]使用Z順序曲線進(jìn)行降維；ML-Index索引[9]采用基于iDistance[23]方法的改進(jìn)策略對數(shù)據(jù)進(jìn)行投影；LISA 索引[10]使用網(wǎng)格劃分和基于勒貝格測度的投影進(jìn)行數(shù)據(jù)有序化。Flood 索引[11]采用基于成本模型的網(wǎng)格劃分策略；在模型選擇上，ZM索引和ML-Index 索引都選用了RMI 模型；為了使索引擁有更低的空間成本和執(zhí)行成本，LISA 索引和Flood 索引選擇使用分段線性回歸模型。在空間查詢應(yīng)用中，已有的多維索引都實(shí)現(xiàn)了對空間范圍查詢的支持，ML-Index、LISA 索引和Flood 索引還可以支持KNN 查詢。Nathan 等[11]沒有給出利用Flood 索引進(jìn)行KNN 查詢的具體實(shí)現(xiàn)。LISA 索引采用格子回歸模型[24]，并結(jié)合范圍查詢實(shí)現(xiàn)了KNN 查詢。

支持頻繁的數(shù)據(jù)更新是上述多維學(xué)習(xí)索引面臨的一個難題。ZM 索引、ML-Index 索引和Flood索引目前僅支持只讀的靜態(tài)負(fù)載；LISA 索引雖然通過采用異地插入的方式支持了索引插入和刪除，但是索引的更新效率隨著數(shù)據(jù)更新規(guī)模的增加而下降，因此不適用于頻繁更新的空間數(shù)據(jù)。為了應(yīng)對可能頻繁更新的空間數(shù)據(jù)，本文提出了QML 混合空間索引結(jié)構(gòu)。QML 索引在支持范圍查詢和KNN 查詢的基礎(chǔ)上，通過動態(tài)數(shù)據(jù)分段算法DDSA快速構(gòu)建本地模型，在大幅降低存儲空間和提高動態(tài)更新效率的同時，獲得近似最優(yōu)樹形空間索引的查詢性能。

多維空間數(shù)據(jù)在降維和有序化后可以近似看作具有時序特征的數(shù)據(jù)。時序數(shù)據(jù)的分段模式表示是一種對時序數(shù)據(jù)進(jìn)行抽象和概況的表示方法[25]。分段線性近似（PLA,piecewise linear approximation）算法將數(shù)據(jù)分割成若干段后使用線性函數(shù)來逼近每個段。Liu 等[26]提出了一種利用PLA 實(shí)現(xiàn)緊湊分段的方法，稱為可行空間窗（FSW,feasible space window）。FSW 算法通過可行空間的概念，在保證每個數(shù)據(jù)點(diǎn)有誤差界的情況下，可以找到每個數(shù)據(jù)段的最遠(yuǎn)分割點(diǎn)，在學(xué)習(xí)索引模型FITing-Tree[3]中應(yīng)用的就是該方法。但FSW 算法無法直接用于非線性函數(shù)。Xu 等[27]在此基礎(chǔ)上提出一種可行系數(shù)空間（FCS,feasible coefficient space）算法用于解決該問題。該算法通過尋找特定函數(shù)系數(shù)邊界確定一個可行系數(shù)空間，通過不斷縮小該空間的范圍來進(jìn)行數(shù)據(jù)分段。FCS 算法適用于各種復(fù)雜多項(xiàng)式函數(shù)的擬合，但空間數(shù)據(jù)一般呈二次曲線分布，F(xiàn)CS 算法對于索引構(gòu)建過于復(fù)雜。

本文針對上述的問題提出了適用于學(xué)習(xí)索引的動態(tài)數(shù)據(jù)分段算法DDSA，該算法使用分段線性函數(shù)和二階多項(xiàng)式函數(shù)進(jìn)行分段，在保證分段效率的同時盡可能將相似數(shù)據(jù)劃分到一起。

3 QML 索引

3.1 QML 核心思想

本文選取了公開數(shù)據(jù)集OpenStreetMap[28]上的美國本土各類建筑、商店等標(biāo)簽的地理信息，通過Z順序曲線變換后數(shù)據(jù)的分布規(guī)律如圖1 所示。從圖1 中可以看出，空間數(shù)據(jù)在經(jīng)過降維和序列化后呈單調(diào)遞增的分布規(guī)律。

圖1 OSM 美國本土地理信息數(shù)據(jù)分布規(guī)律

為了更好地?cái)M合數(shù)據(jù)分布并支持索引的動態(tài)更新，QML 索引采用四叉樹進(jìn)行數(shù)據(jù)劃分，Z順序曲線進(jìn)行數(shù)據(jù)降維和有序化，最后使用動態(tài)數(shù)據(jù)分段算法DDSA 進(jìn)行數(shù)據(jù)分段和模型構(gòu)建。

四叉樹的生成和維護(hù)比較簡單，當(dāng)數(shù)據(jù)分布比較均勻時，有較高的數(shù)據(jù)插入和查詢速率。當(dāng)數(shù)據(jù)分布不均且數(shù)據(jù)量較大時，為了緩解數(shù)據(jù)偏移帶來的索引樹不平衡的壓力，QML 索引使用存儲最大數(shù)據(jù)量閾值的單元格cell 作為四叉樹的葉節(jié)點(diǎn)，減少中間節(jié)點(diǎn)的數(shù)量和樹深度。LISA 索引采用的網(wǎng)格劃分策略因?yàn)樵跀?shù)據(jù)變動較大時需要重新排序并劃分，所以并不適用于頻繁變更的數(shù)據(jù)集，相比之下，QML 的四叉樹結(jié)構(gòu)則可以更靈活快速地進(jìn)行索引插入和刪除操作。

在存儲優(yōu)化方面，QML 索引的節(jié)點(diǎn)包括中間節(jié)點(diǎn)和葉節(jié)點(diǎn)，中間節(jié)點(diǎn)不存儲數(shù)據(jù)，葉節(jié)點(diǎn)存儲最大數(shù)據(jù)量閾值的數(shù)據(jù)和本地模型集合。因此QML可以顯著降低中間節(jié)點(diǎn)的數(shù)量，減少存儲消耗。

在索引動態(tài)更新方面，四叉樹的數(shù)據(jù)分割策略將數(shù)據(jù)空間V按數(shù)據(jù)量劃分成最小單元格cell，保證在數(shù)據(jù)更新時只需對單獨(dú)cell 上的模型進(jìn)行重構(gòu)，避免相互間的影響。動態(tài)數(shù)據(jù)分段算法DDSA 可以通過一次性的數(shù)據(jù)遍歷構(gòu)建索引模型。實(shí)驗(yàn)表明QML 索引擁有比傳統(tǒng)索引更好的更新性能。

在查詢性能優(yōu)化方面，QML 的混合索引結(jié)構(gòu)通過減少中間節(jié)點(diǎn)減少了不必要的間接查詢，其模型可以根據(jù)數(shù)據(jù)分布特征選取不同的多項(xiàng)式函數(shù)進(jìn)行擬合，減少不必要的數(shù)據(jù)分段。這些結(jié)構(gòu)設(shè)計(jì)可以優(yōu)化QML 索引查詢算法，提高檢索速度，同時也很好地支持了范圍查詢和KNN 查詢。

3.2 QML 構(gòu)建

如圖2 所示，QML 索引的構(gòu)建過程可以分為3 個階段：數(shù)據(jù)劃分、數(shù)據(jù)降維和有序化、數(shù)據(jù)分段和模型生成。相關(guān)參數(shù)定義如表1 所示。QML 索引的輸入為原始數(shù)據(jù)集Data:Data={ki|i=0,1,…,t}。

圖2 QML 構(gòu)建示意

表1 參數(shù)定義

階段1數(shù)據(jù)劃分

步驟1將原始數(shù)據(jù)集Data 的數(shù)據(jù)點(diǎn)ki映射到二維數(shù)據(jù)空間V=[0,X)[0,Y)∈R2，計(jì)算數(shù)據(jù)空間V的數(shù)據(jù)量Vcount；

步驟2如果Vcount>Cell_max_count，執(zhí)行步驟3；如果Vcount≤Cell_max_count 則構(gòu)建單元格cell，將cell 加入根節(jié)點(diǎn)并執(zhí)行階段2 的步驟4；

步驟3對數(shù)據(jù)空間V按照四叉樹進(jìn)行等距劃分，生成4 個子數(shù)據(jù)空間{NW,NE,SW,SE}并加入根節(jié)點(diǎn)中，對新生成的空間區(qū)域Vi∈{NW,NE,SW,SE}利用步驟1 再次進(jìn)行劃分；

（見算法1 的第1)行～第11)行）

階段2數(shù)據(jù)降維和有序化

步驟4對于單元格 cell 內(nèi)任意的ki=(xi,yi)按照Z順序曲線映射函數(shù)M計(jì)算，構(gòu)建三元組

步驟5對單元格cell所有的按照由小到大排序，形成有序數(shù)據(jù)集

（見算法1 的第12)行～第21)行）

階段3數(shù)據(jù)分段和模型生成

步驟6將有序數(shù)據(jù)集d中每個的和j映射到二維空間，然后使用DDSA 進(jìn)行數(shù)據(jù)分段，得到數(shù)據(jù)集合D={di | i=0,1,…,m}；

步驟7根據(jù)每個子數(shù)據(jù)集di的數(shù)據(jù)分布特征分別使用線性函數(shù)和二階多項(xiàng)式函數(shù)進(jìn)行擬合，生成本地模型集合L={li|i=0,1,…,m}；

（見算法1 的第22)行～第24)行）

4 動態(tài)數(shù)據(jù)分段算法DDSA

為了使索引的模型更加符合數(shù)據(jù)分布特征并提高構(gòu)建效率，本文設(shè)計(jì)的動態(tài)數(shù)據(jù)分段算法DDSA采用FSW算法[27]和SFCS算法交叉驗(yàn)證的方式，分別使用線性函數(shù)和二階多項(xiàng)式函數(shù)進(jìn)行擬合。其中SFCS 算法是本文針對數(shù)據(jù)的非線性特征專門設(shè)計(jì)的一個與之適配的簡化可行系數(shù)空間算法。

本文DDSA 的工作原理是將待分割有序數(shù)據(jù)集的第一個數(shù)據(jù)點(diǎn)初始化為分段的左端點(diǎn)，然后在每一步中嘗試將下一個點(diǎn)也放入分段。新加入的數(shù)據(jù)點(diǎn)需要在當(dāng)前分段的最大誤差允許范圍內(nèi)，如果超過最大誤差則開啟新的分段。其關(guān)鍵是使當(dāng)前分段在給定的最大誤差下盡可能地延長。

對于每一個分段，DDSA 都會根據(jù)最大誤差閾值生成一個可行區(qū)間S。當(dāng)有新的數(shù)據(jù)點(diǎn)加入時，算法需要結(jié)合初始點(diǎn)和最大誤差閾值計(jì)算新數(shù)據(jù)點(diǎn)的可行區(qū)間S′，當(dāng)2 個區(qū)間S和S′沒有共同區(qū)域時則表示當(dāng)前分段結(jié)束。

DDSA 先使用FSW 算法[27]判斷新加入的數(shù)據(jù)點(diǎn)是否符合線性分布，如果不符合再使用本文設(shè)計(jì)的SFCS 算法判斷是否為二次曲線分布。

DDSA 的詳情如算法2 所示。DDSA 輸入為有序數(shù)據(jù)集data、最大誤差閾值ε和算法類型type。算法類型type 分別用0 和1 表示FSW 算法和SFCS算法。輸出結(jié)果為數(shù)據(jù)集Data 的本地模型集合L。

首先進(jìn)行初始化操作。設(shè)置type=0，構(gòu)建FSW算法可行區(qū)間Sfsw，初始數(shù)據(jù)段d包含第一個和第二個數(shù)據(jù)點(diǎn)，初始數(shù)據(jù)點(diǎn)設(shè)置初始數(shù)據(jù)段d的算法類型d.type=0。

算法從數(shù)據(jù)點(diǎn)開始遍歷。用FSW 算法構(gòu)建新的可行區(qū)間Sfsw，當(dāng)該可行區(qū)間為空時改用SFCS算法進(jìn)行判斷。每一次從FSW 算法切換到SFCS算法時都需要進(jìn)行初始化操作，選取當(dāng)前數(shù)據(jù)段的起始點(diǎn)、中間點(diǎn)和最后數(shù)據(jù)點(diǎn)構(gòu)建SFCS 算法的可行區(qū)間Ssfcs。然后根據(jù)新生成的可行區(qū)間Ssfcs來判斷待檢測點(diǎn)是否滿足二次曲線分布。

如果在處Sfsw和Ssfcs都為空，則在此處進(jìn)行切分，作為下一個數(shù)據(jù)段的起始點(diǎn)。d形成新的數(shù)據(jù)段。最后根據(jù)d的算法類型d.type 確定使用線性函數(shù)或者二次多項(xiàng)式函數(shù)進(jìn)行擬合生成本地模型l，加入模型集合L中。

上述過程中，SFCS 算法通過計(jì)算二次多項(xiàng)式函數(shù)參數(shù)的可行區(qū)間進(jìn)行判斷。詳情如下。

假設(shè)XY二維坐標(biāo)系中有數(shù)據(jù)點(diǎn)p0,p1,…,pn近似二次多項(xiàng)式y(tǒng)=ax2+bx+c分布，對于每個數(shù)據(jù)點(diǎn)pi=(xi,yi) 如果滿足xi

坐標(biāo)系中二次函數(shù)采用式(1)的形式，其中a、b、c是該函數(shù)的系數(shù)

為了定位該曲線，將坐標(biāo)系的第一個數(shù)據(jù)點(diǎn)p0(x0,y0) 和第二個數(shù)據(jù)點(diǎn)p1(x1,y1)放置在近似曲線上，可以得到

根據(jù)式(2)和式(3)可以得到參數(shù)a、b的映射關(guān)系

設(shè)置允許的誤差范圍為ε∈N+，即擬合曲線與數(shù)據(jù)點(diǎn)的距離在ε內(nèi)。為了簡化算法，本文將該距離近似為兩者Y坐標(biāo)軸的差值，假如第三個數(shù)據(jù)點(diǎn)p2(x2,y2) 滿足最大誤差的二次曲線分布，則有

利用式(5)和式(2)，可以進(jìn)一步得到

如圖3(a)所示，式(4)描述為直線L0，式(6)和式(7)描述為平行線L11和L12之間的區(qū)域，因此可以得到參數(shù)a、b的可行區(qū)間[P11,P12]。當(dāng)驗(yàn)證第四個數(shù)據(jù)點(diǎn)時，可以得到類似式(6)和式(7)的關(guān)系（圖3(a)中平行線L21和L22之間的區(qū)域），該區(qū)間與直線L0相交于點(diǎn)P21和P22。因此區(qū)間[P11,P12]和[P21,P22] 重疊區(qū)域[P21,P12]即新的可行區(qū)間。重復(fù)該過程，直到可行區(qū)間為空。該算法通過不斷縮小范圍來得到分布相似的數(shù)據(jù)點(diǎn)并進(jìn)行劃分，其過程如圖3(b)所示。

圖3 SFCS 算法示意

SFCS 算法如算法3 所示。相比于算法復(fù)雜度為O(n) 的FCS 算法，SFCS 算法將多邊形的可行空間計(jì)算簡化為線性的可行區(qū)間計(jì)算，算法復(fù)雜度為O(1)，雖然犧牲了一定的精確度，但是降低了算法的復(fù)雜度，提升了算法的運(yùn)行速度。

5 基于QML 的查詢處理

5.1 范圍查詢

對于QML 索引的范圍查詢可以視為對矩形區(qū)域的查詢。給定查詢矩形 qr=[xl,xu)[y l,yu)，其中xl和yl分別表示x軸和y軸方向最小邊界值，xu和yu分別表示x軸和y軸方向最大邊界值。范圍查詢示意如圖4 所示，先通過四叉樹快速查找到與qr 有交集的單元格cell，然后將qr 查詢分解為多個小矩形的并集

當(dāng)查詢的類型為lri（圖4(b)）時，索引會先計(jì)算其矩形區(qū)域的最小Z值和最大Z值。然后將Z值映射到模型曲線上（圖4(c)）獲取可能的數(shù)據(jù)地址，對應(yīng)的數(shù)據(jù)地址需要根據(jù)最大誤差范圍進(jìn)行修正以保證覆蓋率。因?yàn)槟Ｐ颓€映射的數(shù)據(jù)范圍大于查詢的lri實(shí)際范圍（圖4(b)深色區(qū)域），因此需要對查詢的數(shù)據(jù)進(jìn)行校驗(yàn)再放入查詢結(jié)果中。

圖4 范圍查詢示意

5.2 KNN 查詢

給定一個數(shù)據(jù)點(diǎn)qknn=(x,y) 和一個距離值δ，以點(diǎn)qknn為圓心劃定半徑為δ的圓，將該圓內(nèi)部區(qū)域定義為B(qknn,δ)。將B(qknn,δ) 包含的點(diǎn)按照與點(diǎn)qknn的距離由小到大排列，最終選取的topK個點(diǎn)即KNN 查詢的結(jié)果。

QML索引采用空間密度估算KNN查詢距離δ，將KNN 查詢轉(zhuǎn)化為遞歸和范圍查詢。QML 的KNN查詢過程如圖5 所示，通過構(gòu)建矩形區(qū)域Q(qknn,δ)，將目標(biāo)區(qū)域B(qknn,δ)變?yōu)镼(qknn,δ)的內(nèi)切圓，將查詢B(qknn,δ)的點(diǎn)轉(zhuǎn)化為查詢Q(qknn,δ) 范圍內(nèi)的點(diǎn)。通過設(shè)置初始距離δ0，逐步擴(kuò)展查詢區(qū)域，直到查詢結(jié)果滿足K個或者距離大于最大查詢距離δ。

初始距離δ0設(shè)置和擴(kuò)展策略對KNN 查詢算法至關(guān)重要。δ0過大或者或過小都會導(dǎo)致查詢性能下降。為此本文提出QML 的空間密度測量方法。QML混合索引通過引入四叉樹，盡可能地將數(shù)據(jù)進(jìn)行等量劃分，每個單元格 cell 包含的數(shù)據(jù)量不大于Cell_max_count。因此本文可以做出合理假設(shè)：空間cell 內(nèi)數(shù)據(jù)點(diǎn)大致均勻分布，在此基礎(chǔ)上計(jì)算cell=[l x,u x)[l y,uy)包含數(shù)據(jù)的空間密度

當(dāng)要選取區(qū)域cell 內(nèi)K個點(diǎn)時，可以根據(jù)空間密度估算距離δ0為

如圖5 所示，此時可以先獲取區(qū)域B(qknn,δ0)內(nèi)的所有數(shù)據(jù)點(diǎn)。假設(shè)區(qū)域B(qknn,δ0) 內(nèi)的數(shù)據(jù)點(diǎn)數(shù)量K′小于要查詢的K，則需要對初始距離δ0進(jìn)行擴(kuò)展。在空間密度保持不變的假設(shè)條件下，B(qknn,δ1)的勒貝格測度是B(qknn,δ0) 的K/K′倍，因此可以推斷出拓展后的距離為

圖5 KNN 查詢示意

給定查詢點(diǎn)qknn=(x,y)、最大查詢距離δ、返回結(jié)果數(shù)量K，QML 索引的KNN 查詢過程如下。

步驟1初始化查詢矩形qr 為空，查找點(diǎn)qknn所在的cell，并根據(jù)cell 的空間密度ρ和返回結(jié)果數(shù)量K計(jì)算半徑距離δ0（式(11)）；

步驟2比較δ0和最大查詢距離δ，選擇較小值為初始查詢距離δ′；

步驟3使用qknn和δ′構(gòu)建查詢矩形然后計(jì)算qr′和qr ∩qr′的差集得到需要查詢的矩形區(qū)域qr″；

步驟4查詢矩形區(qū)域qr″得到可能的結(jié)果隊(duì)列result′，遍歷result′判斷數(shù)據(jù)點(diǎn)是否在圓形區(qū)域B(qknn,δ′)范圍內(nèi)，如果在，則加入結(jié)果隊(duì)列Lr中，否則加入等待隊(duì)列Lw中；

步驟5對等待隊(duì)列Lw中數(shù)據(jù)點(diǎn)做校驗(yàn)判斷是否符合B(qknn,δ′) 的范圍要求，符合則加入Lr中；

步驟6判斷結(jié)果隊(duì)列Lr中的數(shù)據(jù)量是否已經(jīng)滿足K個，滿足則退出，不滿足則使用式(12)重新計(jì)算δ′，并將現(xiàn)在的qr′賦值給qr，再次執(zhí)行查詢操作。

6 QML 的數(shù)據(jù)更新

QML 的數(shù)據(jù)更新包括插入和刪除操作，相應(yīng)的更新算法同時支持單點(diǎn)更新和批量更新。

6.1 插入

QML 的本地模型是基于有序數(shù)據(jù)排列完成的，當(dāng)有新的數(shù)據(jù)加入時需要對數(shù)據(jù)進(jìn)行重新排序和本地模型訓(xùn)練。這樣的操作會消耗一定的計(jì)算資源。為了避免頻繁的排序和模型訓(xùn)練，QML采用緩存插入的方式。當(dāng)新的數(shù)據(jù)點(diǎn)要插入數(shù)據(jù)節(jié)點(diǎn)時，先加入等待插入的緩存隊(duì)列，當(dāng)緩存隊(duì)列達(dá)到最大閾值時，再對節(jié)點(diǎn)進(jìn)行重新排序和模型訓(xùn)練。

給定需要插入的數(shù)據(jù)點(diǎn)k=(x,y)，QML 索引的插入過程如下。

步驟1通過QML 索引根節(jié)點(diǎn)查找到k所在的單元格cell，如果單元格cell 為空則初始化該單元格；

步驟2使用Z順序曲線映射函數(shù)M計(jì)算k的Z值zvalue得到kz，使用單元格cell 的本地模型集合L對zvalue進(jìn)行檢索；

步驟3如果檢索到zvalue所在位置數(shù)值為空，則直接將kz插入該點(diǎn)；如果檢索到zvalue不存在，則先將該數(shù)據(jù)點(diǎn)加入cell 的緩存隊(duì)列中，然后執(zhí)行步驟4 的分裂檢查機(jī)制；

步驟 4如果 cell 的數(shù)據(jù)量 size 大于Cell_max_count 或者緩沖區(qū)數(shù)據(jù)量大于緩沖區(qū)閾值則合并數(shù)據(jù)集，并對當(dāng)前單元格cell 執(zhí)行算法1 的數(shù)據(jù)劃分操作。

6.2 刪除

考慮到更新效率，QML 索引在執(zhí)行刪除操作時不會直接刪除索引，而是先將該索引處的數(shù)值置空，然后執(zhí)行節(jié)點(diǎn)合并檢查機(jī)制，當(dāng)滿足條件時再對單元格cell 重新構(gòu)建。

給定需要刪除的數(shù)據(jù)點(diǎn)k=(x,y)，QML 索引的刪除過程如下。

步驟1通過根節(jié)點(diǎn)查找k所在的cell，若cell不存在則直接返回false，否則執(zhí)行步驟2；

步驟2通過Z順序曲線映射函數(shù)M計(jì)算k的Z值得到kz，使用cell 的本地模型集合L檢索kz的zvalue，若zvalue存在且數(shù)值不為空，則將該索引處的數(shù)值置空，然后執(zhí)行步驟3 的合并檢查機(jī)制；

步驟3獲取cell 的父節(jié)點(diǎn)pCell，如果pCell的數(shù)據(jù)量小于Cell_max_count，則將pCell 賦值給cell，并遞歸使用步驟3 進(jìn)行判斷；當(dāng)pCell 數(shù)據(jù)量大于Cell_max_count 時執(zhí)行步驟4 并發(fā)送當(dāng)前的cell；

步驟4將步驟3 的輸出結(jié)果命名為newCell，若newCell 與初始cell 不同，即上層節(jié)點(diǎn)滿足合并條件時，對newCell 執(zhí)行算法1 的數(shù)據(jù)劃分操作；如果newCell 和cell 是同一個，則比較cell 的數(shù)據(jù)量和其索引長度大小，若兩者差值大于最大閾值，則對當(dāng)前cell 執(zhí)行算法1 的數(shù)據(jù)分段和模型生成操作。

7 索引評估

本節(jié)從學(xué)習(xí)多維索引對比和實(shí)驗(yàn)驗(yàn)證2 個方面對構(gòu)建的QML 索引進(jìn)行評估。

7.1 學(xué)習(xí)多維索引對比

QML 索引實(shí)現(xiàn)了ZM[8]、ML-Index[9]、LISA[10]、Flood[11]等學(xué)習(xí)多維空間索引所支持的各種功能，包括范圍查詢、KNN 查詢、索引更新等，本文從數(shù)據(jù)布局、一維空間學(xué)習(xí)模型以及算法復(fù)雜度等角度對現(xiàn)有的學(xué)習(xí)多維空間索引進(jìn)行了對比，如表2 所示。

表2 學(xué)習(xí)多維索引比較

QML 索引的數(shù)據(jù)布局采用四叉樹和Z順序曲線結(jié)合的方式，根據(jù)設(shè)計(jì)的DDSA 通過一次性數(shù)據(jù)遍歷構(gòu)建分段模型。QML 索引相比于其他學(xué)習(xí)多維索引的優(yōu)勢主要在功能實(shí)現(xiàn)和數(shù)據(jù)更新上。QML索引的范圍查詢時間復(fù)雜度為O(logn)+O(n)，優(yōu)于LISA 索引的O(n2)+O(n)。QML 使用樹狀索引作為中間節(jié)點(diǎn)保證了數(shù)據(jù)更新（插入和刪除）的時間復(fù)雜度為O(1)，相比其他索引具有更靈活的構(gòu)建方式，能快速實(shí)現(xiàn)索引的動態(tài)更新。

7.2 實(shí)驗(yàn)驗(yàn)證

因?yàn)閷?shí)驗(yàn)數(shù)據(jù)的限制，本文的實(shí)驗(yàn)驗(yàn)證部分主要是將QML 索引和R*-tree[13]、KD-tree、Quad-tree、UB-tree 進(jìn)行比較。本節(jié)實(shí)驗(yàn)包括實(shí)驗(yàn)設(shè)置、數(shù)據(jù)分段算法對比實(shí)驗(yàn)、參數(shù)影響、數(shù)據(jù)更新表現(xiàn)、范圍查詢表現(xiàn)和KNN 查詢表現(xiàn)。

1) 實(shí)驗(yàn)設(shè)置

本文使用了如下的3 個空間數(shù)據(jù)集作為測試數(shù)據(jù)集。

①Imis-3months 由專注于 AIS 技術(shù)和公共信息系統(tǒng)的公司 IMIS Hellas S.A.收集。刪除重復(fù)項(xiàng)后，保留106 700 263 條記錄。

② OpenStreetMap（OSM）[28]由英國 Steve Coast 于 2004 年創(chuàng)建。本文從 OpenStreetMap 上獲取了美國本土各類建筑、商店等標(biāo)簽的地理信息，去重后包含2 490 799 條記錄。

③Uniform 是通過對一定區(qū)域內(nèi)均勻分布的數(shù)據(jù)進(jìn)行隨機(jī)采樣產(chǎn)生的數(shù)據(jù)集，去重后的數(shù)據(jù)為20 000 000 條。

對比模型。為了驗(yàn)證本文提出的動態(tài)數(shù)據(jù)分段算法DDSA 和QML 混合空間索引的有效性，本文設(shè)計(jì)了如下的實(shí)驗(yàn)：將本文的DDSA 與傳統(tǒng)的FSW算法進(jìn)行比較，將QML 索引與4 種現(xiàn)有的索引R*-tree[13]、KD-tree、Quad-tree、UB-tree 進(jìn)行對比實(shí)驗(yàn)。

評估指標(biāo)。在數(shù)據(jù)分段算法實(shí)驗(yàn)中本文比較了FSW 算法和DDSA 在不同數(shù)據(jù)集下的表現(xiàn)。使用3個度量來評估數(shù)據(jù)切分算法的性能：平均誤差A(yù)verage Error、分段數(shù)量Number、算法耗時Time。

在空間索引對比實(shí)驗(yàn)中本文使用2 個度量來評估方法的性能：內(nèi)存空間占用Size、索引操作耗時Time。對于每個數(shù)據(jù)集本文隨機(jī)生成5 000 個查詢矩形R和5 000 個KNN 查詢點(diǎn)K，然后計(jì)算出每個索引類型進(jìn)行查詢操作的平均值并進(jìn)行比較。

2) 數(shù)據(jù)分段算法對比實(shí)驗(yàn)

數(shù)據(jù)分段算法的效果與置信區(qū)間設(shè)置和數(shù)據(jù)集大小相關(guān)。為了綜合評估FSW 算法和DDSA，本文在3 個空間數(shù)據(jù)集Imis-3months、OSM、Uniform 上分別選取記錄數(shù)為{2 000,4 000,6 000,…,50 000,60 000}的測試集合M={m0,m1,…,m11}，在每個測試集mi上設(shè)置置信區(qū)間{5,10,15,20,25,30}進(jìn)行多次實(shí)驗(yàn)，

最后取平均值作為測試集mi的實(shí)驗(yàn)結(jié)果。在生成測試數(shù)據(jù)集時，本文按照四叉樹劃分算法進(jìn)行等比例劃分以更符合實(shí)際情況。通過比較2 種算法在不同數(shù)據(jù)集上的平均誤差、分段數(shù)量和算法耗時來評估算法的性能。

實(shí)驗(yàn)結(jié)果如圖6 所示。從圖6(a)中可以看出，DDSA 比FSW 算法平均誤差要小，經(jīng)測算平均可以減少12%～17%的誤差。這是因?yàn)镈DSA 采用分段線性函數(shù)和二階多項(xiàng)式函數(shù)對不同分布特征的數(shù)據(jù)分別進(jìn)行擬合，更貼合數(shù)據(jù)實(shí)際分布規(guī)律?？s小平均誤差可以減少Q(mào)ML 索引中間查詢結(jié)果隊(duì)列的數(shù)量，優(yōu)化查詢速度。

從圖6(b)中可以看出，DDSA 相比于FSW 算法可以有效減少分段函數(shù)的個數(shù)，測試數(shù)據(jù)集越大，DDSA 效果越好。經(jīng)測算DDSA 可以平均降低7%～10%分段數(shù)。減少分段數(shù)量可以有效降低索引的存儲空間和維護(hù)成本，同時也可以更快地查找到目標(biāo)數(shù)據(jù)的本地模型，從而加快索引速度。

從圖6(c)中可以看出，DDSA 的時間消耗要比FSW 算法多，平均會增加13%～17%的耗時。這是因?yàn)镈DSA 需要先進(jìn)行線性函數(shù)的驗(yàn)證，如果不符合線性分布會再進(jìn)行二階多項(xiàng)式函數(shù)的驗(yàn)證，所以會不可避免地帶來時間的損耗。

圖6 FSW 和DDSA 平均誤差、分段數(shù)量、算法耗時比較

在QML 檢索應(yīng)用中，對生成的數(shù)據(jù)分段先通過查找算法（以二分查找為例）找到對應(yīng)的分段函數(shù)，然后通過該函數(shù)推測數(shù)據(jù)可能的位置，最后根據(jù)誤差閾值進(jìn)行校驗(yàn)（±ε）得到可能的結(jié)果隊(duì)列。DDSA 相比于FSW 算法對QML 索引檢索速度提高10%～13%。為了保證QML 索引性能，單元格最大閾值Cell_max_count 應(yīng)設(shè)置在[10 000,30 000]范圍內(nèi)，過大或者過小都會降低索引性能。QML 索引的構(gòu)建支持并發(fā)操作，當(dāng)數(shù)據(jù)集比較大時，可以通過適當(dāng)增加計(jì)算資源（1.13～1.17 倍）采用多線程的方式緩解DDSA 的算法耗時。

3) 參數(shù)影響

影響QML 索引性能的參數(shù)包括單元格最大閾值Cell_max_count 和本地模型的置信區(qū)間ε。為了研究這2 個參數(shù)對QML 索引空間大小、索引初始化時間和數(shù)據(jù)檢索時間的影響，本文設(shè)計(jì)如下實(shí)驗(yàn)：從公開數(shù)據(jù)集Imis-3months 中隨機(jī)選取40×106條記錄作為測試集，將QML 的索引單元格最大閾值Cell_max_count 設(shè)置在[2 048,63 488] 范圍內(nèi)，將本地模型置信區(qū)間ε設(shè)置在[10,100]范圍內(nèi)，進(jìn)行多次實(shí)驗(yàn)后取平均值作為實(shí)驗(yàn)的最終結(jié)果。

實(shí)驗(yàn)結(jié)果如圖7 所示。從圖7 中可以看出，QML單元格最大閾值Cell_max_count與QML索引空間大小成反比，與QML 索引初始化時間成正比，對QML檢索時間影響不大。這是因?yàn)殡S著Cell_max_count的增大，QML 索引的葉節(jié)點(diǎn)數(shù)量隨之減少，所以需要的存儲空間變小。但是每個單元格cell 需要花費(fèi)更多的時間構(gòu)建本地模型，葉節(jié)點(diǎn)初始化和更新維護(hù)成本也會隨之上升。當(dāng)Cell_max_count 增加時，QML 索引的本地模型集合L也會變大，但是QML的中間節(jié)點(diǎn)減少，所以整體的檢索速度變化不大。

圖7 QML 參數(shù)影響三維立體

QML 檢索時間和初始化時間隨ε的增加逐漸波動上升。QML 索引空間大小隨ε增加逐漸下降。當(dāng)ε增加時，QML 索引本地模型的準(zhǔn)確率會逐漸下降，這就使本地模型推算的結(jié)果隊(duì)列增加，因此QML 需要花費(fèi)更多的時間對結(jié)果隊(duì)列進(jìn)行校驗(yàn)，導(dǎo)致檢索速度成本上升。同時隨著ε的增加，QML 的單位模型可以容納更多的數(shù)據(jù)量，使本地模型集合的分段數(shù)量減少，因此可以加快分段函數(shù)檢索速度，減少模型集合空間大小。QML 索引準(zhǔn)確率的影響要比分段數(shù)量帶來的影響要大，這就使QML 檢索時間和初始化時間隨著ε的增加呈現(xiàn)逐漸波動上升，QML 索引空間大小隨著ε的增加逐漸下降。

綜合來看，QML 的索引參數(shù)Cell_max_count和ε設(shè)置應(yīng)充分考慮QML 索引的具體應(yīng)用場景。如果應(yīng)用場景對索引空間占比要求較高，應(yīng)適當(dāng)調(diào)大2 個參數(shù)，如果對索引更新性能要求較高，應(yīng)適當(dāng)調(diào)小2 個參數(shù)。本文后續(xù)的實(shí)驗(yàn)中QML 索引最大單元格閾值設(shè)置為20 000，本地模型置信區(qū)間ε設(shè)置為10。

4) 數(shù)據(jù)更新表現(xiàn)

為了比較 QML 索引與傳統(tǒng)的數(shù)據(jù)索引R*-tree、KD-tree、Quad-tree、UB-tree 在數(shù)據(jù)更新時的性能表現(xiàn)，本文設(shè)計(jì)如下實(shí)驗(yàn)：從數(shù)據(jù)集Imis-3months、Uniform 中按照區(qū)域選取記錄數(shù)為4×106、8×106、12×106、16×106、20×106的數(shù)據(jù)構(gòu)成測試數(shù)據(jù)集D={d0,d1,d2,d3,d4}，對于每個數(shù)據(jù)集d選取其中50%構(gòu)建初始數(shù)據(jù)集I，另外的50%作為額外的數(shù)據(jù)集E插入索引中。從I∪E中隨機(jī)抽選50%的點(diǎn)作為要刪除的數(shù)據(jù)集D。以上3 種配置上進(jìn)行實(shí)驗(yàn)。Configuration Init 為初始化構(gòu)建實(shí)驗(yàn)，使用I來構(gòu)建所有的5 個索引。Configuration AI 為插入測試實(shí)驗(yàn)，使用E來進(jìn)行插入操作。Configuration AD 為刪除測試實(shí)驗(yàn)，使用I構(gòu)建索引并插入E后，刪除D中的數(shù)據(jù)。

實(shí)驗(yàn)結(jié)果如圖8 所示。在Configuration Init 實(shí)驗(yàn)中，所有的索引結(jié)構(gòu)耗時都隨著數(shù)據(jù)量的增加呈線性增長。當(dāng)數(shù)據(jù)量激增時，Quad-tree 的初始化性能會降低很多。除了Quad-tree，QML 索引耗時始終少于其他索引結(jié)構(gòu)。在 Configuration AI 和Configuration AD 實(shí)驗(yàn)中，QML 索引呈現(xiàn)出近似O(1)的時間復(fù)雜度變化趨勢，除Quad-tree 外的其他索引呈現(xiàn)O(n) 的線性變化。因?yàn)镼ML 使用了四叉樹作為中間節(jié)點(diǎn)，所以QML 索引與Quad-tree 的數(shù)據(jù)更新操作效率相近。與最典型的樹形索引R*-tree 對比，在Configuration Init 中，QML 索引平均耗時減少40%；在Configuration AI 中，QML索引平均耗時減少約80%；在Configuration AD 中，QML 索引平均耗時減少40%～60%。

圖8 數(shù)據(jù)更新處理耗時比較

圖9 顯示了5 個索引結(jié)構(gòu)在不同數(shù)據(jù)集下的內(nèi)存消耗。從圖9 中可以看出，QML 索引相比于傳統(tǒng)的索引結(jié)構(gòu)，存儲相同的數(shù)據(jù)量時可以占用更少的內(nèi)存空間。而且隨著數(shù)據(jù)量的增加效果越明顯。相比于R*-tree，平均可以減少約33%的存儲空間。

圖9 索引內(nèi)存消耗比較

5) 范圍查詢表現(xiàn)

為了比較QML 索引與4 個傳統(tǒng)索引范圍查詢的性能，本文設(shè)計(jì)如下實(shí)驗(yàn)：對于每個數(shù)據(jù)集本文隨機(jī)生成5 000 個數(shù)據(jù)點(diǎn)，并構(gòu)建查詢矩形R，分別使用5 個索引進(jìn)行點(diǎn)查詢和范圍查詢，記錄耗時。

實(shí)驗(yàn)結(jié)果如圖10 所示。從圖10 中可以看出，QML 索引在點(diǎn)查詢方面呈現(xiàn)出相當(dāng)大的優(yōu)勢。在范圍查詢中與其他索引基本持平。這是因?yàn)镼ML索引cell 的本地模型在推測目標(biāo)數(shù)據(jù)位置時存在一定的誤差（這也是需要設(shè)置置信區(qū)間的原因）。誤差的存在導(dǎo)致QML 索引必須對模型檢索的結(jié)果進(jìn)行遍歷校驗(yàn)。當(dāng)檢索的矩形區(qū)域范圍擴(kuò)大時，包含的數(shù)據(jù)點(diǎn)也會增多，QML 索引本地模型檢索出的數(shù)據(jù)量也會增多，因此需要花費(fèi)更多的時間進(jìn)行數(shù)據(jù)校驗(yàn)。因?yàn)辄c(diǎn)查詢過程只需要檢索一個有效數(shù)據(jù)，所以QML 本地模型推算到的數(shù)據(jù)誤差也就能保證在[?ε,ε]范圍內(nèi)。當(dāng)QML 索引本地模型檢索的數(shù)據(jù)結(jié)果長度小于傳統(tǒng)樹形索引結(jié)構(gòu)需要遍歷的深度時，QML 索引就能表現(xiàn)出優(yōu)于傳統(tǒng)樹形索引的性能。

圖10 點(diǎn)查詢和范圍查詢比較

6) KNN 查詢表現(xiàn)

對于每個數(shù)據(jù)集，本文隨機(jī)生成5 000 個KNN查詢點(diǎn)K，然后在索引QML、R*-tree 和KD-tree進(jìn)行檢索，記錄返回的時間。最后對所有的檢索結(jié)果取平均值。

實(shí)驗(yàn)結(jié)果如圖11 所示。從圖11 中可以看出，QML 索引的KNN 查詢結(jié)果相比于R*-tree 和KD-tree 不是很穩(wěn)定。原因在于QML 索引的KNN查詢性能與數(shù)據(jù)分布特征有關(guān)。QML 索引的KNN查詢算法引入了空間密度的概念，通過計(jì)算最小單元格cell 的均勻空間密度計(jì)算初始空間距離δ0。當(dāng)單元格cell 內(nèi)的數(shù)據(jù)有較大數(shù)據(jù)偏移時，會導(dǎo)致初始的空間距離δ0計(jì)算不精確，從而增加查詢周期。同時cell 的大小也會對空間密度產(chǎn)生一定影響。如果Cell_max_count 偏大，必然會導(dǎo)致單元格空間密度的失真。如何增加QML 索引KNN 查詢的穩(wěn)定性是接下來的工作重點(diǎn)之一。

圖11 KNN 查詢比較

7.3 高維空間的拓展

本文提出的QML 索引可以很容易拓展到n維空間領(lǐng)域。對于n維數(shù)據(jù)集可以使用2n叉樹代替原有的四叉樹結(jié)構(gòu)，例如三維數(shù)據(jù)可以使用八叉樹代替四叉樹。使用n維子空間space 作為葉節(jié)點(diǎn)存儲單位，space 存儲單位閾值的數(shù)據(jù)。Z順序曲線變換可以將n維數(shù)據(jù)降維到一維。DDSA 可以根據(jù)數(shù)據(jù)的分布規(guī)律增加多項(xiàng)式函數(shù)的類型以適應(yīng)更復(fù)雜的曲線，比如三階多項(xiàng)式函數(shù)。

8 結(jié)束語

在本文中提出了一種新的空間數(shù)據(jù)學(xué)習(xí)索引結(jié)構(gòu)——QML。通過本文設(shè)計(jì)的動態(tài)數(shù)據(jù)分段算法DDSA，結(jié)合四叉樹和Z順序曲線構(gòu)建的QML 索引可以利用空間數(shù)據(jù)分布規(guī)律優(yōu)化檢索速度。DDSA 保證了通過一次性的數(shù)據(jù)遍歷構(gòu)建索引模型。通過引入四叉樹和Z順序曲線，以cell 單元格為最小單位訓(xùn)練本地模型保證了單位索引相互之間的獨(dú)立性。QML 索引在存儲空間和查詢速度上都達(dá)到了一個理想的效果，并能夠靈活快速地實(shí)現(xiàn)索引構(gòu)建和更新。QML 采用四叉樹結(jié)構(gòu)作為內(nèi)部節(jié)點(diǎn)，因此可以進(jìn)一步支持使用壓縮方案與節(jié)點(diǎn)級壓縮技術(shù)來減少索引的大小。它是學(xué)習(xí)索引在空間數(shù)據(jù)集上的一種新的嘗試。