QML：一種混合空間索引結構

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

（北京郵電大學網絡與交換技術國家重點實驗室，北京 100876）

1 引言

物聯網設備會生成大量的地理空間數據，為了有效地訪問和處理此類數據，數據庫管理員通常會采用基于樹的索引結構來提高數據分析和事務性工作負載性能[1]。為了提升數據庫的讀寫性能，整個索引通常會保存在內存中。但當數據量達到PB級別以上時，樹形索引結構會急速變大，進而嚴重侵占系統資源。研究表明，在商用內存數據庫中，索引占用了全部內存空間的55%[2]。現有的索引結構在空間大數據環境下面臨存儲空間占用高和查詢I/O 次數多的問題。

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

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

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

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

2) 提出了適用于學習索引的動態數據分段算法DDSA，該算法能夠根據局部數據分布特征選取不同的多項式函數進行擬合。

3) 設計并實現了基于QML 的范圍查詢算法和KNN 查詢算法，并通過真實數據集的測試證明QML 提供了與最優樹形索引結構相近的（點查詢性能更好）查詢性能和更新性能，大幅降低了存儲空間。

2 相關工作

空間索引是為多維數據訪問設計的數據結構。大多數空間索引是空間驅動或數據驅動的結構[13]。空間驅動的結構（如固定網格索引[14]）將空間分解為單元格，并根據幾何準則映射數據對象。數據驅動的結構（如R-tree[15]）將數據對象劃分為簇，并通過其最小外接矩形（MBR,minimum bounding rectangle）劃分空間。此外，UB-tree[16]是Z順序曲線[17]和B+tree 的組合，是一個平衡樹，數據對象按Z階存儲。實際數據具有一定的分布特點，但是傳統的數據索引結構沒有利用這一特點，因此不能發揮數據最大的作用。

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

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

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

本文針對上述的問題提出了適用于學習索引的動態數據分段算法DDSA，該算法使用分段線性函數和二階多項式函數進行分段，在保證分段效率的同時盡可能將相似數據劃分到一起。

3 QML 索引

3.1 QML 核心思想

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

圖1 OSM 美國本土地理信息數據分布規律

為了更好地擬合數據分布并支持索引的動態更新，QML 索引采用四叉樹進行數據劃分，Z順序曲線進行數據降維和有序化，最后使用動態數據分段算法DDSA 進行數據分段和模型構建。

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

在存儲優化方面，QML 索引的節點包括中間節點和葉節點，中間節點不存儲數據，葉節點存儲最大數據量閾值的數據和本地模型集合。因此QML可以顯著降低中間節點的數量，減少存儲消耗。

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

在查詢性能優化方面，QML 的混合索引結構通過減少中間節點減少了不必要的間接查詢，其模型可以根據數據分布特征選取不同的多項式函數進行擬合，減少不必要的數據分段。這些結構設計可以優化QML 索引查詢算法，提高檢索速度，同時也很好地支持了范圍查詢和KNN 查詢。

3.2 QML 構建

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

圖2 QML 構建示意

表1 參數定義

階段1數據劃分

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

步驟2如果Vcount>Cell_max_count，執行步驟3；如果Vcount≤Cell_max_count 則構建單元格cell，將cell 加入根節點并執行階段2 的步驟4；

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

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

階段2數據降維和有序化

步驟4對于單元格 cell 內任意的ki=(xi,yi)按照Z順序曲線映射函數M計算，構建三元組

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

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

階段3數據分段和模型生成

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

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

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

4 動態數據分段算法DDSA

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

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

對于每一個分段，DDSA 都會根據最大誤差閾值生成一個可行區間S。當有新的數據點加入時，算法需要結合初始點和最大誤差閾值計算新數據點的可行區間S′，當2 個區間S和S′沒有共同區域時則表示當前分段結束。

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

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

首先進行初始化操作。設置type=0，構建FSW算法可行區間Sfsw，初始數據段d包含第一個和第二個數據點，初始數據點設置初始數據段d的算法類型d.type=0。

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

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

