一種基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法

彭永鑫

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛 726000）

近年來(lái)，高維度數(shù)據(jù)越來(lái)越廣泛地應(yīng)用于數(shù)據(jù)倉(cāng)庫(kù)[1]、信息檢索和數(shù)據(jù)挖掘等領(lǐng)域。隨著數(shù)據(jù)量不斷增加，如何在海量數(shù)據(jù)中進(jìn)行高效和有效地檢索，查找到所需要的數(shù)據(jù)，成為人們?nèi)找骊P(guān)注的問(wèn)題。范圍查找是數(shù)據(jù)應(yīng)用中經(jīng)常使用的檢索方式，即在一個(gè)數(shù)據(jù)空間中，給定一個(gè)查找對(duì)象，查詢到與查找對(duì)象的距離小于等于查詢半徑的數(shù)據(jù)點(diǎn)[2]。作為范圍查找的代表性方法，KD樹(shù)和R樹(shù)等樹(shù)型結(jié)構(gòu)查找結(jié)果雖然較為精確，但往往需要占用較大的存儲(chǔ)空間，查找效率也較低。隨著數(shù)據(jù)維度和數(shù)據(jù)量的增加，由于高維度向量的距離計(jì)算需要付出很大的代價(jià)，在查找的過(guò)程中會(huì)產(chǎn)生“維度災(zāi)難”[3]，使得查找退化為線型掃描，極大影響查詢效率。因此，有必要研究一種查找效率高，同時(shí)又不會(huì)損失過(guò)多查找精度的范圍查找算法。

研究人員通常從改進(jìn)查找過(guò)程及更快命中數(shù)據(jù)兩個(gè)角度來(lái)提高范圍查找的效率，例如Yesquel[4]、SLIK[5]和Nitro[6]。這些方法在一定程度上能降低維度和數(shù)據(jù)量的增加對(duì)查找效率帶來(lái)的影響，但所能取得的效果有限。當(dāng)前，隨著數(shù)據(jù)量的日益積累，研究者開(kāi)始探索更多的用于處理海量數(shù)據(jù)的方法。其中，使用機(jī)器學(xué)習(xí)模型替換現(xiàn)有模型的某個(gè)部分成為新興的研究方向。Kraska等[7]明確提出了可學(xué)習(xí)索引（learned index）的結(jié)構(gòu)。他們對(duì)如何使用機(jī)器學(xué)習(xí)模型代替B樹(shù)進(jìn)行了研究和討論，并采用回歸的方法，成功地將待查詢點(diǎn)定位在一個(gè)最小誤差值和一個(gè)最大誤差值之間，驗(yàn)證了可學(xué)習(xí)索引模型在B樹(shù)上的可行性。這種基于可學(xué)習(xí)索引模型的構(gòu)建方法為解決空間數(shù)據(jù)查找問(wèn)題提出了新思路。

可學(xué)習(xí)索引依托于神經(jīng)網(wǎng)絡(luò)模型，被證明是一種可行的用于代替某些索引結(jié)構(gòu)的方法。傳統(tǒng)的索引結(jié)構(gòu)按照固定的方式組織數(shù)據(jù)，并不考慮數(shù)據(jù)的分布。而利用機(jī)器學(xué)習(xí)構(gòu)建可學(xué)習(xí)的索引模型，在訓(xùn)練的過(guò)程中需要數(shù)據(jù)參與，能夠在神經(jīng)網(wǎng)絡(luò)的不同層次中獲得不同層級(jí)信息。許多傳統(tǒng)索引結(jié)構(gòu)的檢索過(guò)程，可以看作是一個(gè)回歸或者分類任務(wù)，這和神經(jīng)網(wǎng)絡(luò)能夠完成的工作沒(méi)有本質(zhì)區(qū)別。因此，使用神經(jīng)網(wǎng)絡(luò)構(gòu)建索引結(jié)構(gòu)不但具有可行性，而且相比傳統(tǒng)的索引結(jié)構(gòu)可能會(huì)有更好的性能。在可學(xué)習(xí)索引的基礎(chǔ)上，LISA[8]的提出使得查找任意空間數(shù)據(jù)集中的最近鄰成為可能；ALEX[9]重點(diǎn)研究了查找策略的優(yōu)化；Ali Hadian等[10]則討論了數(shù)據(jù)更新對(duì)模型的影響。本文借助可學(xué)習(xí)索引模型和神經(jīng)網(wǎng)絡(luò)，提出一種新的范圍查找算法，用于解決傳統(tǒng)方法所面臨的查找效率低等問(wèn)題，并初步驗(yàn)證該算法的可行性。

