一種基于混合索引的最近鄰查找方法

彭永鑫，羅英

（1.商洛學院 數學與計算機應用學院/秦嶺康養大數據陜西省高校工程研究中心,陜西商洛 726000；2.中國兵器工業信息中心，北京海淀 100089）

數據庫系統中，一般使用索引技術來提升數據的存儲性能。數據庫系統通常把磁盤作為持久性的存儲設備。然而使用磁盤會帶來較高的訪問延遲，磁盤輸入和輸出次數的降低成為提高數據庫性能的重要指標。如何高效地在磁盤中進行數據檢索成為數據庫系統中被人們所關注的問題。傳統方法通常從改進查找過程及更快命中數據兩個角度來提高范圍查找效率，但只能在一定程度上降低維度和數據量的增加對查找效率所帶來的影響，所能取得的效果有限。作為樹型索引結構的代表，KD[1]樹由于具有準確度高、對異常數據不敏感和查找準確等優點廣泛應用在最近鄰查找之中。然而，在大數據環境下，傳統的索引都面臨諸如空間占用率高、查找過程需要多次間接搜索等問題，影響到了查詢性能。尤其是樹形結構，隨著實際應用中數據維度的不斷升高，在進行精確查找的過程中，會產生“維度災難”[2]，使得搜索變為線型掃描。找到一種既能提高索引效率，同時又能滿足一定索引精度的算法，成為新的研究方向。

隨著人工智能的發展，研究人員開始使用機器學習技術來提高數據庫的索引性能。關于可學習索引（learned index）[3]的工作為索引結構的研究開辟了新的方向。樹型索引結構例如B樹，可以被認為是一棵把鍵映射到索引條目排序數組中相應位置的回歸樹。這項工作開啟了用基于數據分布構建的學習模型替換現有索引樹可能性的研究，提出的RM-Index[3]在搜索性能和索引空間開銷方面都優于傳統的B樹。

在可學習索引中，可以把索引本身當作一個機器學習模型。無論是B樹還是可學習索引模型，輸入值都為一個待查找的鍵。不同之處在于B樹通過搜索查找，會得到這個鍵所在記錄的位置。而可學習索引模型在待查找的鍵輸入后，經過神經網絡模型的一系列運算，會輸出一個包含最大誤差和最小誤差的區域，并能在這個誤差區域內使用二分法找到記錄的確定位置。傳統的索引結構往往沒有考慮數據的分布，而可學習索引利用機器學習進行模型的構建，在訓練的過程中能夠通過不同層級的神經網絡得到數據的分布信息。

Peng等[4]研究發現，相對于傳統的KD樹，使用基于可學習索引的可學習KD樹模型可以有效地提高最近鄰查找的查找效率。本文在可學習的KD樹[4]的基礎上，提出一種基于混合索引的最近鄰查找方案。混合索引將傳統KD樹在查找精度和可學習KD樹在查找效率上的優勢相結合，能夠根據對查找效率和查找精度的不同要求，更加靈活地解決空間中的最近鄰查找問題，并表現出較好的試驗結果。

1 KD樹與混合索引

1.1 KD樹及其改進

KD樹的概念自從提出以來，就被廣泛應用于最近鄰查找之中，用來解決在k維數據空間中如何為數據集建立索引的問題。為了在已知的樣本空間中高效地查找到輸入點的最近鄰點，通常采取建立索引的方式，“以空間換時間”。KD樹采用分治法的思想，利用已有數據對k維空間進行切分。作為KD樹的改進，Ball[5]樹中劃分特征空間后形成的超矩形體改為超球體，提高了查找效率。然而，樹形結構需要對空間進行細分，對可能是精確的近鄰點都要進行對比計算，會占用較高的計算資源。因此，Zhou等[6]利用了GPU的加速功能，讓KD樹在GPU上運行，目的是為了提高KD樹的運算速率。其他一些方法也能在一定程度上解決由于維度升高造成的影響，但所能達到的效果有限。

1.2 可學習索引

RMI[3]采用了類似B樹的分層機器學習模型來代替傳統的索引結構，構建了一個層次化的模型，如圖1所示。除去第一層外，每一層都由多個小模型構成，每一層模型都和上一層模型互相關聯，上一層模型的預測結果將會決定接下來一層的數據如何進行劃分。每一層模型都會縮小查找范圍，直到最底層得到記錄位置的最終預測。由于誤差的存在，一般情況下還需要使用二分法定位記錄的精確位置。相對于傳統的B樹，可學習索引在查找性能和減少內存占用上有了較大的提升。除了一些專注于可學習索引模型本身的研究，例如Xindex[7]和Colin[8]外，還有一些研究將注意力集中在多維范圍的可學習索引上[9-10]。官嘉林等[11]研究了內存預分配策略，較好地降低了內存缺頁中斷率，提高了可學習索引的性能。