上述過程中，SFCS 算法通過計算二次多項式函數參數的可行區間進行判斷。詳情如下。

假設XY二維坐標系中有數據點p0,p1,…,pn近似二次多項式y=ax2+bx+c分布，對于每個數據點pi=(xi,yi) 如果滿足xi

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

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

根據式(2)和式(3)可以得到參數a、b的映射關系

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

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

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

圖3 SFCS 算法示意

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

5 基于QML 的查詢處理

5.1 范圍查詢

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

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

圖4 范圍查詢示意

5.2 KNN 查詢

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

QML索引采用空間密度估算KNN查詢距離δ，將KNN 查詢轉化為遞歸和范圍查詢。QML 的KNN查詢過程如圖5 所示，通過構建矩形區域Q(qknn,δ)，將目標區域B(qknn,δ)變為Q(qknn,δ)的內切圓，將查詢B(qknn,δ)的點轉化為查詢Q(qknn,δ) 范圍內的點。通過設置初始距離δ0，逐步擴展查詢區域，直到查詢結果滿足K個或者距離大于最大查詢距離δ。

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

當要選取區域cell 內K個點時，可以根據空間密度估算距離δ0為

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

圖5 KNN 查詢示意

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

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

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

步驟3使用qknn和δ′構建查詢矩形然后計算qr′和qr ∩qr′的差集得到需要查詢的矩形區域qr″；

步驟4查詢矩形區域qr″得到可能的結果隊列result′，遍歷result′判斷數據點是否在圓形區域B(qknn,δ′)范圍內，如果在，則加入結果隊列Lr中，否則加入等待隊列Lw中；

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

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

6 QML 的數據更新

QML 的數據更新包括插入和刪除操作，相應的更新算法同時支持單點更新和批量更新。

6.1 插入

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

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

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

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

步驟3如果檢索到zvalue所在位置數值為空，則直接將kz插入該點；如果檢索到zvalue不存在，則先將該數據點加入cell 的緩存隊列中，然后執行步驟4 的分裂檢查機制；

步驟 4如果 cell 的數據量 size 大于Cell_max_count 或者緩沖區數據量大于緩沖區閾值則合并數據集，并對當前單元格cell 執行算法1 的數據劃分操作。

6.2 刪除

考慮到更新效率，QML 索引在執行刪除操作時不會直接刪除索引，而是先將該索引處的數值置空，然后執行節點合并檢查機制，當滿足條件時再對單元格cell 重新構建。

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

步驟1通過根節點查找k所在的cell，若cell不存在則直接返回false，否則執行步驟2；

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

步驟3獲取cell 的父節點pCell，如果pCell的數據量小于Cell_max_count，則將pCell 賦值給cell，并遞歸使用步驟3 進行判斷；當pCell 數據量大于Cell_max_count 時執行步驟4 并發送當前的cell；

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

7 索引評估

本節從學習多維索引對比和實驗驗證2 個方面對構建的QML 索引進行評估。

7.1 學習多維索引對比

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

表2 學習多維索引比較

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

7.2 實驗驗證

因為實驗數據的限制，本文的實驗驗證部分主要是將QML 索引和R*-tree[13]、KD-tree、Quad-tree、UB-tree 進行比較。本節實驗包括實驗設置、數據分段算法對比實驗、參數影響、數據更新表現、范圍查詢表現和KNN 查詢表現。

1) 實驗設置

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

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

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

③Uniform 是通過對一定區域內均勻分布的數據進行隨機采樣產生的數據集，去重后的數據為20 000 000 條。

對比模型。為了驗證本文提出的動態數據分段算法DDSA 和QML 混合空間索引的有效性，本文設計了如下的實驗：將本文的DDSA 與傳統的FSW算法進行比較，將QML 索引與4 種現有的索引R*-tree[13]、KD-tree、Quad-tree、UB-tree 進行對比實驗。