1 樹(shù)型結(jié)構(gòu)的構(gòu)建與范圍查找

以二維平面為例（如圖1（a）所示，其中P表示構(gòu)成KD樹(shù)的節(jié)點(diǎn)），對(duì)于一棵KD樹(shù)，每個(gè)節(jié)點(diǎn)都會(huì)保存兩個(gè)值，分別是所要分裂的維度和分裂的值。每個(gè)節(jié)點(diǎn)都會(huì)對(duì)二維空間的x軸或者y軸進(jìn)行劃分，將其余節(jié)點(diǎn)分割成兩個(gè)部分，稱為左子樹(shù)和右子樹(shù)，由矩形區(qū)域所組成。每一個(gè)由矩形構(gòu)成的區(qū)域，稱之為一個(gè)單元（由此產(chǎn)生的單元不一定有邊界）。其中根節(jié)點(diǎn)對(duì)應(yīng)的是整個(gè)空間。葉子結(jié)點(diǎn)存儲(chǔ)位置信息，非葉子結(jié)點(diǎn)用于分裂，生成的KD樹(shù)如圖1（b）所示。

圖1 二維平面KD樹(shù)

使用KD樹(shù)進(jìn)行范圍查找時(shí)，假設(shè)陰影部分（如圖2（a）所示）為查找的區(qū)域R。查找過(guò)程如圖2（b）所示。每次查找都從根節(jié)點(diǎn)開(kāi)始。給定目前分裂的維度是x軸（或者y軸），左節(jié)點(diǎn)和右節(jié)點(diǎn)分別為l和r。如果節(jié)點(diǎn)l為一個(gè)葉子節(jié)點(diǎn)，返回這個(gè)節(jié)點(diǎn)所在單元和查找區(qū)域R相交的部分。如果這個(gè)葉子節(jié)點(diǎn)所在單元里的節(jié)點(diǎn)全都包含在查找區(qū)域R內(nèi)，返回這個(gè)單元內(nèi)的所有點(diǎn)；如果該單元不與區(qū)域R有交集，繼續(xù)遞歸查詢下一個(gè)節(jié)點(diǎn)。對(duì)右節(jié)點(diǎn)r也是相同的處理方式。

圖2 KD樹(shù)的范圍查找

二維的情況下，使用KD樹(shù)進(jìn)行范圍查找，最壞狀態(tài)下的時(shí)間復(fù)雜度為tworst=O(n1/2+m)。其中，n是構(gòu)成KD樹(shù)的節(jié)點(diǎn)數(shù)量，即總的數(shù)據(jù)量的大??；m是輸出數(shù)據(jù)的大小。將二維空間推廣到d維，每次查找都會(huì)遞歸地分解到多個(gè)低維空間中去查找，容易得到其查找的時(shí)間復(fù)雜度是O((log n)d+md)。其中，md表示查找結(jié)果所組成集合的大小。其他用于范圍查找的樹(shù)形結(jié)構(gòu)，例如R樹(shù)，采用了空間分割的理念，其核心思想是聚合距離相近的節(jié)點(diǎn)并在樹(shù)結(jié)構(gòu)的上一層將其表示為這些節(jié)點(diǎn)的最小外接矩形，這個(gè)最小外接矩形就成為上一層的一個(gè)節(jié)點(diǎn)。因?yàn)樗泄?jié)點(diǎn)都在它們的最小外接矩形中，所以跟某個(gè)矩形不相交的查詢就一定跟這個(gè)矩形中的所有節(jié)點(diǎn)都不相交。在此基礎(chǔ)上，R*樹(shù)[11]作為R樹(shù)的一種變體，提升了R樹(shù)的性能。使用KD樹(shù)等樹(shù)型結(jié)構(gòu)進(jìn)行范圍查找在一定程度上能夠滿足多維查詢功能，但會(huì)受到數(shù)據(jù)維度的制約。因此，需要對(duì)現(xiàn)有的算法進(jìn)行改進(jìn)或者提出新算法，使之能夠滿足更高的查詢要求。

2 范圍查找算法的構(gòu)建與應(yīng)用