2 混合索引的構建

混合索引模型由可學習索引和傳統KD樹兩部分構成。可學習索引部分通過構建機器學習模型，來代替傳統索引結構中的查找和計算部分?？梢詫⑼ㄟ^索引進行最近鄰查找的過程看作是一個機器學習中的分類任務。在最近鄰查找中，輸入值和其所對應的最近鄰點存在聯系，這種聯系以距離的形式體現，距離越接近的，聯系越緊密，可以認為是進行聚類的過程。在構建模型的時候，采用監督學習的方式。模型訓練的過程如下：對于處理好的數據集，首先將其構建成一棵KD樹，隨后，產生一系列隨機數作為KD樹的索引值，即為標簽一，與構成KD樹的每一個節點相對應。接著，通過KD樹得到訓練集和測試集的最近鄰點，并將所對應的最近鄰點轉化成為索引值，即為標簽二。標簽二就是訓練集和測試集的標簽。準確率定義為正確查找到真實k近鄰點的所有數據占所有待查詢數據的比值。

模型訓練階段的算法如Algorithm 1所示：

影響可學習索引運行速度的一個重要因素是神經網絡的層數。一般來說，隱藏層的數目越多，提取到的特征就會越準確，整個神經網絡的誤差就會越低，從而讓精度得以上升。然而，當層數增加時，會使得總的參數量增加，導致神經網絡更加復雜。同時也可能會使神經網絡的訓練出現過擬合現象，訓練時間也會變長。為了使神經網絡的性能得到一定程度的保證，同時保證模型的泛化能力，盡量避免過擬合的發生，在保證準確率的基礎上，盡可能使用較少的神經網絡層數。

使用KD樹進行最近鄰查找時，主要包含兩個部分：首先是把最近鄰點的葉子節點當作待查找點的近似鄰最近點。其次是進行回溯操作，以待查找點和最近鄰的近似點的距離沿樹根部進行回溯和迭代。一般來說，KD樹能夠有效降低查找的次數。但是在某些場景中，待查詢數據點所在的位置會需要在另外一棵子樹上進行查找，造成查找次數增加，從而降低了查找的效果。隨著數據維度的升高，使用KD樹進行最近鄰查找的性能會明顯降低。通常情況下KD樹在20維以內的數據集上較為有效。

在使用KD樹進行最近鄰查找的過程中，需要經過大量的回溯操作和距離計算，從而得到精確的結果。對于可學習索引來說需要做的是將這些回溯和計算用神經網絡進行代替，同時輔以少量的計算和排序，在提高神經網絡準確性的基礎上，盡量得到相同或相似的結果。Peng等[4]詳細介紹了基于可學習索引的可學習KD樹的構建過程和在最近鄰查找中相對于傳統KD樹的優勢。

使用基于神經網絡的可學習索引方法，利用神經網絡并行計算的優勢，可以有效地降低運算過程所花費的時間。同時，神經網絡模型還可以通過設計更好的網絡結構、降低參數數量等方法進行改進和優化，在確保模型準確率的情況下提高模型的運算速度。然而，使用這種方法，往往難以達到100% 的準確率。雖然使用傳統的樹型結構查找更為精確，但在查找速度上容易受到較多因素的制約。因此，將二者結合，通過構建混合索引，發揮兩種方法各自的優勢，有理由相信會取得更好的效果。

混合索引的工作流程如圖2所示。對于原始的KD樹，首先利用可學習索引，使用神經網絡進行訓練。隨后，把構成KD樹的數據點一分為二，并使用任意一半的數據點重新構建一棵KD樹。對于待查找的輸入數據，同時輸入神經網絡模型和新構建的KD樹之中，使之并行計算。兩者都輸出k個近鄰點。接著，將二者輸出的結果進行混合，得到2k個近鄰點，這2k個近鄰點中包含了正確的k個近鄰點。最后，對這2k個點相對于輸入點的距離進行排序，根據k值得到最終的k近鄰點。

圖2 混合索引的工作流程

對于一條輸入數據，假設使用KD樹進行k近鄰查找所需時間為t1，使用一半節點構成的KD樹進行查找所需的時間為t2，使用神經網絡查找所需要的時間為t3，后續計算所需的時間為tn，準確率為acc1。使用混合索引時后續產生的計算量的用時為tmix，總的準確率為acc2。一般來說，使用KD樹進行k近鄰查找需要花費的時間最長。使用混合索引時，要對2k個數據進行計算和排序，而使用可學習的KD樹，需要計算和排序的數據個數為k，因此使用混合索引產生的計算量比可學習KD樹所產生的計算量要大，花費的時間也會更多。即tn