評估指標。在數據分段算法實驗中本文比較了FSW 算法和DDSA 在不同數據集下的表現。使用3個度量來評估數據切分算法的性能：平均誤差Average Error、分段數量Number、算法耗時Time。

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

2) 數據分段算法對比實驗

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

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

實驗結果如圖6 所示。從圖6(a)中可以看出，DDSA 比FSW 算法平均誤差要小，經測算平均可以減少12%～17%的誤差。這是因為DDSA 采用分段線性函數和二階多項式函數對不同分布特征的數據分別進行擬合，更貼合數據實際分布規律。縮小平均誤差可以減少QML 索引中間查詢結果隊列的數量，優化查詢速度。

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

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

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

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

3) 參數影響

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

實驗結果如圖7 所示。從圖7 中可以看出，QML單元格最大閾值Cell_max_count與QML索引空間大小成反比，與QML 索引初始化時間成正比，對QML檢索時間影響不大。這是因為隨著Cell_max_count的增大，QML 索引的葉節點數量隨之減少，所以需要的存儲空間變小。但是每個單元格cell 需要花費更多的時間構建本地模型，葉節點初始化和更新維護成本也會隨之上升。當Cell_max_count 增加時，QML 索引的本地模型集合L也會變大，但是QML的中間節點減少，所以整體的檢索速度變化不大。

圖7 QML 參數影響三維立體

QML 檢索時間和初始化時間隨ε的增加逐漸波動上升。QML 索引空間大小隨ε增加逐漸下降。當ε增加時，QML 索引本地模型的準確率會逐漸下降，這就使本地模型推算的結果隊列增加，因此QML 需要花費更多的時間對結果隊列進行校驗，導致檢索速度成本上升。同時隨著ε的增加，QML 的單位模型可以容納更多的數據量，使本地模型集合的分段數量減少，因此可以加快分段函數檢索速度，減少模型集合空間大小。QML 索引準確率的影響要比分段數量帶來的影響要大，這就使QML 檢索時間和初始化時間隨著ε的增加呈現逐漸波動上升，QML 索引空間大小隨著ε的增加逐漸下降。

綜合來看，QML 的索引參數Cell_max_count和ε設置應充分考慮QML 索引的具體應用場景。如果應用場景對索引空間占比要求較高，應適當調大2 個參數，如果對索引更新性能要求較高，應適當調小2 個參數。本文后續的實驗中QML 索引最大單元格閾值設置為20 000，本地模型置信區間ε設置為10。

4) 數據更新表現

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

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

圖8 數據更新處理耗時比較

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

圖9 索引內存消耗比較

5) 范圍查詢表現

為了比較QML 索引與4 個傳統索引范圍查詢的性能，本文設計如下實驗：對于每個數據集本文隨機生成5 000 個數據點，并構建查詢矩形R，分別使用5 個索引進行點查詢和范圍查詢，記錄耗時。

實驗結果如圖10 所示。從圖10 中可以看出，QML 索引在點查詢方面呈現出相當大的優勢。在范圍查詢中與其他索引基本持平。這是因為QML索引cell 的本地模型在推測目標數據位置時存在一定的誤差（這也是需要設置置信區間的原因）。誤差的存在導致QML 索引必須對模型檢索的結果進行遍歷校驗。當檢索的矩形區域范圍擴大時，包含的數據點也會增多，QML 索引本地模型檢索出的數據量也會增多，因此需要花費更多的時間進行數據校驗。因為點查詢過程只需要檢索一個有效數據，所以QML 本地模型推算到的數據誤差也就能保證在[?ε,ε]范圍內。當QML 索引本地模型檢索的數據結果長度小于傳統樹形索引結構需要遍歷的深度時，QML 索引就能表現出優于傳統樹形索引的性能。

圖10 點查詢和范圍查詢比較

6) KNN 查詢表現

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

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

圖11 KNN 查詢比較

7.3 高維空間的拓展

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

8 結束語

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