使用神經(jīng)網(wǎng)絡(luò)代替范圍查找算法，核心是使用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)模型進(jìn)行運(yùn)算，代替?zhèn)鹘y(tǒng)方法中的查找過(guò)程。使用KD樹(shù)等樹(shù)型結(jié)構(gòu)進(jìn)行范圍查找，需要經(jīng)過(guò)大量的回溯操作和距離計(jì)算才能得到精確的結(jié)果?；谏窠?jīng)網(wǎng)絡(luò)的范圍查找算法可以把這些回溯和計(jì)算過(guò)程用神經(jīng)網(wǎng)絡(luò)進(jìn)行代替，同時(shí)輔以少量的計(jì)算和排序，在提高神經(jīng)網(wǎng)絡(luò)準(zhǔn)確性的基礎(chǔ)上，盡量得到相同或相似的結(jié)果。該算法首先需要確定查找對(duì)象q(x,y)、查找半徑r和待查找區(qū)域R及數(shù)據(jù)點(diǎn)的總個(gè)數(shù)n。該算法要求所給定的待查找區(qū)域R里可能包含的最大數(shù)據(jù)點(diǎn)的個(gè)數(shù)不超過(guò)數(shù)據(jù)總個(gè)數(shù)n的a%，用數(shù)值k表示；區(qū)域R里包含的實(shí)際數(shù)據(jù)點(diǎn)的個(gè)數(shù)用k0表示。由此可知，k0總是小于等于k。

對(duì)于不同類型的索引結(jié)構(gòu)，可以根據(jù)需要將其定義為回歸或者分類任務(wù)。使用KD樹(shù)進(jìn)行范圍查找，可以看作是一個(gè)多分類的問(wèn)題，即待查詢點(diǎn)和查找到的結(jié)果有著相似的屬性，這種屬性以距離的形式體現(xiàn)：距離越接近的，可以將其視作相似的分類。在構(gòu)建可學(xué)習(xí)索引的過(guò)程中，使用監(jiān)督學(xué)習(xí)的方式。在訓(xùn)練的時(shí)候，先構(gòu)建好一棵KD樹(shù)，并隨機(jī)為這些構(gòu)成KD樹(shù)的每一條數(shù)據(jù)構(gòu)建索引值，隨后將訓(xùn)練集和測(cè)試集通過(guò)KD樹(shù)得到k近鄰點(diǎn)，將k近鄰點(diǎn)轉(zhuǎn)化為索引值，根據(jù)索引值得到訓(xùn)練集和測(cè)試集的標(biāo)簽進(jìn)行訓(xùn)練。當(dāng)模型訓(xùn)練好之后，待查詢的數(shù)據(jù)點(diǎn)通過(guò)訓(xùn)練好的模型，輸出多個(gè)可能是k近鄰點(diǎn)位置的坐標(biāo)，計(jì)算這些坐標(biāo)和待查找點(diǎn)之間的距離并排序，取前k個(gè)值，從而得到真實(shí)的k近鄰點(diǎn)。在神經(jīng)網(wǎng)絡(luò)訓(xùn)練的過(guò)程中，訓(xùn)練集為查找對(duì)象q的集合，標(biāo)簽為q的k個(gè)近鄰點(diǎn)的坐標(biāo)的索引值。準(zhǔn)確率acc定義為神經(jīng)網(wǎng)絡(luò)所找到的k個(gè)近鄰點(diǎn)占真實(shí)k近鄰點(diǎn)的比值。由于區(qū)域R里所包含的實(shí)際數(shù)據(jù)點(diǎn)的個(gè)數(shù)k0總是小于等于區(qū)域內(nèi)可能存在的最大數(shù)據(jù)點(diǎn)的個(gè)數(shù)k，所以在神經(jīng)網(wǎng)絡(luò)輸出結(jié)果后還需要進(jìn)行一次距離的計(jì)算，即計(jì)算神經(jīng)網(wǎng)絡(luò)輸出的k個(gè)數(shù)據(jù)點(diǎn)和查找對(duì)象q的距離，將這個(gè)距離和查找半徑r進(jìn)行比較以排除查找區(qū)域外的數(shù)據(jù)點(diǎn)，繼而得到區(qū)域R里的k0個(gè)數(shù)據(jù)點(diǎn)的坐標(biāo)，就是滿足范圍查找要求的數(shù)據(jù)點(diǎn)?？傮w上講，使用神經(jīng)網(wǎng)絡(luò)進(jìn)行范圍查找由兩個(gè)部分組成，分別是索引部分和計(jì)算部分。索引部分通過(guò)神經(jīng)網(wǎng)絡(luò)得到查找對(duì)象q的k個(gè)近鄰點(diǎn)的坐標(biāo)，計(jì)算部分通過(guò)距離的比較得到最終的結(jié)果，即k0個(gè)數(shù)據(jù)點(diǎn)的坐標(biāo)。因此，時(shí)間復(fù)雜度為O(1)+O(2)，分別對(duì)應(yīng)了索引部分和計(jì)算部分。在進(jìn)行范圍查找時(shí)，相對(duì)于KD樹(shù)需要進(jìn)行多次搜索計(jì)算和回溯操作，基于神經(jīng)網(wǎng)絡(luò)的范圍查找只需要進(jìn)行少量計(jì)算，從而節(jié)省了KD樹(shù)在計(jì)算和回溯中所花費(fèi)的大量時(shí)間。當(dāng)構(gòu)成KD樹(shù)的數(shù)量和維度數(shù)變大時(shí)，此算法應(yīng)該會(huì)表現(xiàn)出更明顯的優(yōu)勢(shì)。