傳統KD樹是精確查找，一般情況下，使用一棵構建好的節點數為初始節點數一半的新KD樹，會使得整個查找結果準確率提高（因為對這一部分數據，得到的結果是準確的）。因此，使用混合索引，相對于使用可學習KD樹進行k近鄰查找，在查找時間增加的情況下，一般都會獲得準確率的提升：

由于使用可學習KD樹模型所花費的時間一般比傳統KD樹要低，而使用部分節點構成的KD樹比使用所有節點構成的KD樹進行k近鄰查找所花費的時間也要低，所以相對于單一的使用可學習KD樹模型，會在原本運算速度較快但準確率較低的情況下，犧牲一些運算時間以達到精度上的提高。在合適的情況下，混合索引的方案應該是可行的。

3 結果與分析

將通過試驗來評估混合索引的性能，并與傳統KD樹和可學習KD樹在最近鄰查找的性能上進行對比，從而驗證使用混合索引進行最近鄰查找的可行性。試驗使用的框架為Keras。Keras是一個使用python實現的高度模塊化的神經網絡組件庫，提供了許多API模塊封裝了來自TensorFlow的諸多小組件，作為用戶，只需要將API構建的模塊排在一起就可以設計出各種類型的神經網絡。試驗中所使用的Keras版本為2.2.4。試驗在一塊NVIDIA GTX1080Ti 11G GPU上進行訓練，采用的編程語言及版本為Python 3.6.5。

試驗數據集采用不同數據量和不同維度組合的生成數據集。該數據集滿足正態分布，數據量n為10萬條數據，數據的維度d分別為10維、20維、50維。從查找準確率和查找時間兩個角度來評價模型的性能，可以認為傳統KD樹的查找準確率為100% 。可學習索引的神經網絡模型采用全連接網絡，神經網絡的層數分別為5層、6層和7層，所使用的激活函數為Adam。首先驗證數據集在可學習KD樹模型上所能取得的效果，隨后對準確率較低的試驗組使用混合索引模型進行改進。采用10次試驗結果的平均值作為最終的試驗結果，如圖3所示。實線部分為可學習KD樹的試驗結果，虛線部分為經過混合索引模型改進后的結果。

圖3 可學習索引模型和混合索引模型的準確率

從圖3實線部分可以看出，使用可學習索引模型進行最近鄰查找，查找的準確率隨著維度的升高而降低。當維度較低，為10維時，無論神經網絡的層數如何，模型的查找精度均表現得較好，準確率均在97% 以上。當維度為20維時，準確率開始下降，層數為6層時準確率低至90.3% 。當維度為50維時，準確率出現了明顯的下降，最低至90% 以下。因此，在維度為20維，層數為6層和維度為50維的情況下，使用混合索引模型進行改進，結果如圖3虛線部分所示。可以看到，經過混合索引模型的改進后，查找的準確率有了一定的提升，分別由90.3% ，88.6% ，90.1% ，92.3% 提高到了97.9% ，94.2% ，96.5% ，95.1% ，準確率分別提升了7.6% ，5.6% ，6.4% ，2.8% 。

圖4展示了在20維和50維的情況下查找時間的變化?？梢钥吹?，無論是可學習索引模型還是混合索引模型，其查找時間相對于KD樹都有較為明顯的優勢，查找時間隨著神經網絡層數的增加而增加。使用混合索引模型改進后，相對于可學習索引模型，查找時間略有增加，分別由8.9，17.5，18.1，22.3 s增加到 12.5，20.3，22.6，25.9 s。

圖4 KD樹可學習索引模型和混合索引模型運行時間的對比

總的來說，相對于單一使用KD樹或者可學習KD樹模型，混合索引能夠綜合兩種方法的優勢，實現了查找效率和查找時間的平衡。即相比于單獨使用可學習索引模型，使用混合索引時，付出了一定的查找時間增加的代價（這個代價相對于使用傳統KD樹進行最近鄰查找所花費的時間來說是比較小的），可以獲得準確率的進一步提升。極端的狀況是，正確的k近鄰點全都沒有分布在新構成KD樹的數據中，則混合索引從準確率上退化至使用神經網絡，時間上相比神經網絡反而花費更長。在實際運用的過程中，可以根據對準確率和查找時間的不同需要，選擇不同的方式進行最近鄰查找。

4 結語

大數據時代，數據檢索的快慢是衡量存儲系統性能的一個關鍵因素。傳統方法的查找結果通常較為精確但檢索效率較低。為了解決這個問題，Kraska等[3]提出了可學習索引模型，在提高查詢效率和降低內存占用上取得了良好的效果。但在查找效率獲得較大提升的情況下，需要進一步提高查找的準確率。不足之處在于新構建KD樹的節點數目、神經網絡層數和節點數目的選擇都是基于經驗等。未來，將會從理論的角度出發，研究在更高維度和實際數據下該算法所能獲得的效果。