圖3為使用神經(jīng)網(wǎng)絡(luò)的范圍查找算法示例。其中整個(gè)區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)的總個(gè)數(shù)n為100，要求待查找區(qū)域R里可能包含的最大數(shù)據(jù)點(diǎn)的個(gè)數(shù)不超過(guò)數(shù)據(jù)總個(gè)數(shù)n的20%，即k為20。查找對(duì)象q(x,y)的坐標(biāo)為（0.5,0.5），圓形區(qū)域?yàn)榇檎覅^(qū)域R，查找半徑為r，其中所包含的實(shí)際數(shù)據(jù)點(diǎn)的個(gè)數(shù)為k0，值為10，即為滿足范圍查找定義的數(shù)據(jù)點(diǎn)。索引部分得到的結(jié)果是矩形虛線區(qū)域內(nèi)數(shù)據(jù)點(diǎn)的坐標(biāo)，區(qū)域內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)為k，值為20，這些數(shù)據(jù)點(diǎn)是可能滿足查找要求的數(shù)據(jù)點(diǎn)；在計(jì)算部分中，將矩形區(qū)域內(nèi)數(shù)據(jù)點(diǎn)的坐標(biāo)和查找對(duì)象q(x,y)進(jìn)行距離的計(jì)算，距離小于r的數(shù)據(jù)點(diǎn)即為處在查找范圍里的數(shù)據(jù)點(diǎn)，從而完成范圍查找。

圖3 基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法

算法的流程如圖4所示。

圖4 范圍查找的流程圖

3 神經(jīng)網(wǎng)絡(luò)的構(gòu)建

在神經(jīng)網(wǎng)絡(luò)訓(xùn)練的過(guò)程中，神經(jīng)網(wǎng)絡(luò)的層數(shù)并不是一個(gè)固定的值。對(duì)高維數(shù)據(jù)的范圍查找來(lái)說(shuō)，數(shù)據(jù)量n的大小決定了隱藏層數(shù)的多少。使用隱藏層，是為了對(duì)數(shù)據(jù)的特征進(jìn)行提取。一般來(lái)說(shuō)，隱藏層越多，提取到的特征就會(huì)越準(zhǔn)確，整個(gè)神經(jīng)網(wǎng)絡(luò)的誤差就會(huì)越低，使得精度會(huì)越高。然而，當(dāng)隱藏層增加時(shí)，就會(huì)造成參數(shù)總量的增加，進(jìn)而讓神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)變得更加復(fù)雜，導(dǎo)致在神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過(guò)程中更容易出現(xiàn)過(guò)擬合現(xiàn)象。同時(shí)，模型訓(xùn)練的時(shí)間也會(huì)增加。對(duì)此，可以采用增加隱藏層中節(jié)點(diǎn)數(shù)的方法，盡可能避免這個(gè)問(wèn)題。相對(duì)于單純地增加隱藏層的層數(shù)，增加隱藏層中節(jié)點(diǎn)數(shù)的方法更容易獲得訓(xùn)練效果的提升。

因此，在基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法中，如何選擇隱藏層的節(jié)點(diǎn)數(shù)成為關(guān)鍵。節(jié)點(diǎn)數(shù)目不但影響著模型的運(yùn)行效率，而且當(dāng)節(jié)點(diǎn)數(shù)量過(guò)多時(shí)，還會(huì)產(chǎn)生過(guò)擬合現(xiàn)象，從而影響查找結(jié)果。然而，現(xiàn)有的研究中，并未有被廣泛用于確定隱藏層節(jié)點(diǎn)數(shù)的方法。由于不同的問(wèn)題中訓(xùn)練樣本各不相同，同時(shí)現(xiàn)在大部分方法中用于判斷節(jié)點(diǎn)數(shù)的公式都是用于面對(duì)最不利的狀況，這比較難以滿足實(shí)際情況的需要。甚至由不同計(jì)算公式計(jì)算得出的節(jié)點(diǎn)數(shù)往往還會(huì)相差很大。本文中，為了使神經(jīng)網(wǎng)絡(luò)的性能得到一定程度的保證，同時(shí)保證模型的泛化能力，避免過(guò)擬合的發(fā)生，在保證準(zhǔn)確率的基礎(chǔ)上，盡可能使用較少的隱藏層節(jié)點(diǎn)數(shù)。在滿足準(zhǔn)確率的要求后，再對(duì)層數(shù)和節(jié)點(diǎn)數(shù)進(jìn)行調(diào)整。由于隱藏層中節(jié)點(diǎn)數(shù)不僅與輸入層和輸出層的節(jié)點(diǎn)數(shù)有關(guān)，也和待處理數(shù)據(jù)的復(fù)雜程度有關(guān)，隨著試驗(yàn)數(shù)據(jù)量的增加，層數(shù)和節(jié)點(diǎn)數(shù)也會(huì)隨之增加。

4 結(jié)果與分析

在理論分析的基礎(chǔ)上，通過(guò)試驗(yàn)來(lái)評(píng)估基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法的性能，與傳統(tǒng)KD樹(shù)的表現(xiàn)進(jìn)行對(duì)比，并探索在何種情況下該算法更具優(yōu)越性。判斷的標(biāo)準(zhǔn)是查找時(shí)間和查找準(zhǔn)確率，可以認(rèn)為KD樹(shù)的查找準(zhǔn)確率為100%。查找時(shí)間指的是從查找對(duì)象q(x,y)和查找半徑r輸入到神經(jīng)網(wǎng)絡(luò)之后，再到最終查找到區(qū)域R內(nèi)符合查找要求的k0個(gè)數(shù)據(jù)點(diǎn)所花費(fèi)的時(shí)間。試驗(yàn)采用的數(shù)據(jù)集為生成的三維空間數(shù)據(jù)點(diǎn)所構(gòu)成的五組數(shù)據(jù)集，分別滿足均勻分布和正態(tài)分布。試驗(yàn)均使用python編寫的代碼在Intel（R）Core（TM）i7-4770上完成。深度學(xué)習(xí)框架則選用的是目前較為常見(jiàn)的TensorFlow，版本號(hào)為1.13。TensorFlow能便捷地對(duì)神經(jīng)網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練，而且能夠?qū)⒛Ｐ蛥?shù)和模型結(jié)構(gòu)進(jìn)行固化后保存在特定類型的文件中方便后續(xù)的預(yù)測(cè)過(guò)程。

試驗(yàn)根據(jù)數(shù)據(jù)量n的不同分為五組，每組的數(shù)據(jù)量 n 分別為 1 000，10 000，100 000，200 000，500000。前三組數(shù)據(jù)滿足均勻分布，后兩組數(shù)據(jù)滿足正態(tài)分布。神經(jīng)網(wǎng)絡(luò)由全連接層構(gòu)成，每一層使用ReLU作為激活函數(shù)。層數(shù)和節(jié)點(diǎn)數(shù)隨著數(shù)據(jù)量的增加而增加，分別為3層32個(gè)節(jié)點(diǎn)、3層64個(gè)節(jié)點(diǎn)、5層128個(gè)節(jié)點(diǎn)、6層64個(gè)節(jié)點(diǎn)和7層128個(gè)節(jié)點(diǎn)。學(xué)習(xí)率為0.000 1。為了排除偶然因素的干擾，每組試驗(yàn)的準(zhǔn)確率acc和查找時(shí)間為10次試驗(yàn)結(jié)果的平均值。給定區(qū)域R里可能包含的最大數(shù)據(jù)點(diǎn)的個(gè)數(shù)不超過(guò)數(shù)據(jù)總個(gè)數(shù)n的1%。

表1展示了基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法的性能，并在同等條件下與KD樹(shù)的表現(xiàn)進(jìn)行了對(duì)比。從試驗(yàn)結(jié)果可以看出，當(dāng)數(shù)據(jù)集滿足均勻分布時(shí)，在n為1 000的情況下，使用基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法，準(zhǔn)確率高達(dá)99.1%，但查找時(shí)間相比于傳統(tǒng)的KD樹(shù)要慢了很多，用時(shí)為1.05 s，耗費(fèi)的時(shí)間超過(guò)KD樹(shù)的2倍。當(dāng)維度和數(shù)據(jù)量都比較小時(shí)，傳統(tǒng)KD樹(shù)由于搜索和回溯的次數(shù)較少，無(wú)疑能夠表現(xiàn)出明顯的優(yōu)勢(shì)；而基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法需要花費(fèi)更多的時(shí)間在預(yù)測(cè)和距離計(jì)算上，導(dǎo)致查找時(shí)間增加。當(dāng)n為10 000時(shí)，可以看到算法的查找準(zhǔn)確率開(kāi)始下降，為96.7%；但與之相對(duì)應(yīng)的，算法所花費(fèi)的查找時(shí)間和KD樹(shù)在查找時(shí)間上的差距越來(lái)越小，耗費(fèi)的時(shí)間為KD樹(shù)的1.4倍。在維度不變的情況下，隨著數(shù)據(jù)量的增加，KD樹(shù)難以避免受到搜索次數(shù)增加的影響使其在查找效率上的優(yōu)勢(shì)逐漸縮小。當(dāng)n為100 000時(shí)，算法的準(zhǔn)確率略微降低到95.6%，然而在查找時(shí)間上已經(jīng)表現(xiàn)出了一定的優(yōu)勢(shì)，其查找所需要的時(shí)間為1.41 s，而KD樹(shù)用時(shí)為1.68 s。當(dāng)數(shù)據(jù)集滿足正態(tài)分布時(shí)，算法依然保持了較高的準(zhǔn)確率，無(wú)論是200 000還是500 000條數(shù)據(jù)，準(zhǔn)確率都在95%以上，而查找所用的時(shí)間分別為KD樹(shù)用時(shí)的66%和60%，接近KD樹(shù)查找時(shí)間的一半，表現(xiàn)出了較好的性能?？梢灶A(yù)測(cè)到的是，隨著數(shù)據(jù)量和維度的增加，有理由相信，基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法會(huì)表現(xiàn)出更強(qiáng)大的能力。

表1 基于神經(jīng)網(wǎng)絡(luò)的范圍查找算法與KD樹(shù)查找性能對(duì)比

5 結(jié)論

設(shè)計(jì)一種高效的范圍查找算法是索引領(lǐng)域的研究熱點(diǎn)。Kraska等[7]提出用可學(xué)習(xí)索引模型代替?zhèn)鹘y(tǒng)的B樹(shù)，獲得了引人注目的效果，為解決范圍查找問(wèn)題提供了新的方法和思路。本文在可學(xué)習(xí)索引的基礎(chǔ)上，提出了一種用于解決空間范圍查找問(wèn)題的算法。該算法利用神經(jīng)網(wǎng)絡(luò)訓(xùn)練模型，當(dāng)數(shù)據(jù)量較多時(shí)，在查找準(zhǔn)確率較高，且查找時(shí)間上表現(xiàn)出優(yōu)勢(shì)的前提下，一定程度上解決了傳統(tǒng)方法難以解決的由于數(shù)據(jù)量增加導(dǎo)致的查找效率下降的情況。該算法也存在一些不足，例如所取得的效果缺乏理論支撐，神經(jīng)網(wǎng)絡(luò)層數(shù)和節(jié)點(diǎn)數(shù)目的選擇都是基于經(jīng)驗(yàn)等。未來(lái)，將會(huì)從數(shù)學(xué)的角度出發(fā)，研究在更高維度和實(shí)際數(shù)據(jù)下該算法所能取得的效果。