宋寶燕，孟彥偉，丁琳琳

遼寧大學(xué) 信息學(xué)院，沈陽 110036

1 引言

空間數(shù)據(jù)描述了實(shí)體對象的形狀、位置等屬性信息，廣泛應(yīng)用在社交網(wǎng)絡(luò)、物流系統(tǒng)等領(lǐng)域[1]。隨著計(jì)算機(jī)技術(shù)和位置數(shù)據(jù)采集技術(shù)的愈發(fā)成熟，位置數(shù)據(jù)的規(guī)模急劇增長，且不斷隨機(jī)變化。K最近鄰（K-nearest neighbor，KNN）查詢是空間數(shù)據(jù)查詢的重要研究內(nèi)容。

Fig.1 Take-out service圖1 外賣服務(wù)圖

圖1表示外賣服務(wù)的場景。在外賣服務(wù)中，假設(shè)d1、d2、d3配送員同時(shí)接收到store 和business 和其余很多商家發(fā)送的訂單消息，d1、d2、d3配送員如何快速地從多個(gè)消息中找出與商家距離最近的K個(gè)訂單進(jìn)行派送，即KNN查詢問題。然而，位置數(shù)據(jù)是不斷隨機(jī)變化的，該區(qū)域內(nèi)的配送員數(shù)量是隨機(jī)增加和刪除的，同時(shí)某一時(shí)間段內(nèi)，需要派送的商家和數(shù)量也是變化的。面對這些海量、隨機(jī)變化的位置數(shù)據(jù)，目前的KNN 查詢方法面臨查找和更新間的失衡問題[2-4]，不能及時(shí)地給出有效的查詢結(jié)果。如何更高效、準(zhǔn)確地處理KNN查詢成為了研究重點(diǎn)。

本文借助于Voronoi 圖[5]在空間區(qū)域劃分方面的優(yōu)勢，提出了一種基于Voronoi劃分的位置數(shù)據(jù)KNN查詢處理方法，解決了大規(guī)模位置數(shù)據(jù)的KNN 查詢問題。首先，針對數(shù)據(jù)的原有性保持問題，提出了基于K-means算法的位置數(shù)據(jù)重新分布方法，實(shí)現(xiàn)了空間數(shù)據(jù)的不完全聚類。其次，提出了一個(gè)二級空間索引結(jié)構(gòu)——VRI（VHash and VR index），包含VHash（Voronoi Hash）和VR（Voronoi and R）樹兩部分。一級索引結(jié)構(gòu)VHash 表示Voronoi 圖的直鄰，二級索引結(jié)構(gòu)VR 樹，按照各Voronoi 單元所在的最小矩形區(qū)域的重疊面積，自下而上地生成對應(yīng)的R 樹。再次，基于VRI索引結(jié)構(gòu)提出了位置數(shù)據(jù)的KNN查詢算法及動(dòng)態(tài)維護(hù)算法，采用VR樹進(jìn)行定位，VHash查找K近鄰，能夠有效地對查詢點(diǎn)定位，查找速度快。最后，針對數(shù)據(jù)更新的情況，索引結(jié)構(gòu)也能夠及時(shí)更新，在更新的時(shí)間段內(nèi)，對于位置數(shù)據(jù)隨時(shí)間變化的KNN查詢，提出了利用記錄表進(jìn)行有效查詢的方法。

2 相關(guān)工作

2.1 分布式空間索引結(jié)構(gòu)

目前，關(guān)于分布式空間索引技術(shù)的研究取得了一定的研究成果。文獻(xiàn)[6]提出了基于空間填充曲線網(wǎng)格劃分的最近鄰查詢算法，該算法解決了R樹變體中的區(qū)域重疊現(xiàn)象，但破壞了數(shù)據(jù)的原有性，未能使位置更近的中間節(jié)點(diǎn)組合，導(dǎo)致查詢結(jié)果的不準(zhǔn)確和查詢效率低。文獻(xiàn)[7]提出了基于R樹索引的內(nèi)容地址網(wǎng)絡(luò)（R-tree based index in content addressable network，RT-CAN）的空間索引結(jié)構(gòu)，即一種基于路由協(xié)議的CAN 索引技術(shù)[8]和基于R 樹的索引技術(shù)的結(jié)合體。這種空間索引結(jié)構(gòu)，在處理少量高維數(shù)據(jù)查詢時(shí)具有一定的優(yōu)勢，但是在處理海量空間數(shù)據(jù)時(shí)，存在查詢與更新失衡的問題。文獻(xiàn)[9-10]提出了并行的空間查詢處理算法，提高了查詢處理的效率，但是查詢采用自上而下地遍歷索引結(jié)構(gòu)的方法導(dǎo)致根節(jié)點(diǎn)及靠近根節(jié)點(diǎn)的中間節(jié)點(diǎn)的負(fù)載量過大的問題。文獻(xiàn)[11-12]提出了一次性的空間索引方法，使用一個(gè)分離的內(nèi)存數(shù)據(jù)結(jié)構(gòu)跟蹤這些數(shù)據(jù)的變化，通過延時(shí)更新來緩解更新的高負(fù)載問題。這兩種索引結(jié)構(gòu)都需要維護(hù)一個(gè)更新跟蹤緩沖區(qū)，該緩沖區(qū)存儲了全部數(shù)據(jù)的有序的更新，并用于緩沖區(qū)和基礎(chǔ)的空間索引結(jié)構(gòu)交換對象。文獻(xiàn)[13]提出了一種基于Voronoi的Merkel R樹(Merkel R-tree，MR-tree)索引，實(shí)現(xiàn)了區(qū)域覆蓋的最小化，但該索引在的劃分方法，未能保持?jǐn)?shù)據(jù)的原有性，中間節(jié)點(diǎn)間區(qū)域存在區(qū)域覆蓋及未能將距離近的中間節(jié)點(diǎn)區(qū)域結(jié)合的問題。

2.2 KNN查詢

KNN 查詢問題也取得了很多研究成果。文獻(xiàn)[14]提出了改進(jìn)的增量最近鄰查詢算法，該算法是通過一定的內(nèi)存資源代價(jià)，減少最近鄰居查詢索引遍歷過程中的時(shí)空運(yùn)算次數(shù)，但在復(fù)雜空間數(shù)據(jù)和高維空間中，還是具有一定的空間代價(jià)。文獻(xiàn)[15]提出了基于Δ-tree 的自底向上的KNN查詢算法，該算法使用類似Δ-tree 中節(jié)點(diǎn)生成方法確定查詢點(diǎn)在Δ-tree 中所隸屬的葉子節(jié)點(diǎn)及其所有祖先節(jié)點(diǎn)，但存在索引結(jié)構(gòu)的更新與查詢失衡的問題，并且在處理大量隨機(jī)變化的空間數(shù)據(jù)時(shí)效率較低。文獻(xiàn)[16]提出了將KNN 查詢轉(zhuǎn)換為多個(gè)區(qū)域查詢的方法，在進(jìn)行區(qū)域查詢時(shí)，利用查詢點(diǎn)與關(guān)鍵點(diǎn)間的距離逐層縮小查詢空間，提高了查詢的效率，但區(qū)域查詢的初始半徑和查詢半徑的增大速率有待進(jìn)一步提高。文獻(xiàn)[17]以Voronoi 單元代替最小邊界矩形，自下而上地生成了一種新的空間索引結(jié)構(gòu)——VR樹，避免了基于R樹及其變體空間索引結(jié)構(gòu)中的區(qū)域覆蓋問題，提高了查詢的效率，尤其是1NN 查詢，但該索引結(jié)構(gòu)適合靜態(tài)的空間數(shù)據(jù)，不適宜動(dòng)態(tài)、隨機(jī)變化的位置數(shù)據(jù)。

3 Voronoi劃分的空間索引

二級索引結(jié)構(gòu)包括VHash表和VR樹，形成了二級索引結(jié)構(gòu)——VRI。

3.1 分布式Voronoi空間劃分

3.1.1 重新分布

位置數(shù)據(jù)一般是隨機(jī)分布在若干服務(wù)器中，這種存儲沒有考慮到位置數(shù)據(jù)的相對位置、距離等，而KNN 查詢是依據(jù)位置數(shù)據(jù)的相對位置和距離完成的。為了保持?jǐn)?shù)據(jù)的原有性，即位置數(shù)據(jù)的相對位置和距離，本文對需要隨機(jī)分布的位置數(shù)據(jù)進(jìn)行重新分布。

K-means 算法[18]通常是依據(jù)位置數(shù)據(jù)間的歐式距離聚類的，聚類后可以保持這些數(shù)據(jù)間的相對位置。本文采用K-means算法聚類時(shí)，首先將具有經(jīng)緯度的位置數(shù)據(jù)映射為歐式空間數(shù)據(jù)，選擇的聚類中心個(gè)數(shù)是服務(wù)器數(shù)量S，迭代次數(shù)是依先驗(yàn)知識設(shè)定的，此迭代計(jì)算進(jìn)行聚類，聚類后，每個(gè)服務(wù)器存儲一個(gè)聚類結(jié)果與對應(yīng)的聚類中心。

仍以圖1中例子進(jìn)行說明，某一時(shí)刻，隨機(jī)選取11個(gè)有訂單需求的商家，其位置在歐式空間中的表示如圖2所示。

隨機(jī)分布的位置數(shù)據(jù)進(jìn)行重新分布前后的存儲結(jié)果，如圖3所示。

3.1.2 初始Voronoi

Fig.2 Euclidean representation of location data圖2 空間數(shù)據(jù)歐式圖

Fig.3 Schematic diagram of redistribution data圖3 數(shù)據(jù)重新分布示意圖

Voronoi 圖是依據(jù)歐式距離進(jìn)行空間區(qū)域劃分的，可將空間劃分為相鄰而互不重疊的區(qū)域，隱含地構(gòu)建了離散點(diǎn)之間的鄰近關(guān)系，可有效支持K近鄰的快速查找。本文對每個(gè)服務(wù)器上重新分布的位置數(shù)據(jù)創(chuàng)建局部Voronoi圖。

各個(gè)服務(wù)器中，這種局部Voronoi 圖的創(chuàng)建采用多核技術(shù)和改進(jìn)的掃描線算法[16]并行生成。各服務(wù)器中生成的初步局部Voronoi 圖如圖4所示。圖4中的1到11為位置數(shù)據(jù)的歐式表示，也是原始生成點(diǎn)，原始生成點(diǎn)所在的多邊形為Voronoi單元，在S1服務(wù)器中，L2、L3為S1、S2服務(wù)器的邊界點(diǎn)。

Fig.4 Initial local Voronoi diagram of each server圖4 各服務(wù)器的初始局部Voronoi圖

3.1.3 Voronoi優(yōu)化

在各服務(wù)器初步生成的局部Voronoi 圖中，沒有考慮服務(wù)器邊界點(diǎn)間的影響關(guān)系，導(dǎo)致生成的局部Voronoi圖是不準(zhǔn)確的。

為了優(yōu)化不準(zhǔn)確Voronoi 單元的數(shù)量，找出每個(gè)服務(wù)器上的聚類中心，聚類中心代表各服務(wù)器上的聚類結(jié)果，而各個(gè)服務(wù)器中的聚類中心可能是不存在的位置數(shù)據(jù)，本文選取距離聚類中心最近的位置數(shù)據(jù)代表各個(gè)服務(wù)器中的聚類結(jié)果。

定義1（近心點(diǎn)）給定各服務(wù)器重新分布的位置數(shù)據(jù)O及個(gè)數(shù)n和各服務(wù)器聚類中心C及個(gè)數(shù)s，對于各服務(wù)器任意的，即oy為近心點(diǎn)。

Voronoi 優(yōu)化的一個(gè)方面是近心點(diǎn)優(yōu)化，近心點(diǎn)優(yōu)化可以利用空間復(fù)制技術(shù)實(shí)現(xiàn)。首先，根據(jù)近心點(diǎn)生成Voronoi 邊界，S1、S2、S3服務(wù)器間的Voronoi邊界如圖5所示，再由先驗(yàn)知識設(shè)定邊界點(diǎn)到邊界的距離，即邊界距離，計(jì)算各邊界點(diǎn)到邊界的距離，得計(jì)算后的距離。將計(jì)算后的距離與邊界距離比較，當(dāng)計(jì)算后的距離小于等于邊界距離時(shí)，則將該邊界點(diǎn)復(fù)制到有影響的服務(wù)器中，在各服務(wù)器中并行地完成上述過程，即實(shí)現(xiàn)了近心點(diǎn)的優(yōu)化。優(yōu)化后的結(jié)果如圖6所示，其中下劃線標(biāo)識數(shù)據(jù)為需要復(fù)制的位置數(shù)據(jù)。

Fig.5 Voronoi boundary圖5 Voronoi 邊界

Fig.6 Close heart point optimization of data graph圖6 近心點(diǎn)優(yōu)化數(shù)據(jù)圖

Voronoi 優(yōu)化的另一個(gè)方面是不準(zhǔn)確Voronoi 單元的識別和修復(fù)，利用影響區(qū)域[18]對各服務(wù)器邊界點(diǎn)所在的Voronoi 單元進(jìn)行識別和修復(fù)，從而生成正確的局部Voronoi圖。如圖7為優(yōu)化后生成的正確的局部Voronoi圖。

Fig.7 Local Voronoi diagram of each server圖7 各服務(wù)器的局部Voronoi圖

3.1.4 局部Voronoi的直鄰表示——VHash

定義2（直鄰表示）給定一Voronoi圖VG，VG中的Voronoi 單元為VC，對于任意VC ∈VG，具有共享邊和共享頂點(diǎn)VC 的生成點(diǎn)為該VC 的直接鄰居，存儲在哈希表中。

Voronoi 圖可表示鄰居間的關(guān)系，根據(jù)優(yōu)化后正確的Voronoi 圖生成直鄰表示——VHash，作為一級索引結(jié)構(gòu)，直鄰表示不僅支持1NN查詢，還支持KNN（K≠1）查詢。

Fig.8 Voronoi schematic diagram圖8 Voronoi示意圖

由于映射快，方便查找，VHash采用Hash表進(jìn)行存儲，本文直鄰表示存儲的是具有共享邊和共享點(diǎn)的生成點(diǎn)。如圖8中，查詢點(diǎn)q為配送員的位置，其余為需要派送訂單的商家的位置，當(dāng)配送員選擇多個(gè)派送訂單時(shí)，在第二個(gè)訂單的選擇時(shí)，若只考慮共享邊為其鄰居的因素時(shí)，在o2的鄰居中，配送員位置q到o1的距離最近，因此配送員需要派送的第二單為o1，而實(shí)際存在配送員位置q到商家o4的距離小于到o1的距離。只考慮共享邊會導(dǎo)致查詢結(jié)果的不準(zhǔn)確，因此本文選取具有共享邊和共享點(diǎn)的生成點(diǎn)為直鄰判斷的依據(jù)。

表1～表3分別為各服務(wù)器中對應(yīng)的直鄰表示，在VHash 中，存儲的是Object 和Neighbors，Object 為原始生成點(diǎn)，Neighbors為原始生成點(diǎn)的直鄰。

Table 1 S1 VHash表1 S1 VHash

Table 2 S2 VHash表2 S2 VHash

Table 3 S3 VHash表3 S3 VHash

3.1.5 Voronoi劃分后的全局信息

在經(jīng)過位置數(shù)據(jù)的重新分布，初始Voronoi 圖的生成和近心點(diǎn)Voronoi 的優(yōu)化后，各個(gè)服務(wù)器完成了分布式的Voronoi劃分，各個(gè)服務(wù)器存放的信息是（重新分布后的位置數(shù)據(jù)，邊界點(diǎn)，近心點(diǎn)，VHash 表）。這些信息的全局概要，即全局信息，為各個(gè)服務(wù)器的（鄰居，近心點(diǎn)）信息。通過全局信息，獲得各服務(wù)器的相對位置和服務(wù)器間的Voronoi 邊界，方便了優(yōu)化和查找。

3.2 Voronoi劃分的R樹索引

3.2.1 Voronoi單元的最小矩形覆蓋

在正確的Voronoi圖中，找到能夠覆蓋Voronoi單元所在的最小矩形區(qū)域，并用橫縱坐標(biāo)的區(qū)間進(jìn)行表示，即Voronoi單元所在的最小矩形區(qū)域。

3.2.2 組合表示（VR）生成

定義3（組合區(qū)域）給定一Voronoi 單元覆蓋的最小矩形區(qū)域MR，將MR任意組合，將重疊面積大者任意組合，形成組合區(qū)域。

組合表示是按照Voronoi多邊形所在最小矩形區(qū)域重疊面積的大小組合生成的，而重疊面積反映了對應(yīng)Voronoi 多邊形中生成點(diǎn)間的距離關(guān)系，將重疊面積較大的區(qū)域組合，減少了組合表示的數(shù)量，并使距離近的位置數(shù)據(jù)組合在一起。

由此，在找到每個(gè)Voronoi 單元所在的最小覆蓋矩形區(qū)域后，將這些區(qū)域隨機(jī)地組合，找出這些組合區(qū)域的重疊面積，重疊面積比較大者為一個(gè)組合表示，再找出已經(jīng)生成的組合表示所在的最小覆蓋矩形區(qū)域。同樣，將這些區(qū)域隨機(jī)地組合，找出重疊面積較大的組合區(qū)域，為新生成的組合表示，以此迭代地進(jìn)行，直到新生成的一個(gè)組合表示中覆蓋了服務(wù)器中所有的原始生成點(diǎn)，由此自下而上地生成了一個(gè)二級索引結(jié)構(gòu)——VR樹，如圖9所示。

Fig.9 VR tree index structure圖9 VR樹索引結(jié)構(gòu)

VR 樹是由根節(jié)點(diǎn)、中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)組成的，其中葉子節(jié)點(diǎn)的存儲結(jié)構(gòu)為(object，VC，data)，object 為位置數(shù)據(jù)，即Voronoi 單元原始生成點(diǎn)，VC為所在Voronoi區(qū)域唯一標(biāo)識，data為Voronoi區(qū)域存儲的近似表示；根節(jié)點(diǎn)和中間節(jié)點(diǎn)的存儲結(jié)構(gòu)為(objects，child，VR，data)，objects 為組合區(qū)域的生成點(diǎn)，即組合生成點(diǎn)，child 為指向孩子節(jié)點(diǎn)指針，設(shè)定M為該節(jié)點(diǎn)存放的最大記錄數(shù)，m≤M/2為該節(jié)點(diǎn)存放的最小記錄數(shù)，則child指針的個(gè)數(shù)為[m,M]。

VR 樹的主要實(shí)現(xiàn)步驟是將數(shù)據(jù)集中的每個(gè)位置數(shù)據(jù)所在Voronoi 單元的矩形區(qū)域，與具有共享邊的Voronoi 單元所在矩形區(qū)域重疊的面積比較，選取最大的重疊面積，并記錄對應(yīng)的Voronoi單元；將所有的重疊面積快速排序，按照從大到小的順序，兩兩組合，在組合過程中，刪除已經(jīng)組合的數(shù)據(jù)，依次組合。對于每個(gè)服務(wù)器中的數(shù)據(jù)集，調(diào)用此方法，生成對應(yīng)的VR 樹。算法1表示基于Voronoi 劃分的R 樹生成算法。

算法1基于Voronoi劃分的R樹生成

輸入:各服務(wù)器中數(shù)據(jù)集Oi，總數(shù)據(jù)集O。

輸出:VR樹。

在算法1中，第3行至第6行為服務(wù)器中每個(gè)位置數(shù)據(jù)所在的矩形區(qū)域及重疊面積的初始化，時(shí)間復(fù)雜度為O(1);第7行至第17行為選取某位置數(shù)據(jù)與其具有共享邊的Voronoi單元所在矩形區(qū)域的重疊面積的最大值，并記錄其矩形區(qū)域，算法的時(shí)間復(fù)雜度為O(n)；第18行至第21行為每個(gè)服務(wù)器中所有位置數(shù)據(jù)對應(yīng)的最大重疊面積，并記錄該數(shù)據(jù)與其重疊面積最大的Voronoi 單元所在的矩形區(qū)域，完成了整個(gè)服務(wù)器中數(shù)據(jù)集的最大重疊面積。該算法整體的時(shí)間復(fù)雜度為O(n2)，第22行為快排，算法的時(shí)間復(fù)雜度為O(nlgn)，第23行至第28行為VR樹非葉節(jié)點(diǎn)和葉子節(jié)點(diǎn)的生成，算法的時(shí)間復(fù)雜度為O(n2lgn)，第29行至第31行為每個(gè)服務(wù)器中數(shù)據(jù)集的遍歷，由此整個(gè)VR樹生成算法的時(shí)間復(fù)雜度為O(n3lgn)。

3.2.3 VR全局信息

在經(jīng)過了Voronoi 單元的最小覆蓋和組合表示后，各個(gè)服務(wù)器完成了基于Voronoi 劃分的R 樹索引——VR 樹，各個(gè)服務(wù)器存放的信息是（最小矩形區(qū)域，組合區(qū)域）。這些分布信息的全局概要，即全局信息，為各服務(wù)器的根節(jié)點(diǎn)組合區(qū)域，通過根節(jié)點(diǎn)組合區(qū)域這個(gè)全局信息，獲得各服務(wù)器的最小覆蓋矩形區(qū)域。

3.3 二級索引動(dòng)態(tài)維護(hù)

在現(xiàn)實(shí)世界中，位置數(shù)據(jù)是隨時(shí)變化的，要實(shí)現(xiàn)索引結(jié)構(gòu)跟隨空間數(shù)據(jù)的實(shí)時(shí)變動(dòng)是不可能的，而且索引的創(chuàng)建也需要時(shí)間，這種現(xiàn)象在生活中也可見到，如手機(jī)地圖中人的位置信息并不是實(shí)時(shí)更新的，而是每隔一段時(shí)間更新，以此延長電池的使用壽命，因此本文每隔一段時(shí)間重新創(chuàng)建二級索引——VRI。

在位置數(shù)據(jù)變動(dòng)不大的情況下，根據(jù)位置數(shù)據(jù)的變化進(jìn)行數(shù)據(jù)的增加或刪除，在新增位置數(shù)據(jù)中，需判斷新增數(shù)據(jù)到各近心點(diǎn)的距離，以完成數(shù)據(jù)的重新分布。例如在外賣非高峰期時(shí)，因移動(dòng)位置數(shù)據(jù)變化比較小，某一時(shí)刻需要發(fā)送訂單的商家變化也不大，在偶數(shù)次索引創(chuàng)建時(shí)，可不用對發(fā)送訂單的商家進(jìn)行重新分布，只依據(jù)奇數(shù)次，即前一次索引創(chuàng)建的數(shù)據(jù)分布即可，縮短了索引的創(chuàng)建時(shí)間。算法2為索引創(chuàng)建算法。

算法2索引創(chuàng)建

輸入：數(shù)據(jù)集O。

輸出：二級索引結(jié)構(gòu)。

在算法2中，第2行為生成局部Voronoi 圖，第3行為生成VR 樹，整個(gè)索引創(chuàng)建的時(shí)間復(fù)雜度為O(n4lgn)。

4 位置數(shù)據(jù)KNN查詢

通過R 樹確定查詢點(diǎn)所在的Voronoi 單元，進(jìn)一步通過VHash 獲得KNN 查詢結(jié)果；在VHash、VR 二級索引更新期間，針對變化的位置數(shù)據(jù)，實(shí)現(xiàn)了近似查詢及精確查詢。

4.1 KNN查詢

4.1.1 查詢點(diǎn)定位

全局信息可以確定查詢點(diǎn)可能所在的服務(wù)器，而VR 樹中的組合區(qū)域可以逐步縮小查找范圍。在KNN查詢中，首先結(jié)合全局信息，利用VRI索引中的VR樹進(jìn)行查詢點(diǎn)的定位。

例如，假設(shè)服務(wù)器S1接到查詢Q（包含查詢點(diǎn)q和查詢條件），S1服務(wù)器會判斷查詢點(diǎn)q是否在本服務(wù)器中，若查詢點(diǎn)q在S1服務(wù)器中，則查詢Q在服務(wù)器S1中進(jìn)行處理；若查詢點(diǎn)q不在S1服務(wù)器中，則S1服務(wù)器將查詢Q發(fā)送至具有全局信息的服務(wù)器，該服務(wù)器將q的橫縱坐標(biāo)與存儲的各服務(wù)器的根節(jié)點(diǎn)組合區(qū)域比較，得到查詢點(diǎn)q可能所在的服務(wù)器，并將查詢Q發(fā)送至可能所在服務(wù)器，在這些服務(wù)器中，并行地遍歷VR樹，找到查詢點(diǎn)q所在的服務(wù)器，并將結(jié)果返回至全局信息服務(wù)器。

在確定查詢點(diǎn)q所在的服務(wù)器后，在該服務(wù)器中，利用VR 樹查找查詢q所在的Voronoi 單元。在確定查詢點(diǎn)q所在的Voronoi 單元時(shí)，自上而下地遍歷VR 樹。將q的橫縱坐標(biāo)與VR 樹的組合區(qū)域比較，直到遍歷整個(gè)VR樹為止。找到查詢點(diǎn)q可能所在的Voronoi單元，計(jì)算查詢點(diǎn)q到這些Voronoi單元對應(yīng)的生成點(diǎn)的距離，距離最短的生成點(diǎn)對應(yīng)的Voronoi單元為查詢點(diǎn)q所在的Voronoi單元。

4.1.2 近鄰確定

VHash 是直鄰表示，也就是生成點(diǎn)的直接鄰居，即與該生成點(diǎn)有共享邊的Voronoi單元的生成點(diǎn)。在確定查詢點(diǎn)q所在的Voronoi單元后，根據(jù)Voronoi圖中具有共享邊的Voronoi單元的生成點(diǎn)間距離最近這一性質(zhì)，可利用VHash 進(jìn)行查詢點(diǎn)近鄰的確定。針對查詢點(diǎn)q，其第一個(gè)近鄰是所在Voronoi 單元的生成點(diǎn)，而q的第二個(gè)近鄰在第一個(gè)近鄰的鄰居中，此時(shí)遍歷查詢點(diǎn)所在服務(wù)器的VHash索引，根據(jù)VHash可找出第一個(gè)近鄰的鄰居，并計(jì)算查詢點(diǎn)q到這些鄰居的距離，距離最短的為第二個(gè)近鄰，依次迭代地進(jìn)行，直到找到K個(gè)近鄰為止。算法3表示KNN 查詢算法。

算法3KNN查詢

輸入：空間數(shù)據(jù)集O，查詢點(diǎn)q，整數(shù)K，VR樹節(jié)點(diǎn)存儲的Voronoi區(qū)域G，VHash。

輸出：所有符合查詢條件的數(shù)據(jù)對象。

在算法3中，第1行到第3行為查詢點(diǎn)的定位，算法的時(shí)間復(fù)雜度為O(n3)，第4行為第1個(gè)近鄰的查找，算法的時(shí)間復(fù)雜度為O(1)，第6行到第11行為剩余K-1個(gè)近鄰的查找，算法的時(shí)間復(fù)雜度為O(n2)，因此算法的時(shí)間復(fù)雜度為O(n3)。

例如，在利用二級索引結(jié)構(gòu)進(jìn)行KNN查詢時(shí)，查詢Q：查詢點(diǎn)q(13,1),K=3。需要在已知的11個(gè)需要發(fā)送訂單的商家位置中，找出滿足該查詢條件的商家。

首先，結(jié)合VR樹進(jìn)行查詢點(diǎn)q的定位。S1服務(wù)器接到查詢Q時(shí)，S1服務(wù)器在本地將查詢點(diǎn)q的橫縱坐標(biāo)與其最小覆蓋矩形區(qū)域進(jìn)行比較，得知查詢點(diǎn)q不在本服務(wù)器中，則將查詢Q發(fā)送至具有全局信息的服務(wù)器，全局信息服務(wù)器依據(jù)存儲的根節(jié)點(diǎn)組合區(qū)域與q橫縱坐標(biāo)比較，得q在S2服務(wù)器中，將查詢Q發(fā)送至S2。

在S2接收到查詢Q后，將查詢點(diǎn)q的橫縱坐標(biāo)與VR 樹的組合區(qū)域進(jìn)行比較，自上而下地遍歷VR樹，直到遍歷結(jié)束，找到q可能在L4、L6、L11這三個(gè)生成點(diǎn)對應(yīng)的Voronoi 單元中，計(jì)算q到這些生成點(diǎn)的距離，得知q到L6距離最近，即查詢點(diǎn)q在L6這個(gè)Voronoi單元中。

在確定查詢點(diǎn)q在L6這個(gè)Voronoi單元后，利用VHash 進(jìn)行近鄰的確定。依據(jù)Voronoi 圖的性質(zhì)，查詢點(diǎn)q的第一個(gè)近鄰為其所在的Voronoi單元對應(yīng)的生成點(diǎn)L6；q的第二個(gè)近鄰在第一個(gè)近鄰的鄰居中，在S2服務(wù)器的VHash 索引中，如表2所示的VHash中，找到L6的鄰居。表2中，L6的鄰居為L4、L5、L10、L11、L8、L7，比較查詢點(diǎn)q(13,1)到這些鄰居的距離，距離最短的L11為q的第二個(gè)近鄰；同樣，q的第三個(gè)近鄰在6和11這兩個(gè)生成點(diǎn)對應(yīng)的Voronoi單元的鄰居中，即在L4、L5、L10、L7、L8、L9中，找出q到這些點(diǎn)中距離最短的L4、L8為q的第三個(gè)近鄰。由此，找到查詢點(diǎn)q(13,1)的三個(gè)近鄰，為L6、L11、L8或者L6、L11、L4。

4.2 動(dòng)態(tài)維護(hù)

4.2.1 原始生成點(diǎn)結(jié)構(gòu)擴(kuò)展

各服務(wù)器中的位置數(shù)據(jù)是隨時(shí)變化的，實(shí)時(shí)地增加或刪除，針對這些動(dòng)態(tài)變化的空間數(shù)據(jù)，要實(shí)現(xiàn)索引結(jié)構(gòu)的實(shí)時(shí)更新是不可能的，需要一個(gè)記錄表記錄t+Δt時(shí)刻，每個(gè)服務(wù)器中位置數(shù)據(jù)的增加或刪除情況。如表4為t+Δt時(shí)刻記錄表，記錄了各服務(wù)器某一時(shí)刻，需要發(fā)送訂單的商家的位置變化情況。

Table 4 Record table for location data表4 位置數(shù)據(jù)記錄表

在Δt索引更新期間，進(jìn)行查詢時(shí)，先在原索引結(jié)構(gòu)中進(jìn)行KNN查詢，再利用t+Δt記錄表和VR樹進(jìn)行近似查詢和精確查詢。

在動(dòng)態(tài)維護(hù)中，為了實(shí)現(xiàn)近似查詢和精確查詢，需要對葉子節(jié)點(diǎn)的存儲結(jié)構(gòu)擴(kuò)展，增加一個(gè)parent的指針，在回溯方法中便于找到上一層中間節(jié)點(diǎn)。

4.2.2 近似結(jié)果

當(dāng)KNN查詢結(jié)果只作為對整體趨勢的一個(gè)參考時(shí)，已有的KNN查詢結(jié)果即可滿足需求，此結(jié)果為一級近似結(jié)果。

如上述例子中，KNN 查詢結(jié)果為L6、L11、L8或者L6、L11、L4，則一級近似的結(jié)果為L6、L11、L8或者L6、L11、L4。

當(dāng)依據(jù)KNN 查詢結(jié)果確定其所在的區(qū)域時(shí)，利用回溯方法找到KNN查詢結(jié)果對應(yīng)的上一層節(jié)點(diǎn)區(qū)域，判斷新增加的位置數(shù)據(jù)是否在該區(qū)域中，若在該區(qū)域，則保存，并刪除已有結(jié)果中的位置數(shù)據(jù)，找出滿足需求的一個(gè)二級近似結(jié)果。

如上述例子中，KNN 查詢結(jié)果為L6、L11、L8或者L6、L11、L4，在進(jìn)行二級近似查詢時(shí)，只需要在VR樹中找到L6、L11、L4、L8對應(yīng)的上一層節(jié)點(diǎn)區(qū) 域，得 到(S2,R1)、(S2,R2)、(S2,R3)、(S3,R1)、(S3,R2)，而新增位置數(shù)據(jù)L12(13,3)在中間節(jié)點(diǎn)(S2,R1)和(S2,R3)中，L13(17,3)在中間節(jié)點(diǎn)(S3,R1)中，刪除已經(jīng)變化的空間數(shù)據(jù)L11和L8，可得二級近似查詢結(jié)果為L8、L11、L12、L13。

4.2.3 精確結(jié)果

當(dāng)根據(jù)KNN查詢結(jié)果確定空間數(shù)據(jù)的具體位置時(shí)，如配送員在選擇派送的訂單時(shí)，需要對選擇發(fā)送訂單的商家位置有一個(gè)精確的結(jié)果時(shí)，需對KNN 查詢結(jié)果變化數(shù)據(jù)進(jìn)行查找和計(jì)算，找出滿足需求的精確結(jié)果。首先在VR樹中，利用回溯方法找到KNN查詢結(jié)果對應(yīng)的上一層節(jié)點(diǎn)區(qū)域，判斷新增加的位置數(shù)據(jù)是否在該區(qū)域中，若在該區(qū)域，則保存，并刪除已有結(jié)果中的空間數(shù)據(jù)；其次遍歷VHash，找出前K-1個(gè)近鄰的鄰居；最后計(jì)算前K-1個(gè)近鄰中不變的空間數(shù)據(jù)及鄰居和記錄的新增的空間數(shù)據(jù)到查詢點(diǎn)q的距離，升序排序后，選擇前三個(gè)生成點(diǎn)即為查找的三個(gè)近鄰。算法4表示精確查詢算法。

算法4精確查詢

輸入：KNN查詢結(jié)果集kobject，記錄表，VHash。

輸出：符合變化的所有數(shù)據(jù)對象。

在算法4中，第1行為依據(jù)VR樹，找到已有KNN查詢結(jié)果的上層節(jié)點(diǎn)區(qū)域，算法的時(shí)間復(fù)雜度為O(n)，第2行至第3行找到在步驟1中區(qū)域的新增數(shù)據(jù)并記錄，時(shí)間復(fù)雜度為O(n)，第4行至第5行為刪除KNN查詢結(jié)果k-1個(gè)近鄰中位置變化的數(shù)據(jù)，算法的時(shí)間復(fù)雜度為O(n2)，第6行至第7行為計(jì)算查詢點(diǎn)q到步驟5中數(shù)據(jù)的距離，并進(jìn)行排序，算法的時(shí)間復(fù)雜度為O(n2)，第9行至第10行為選取前K個(gè)，算法的時(shí)間復(fù)雜度為O(n)，因此精確查詢算法的時(shí)間復(fù)雜度為O(n2)。

如上述例子中，KNN 查詢結(jié)果為L6、L11、L8或者L6、L11、L4，當(dāng)查詢只需要精確結(jié)果時(shí)，只需要在VR樹中找到L6、L11、L4、L8對應(yīng)的上一層節(jié)點(diǎn)區(qū)域，得 到(S2,R1)、(S2,R2)、(S2,R3)、(S3,R1)、(S3,R2)，而新增位置數(shù)據(jù)L12(13,3) 在中間節(jié)點(diǎn)(S2,R1) 和(S2,R3)中，L13(17,3)在中間節(jié)點(diǎn)(S3,R1)中，刪除已經(jīng)變化的空間數(shù)據(jù)L11和L8，在VHash 中找出前K-1個(gè)近鄰的鄰居，計(jì)算查詢點(diǎn)q到L6、L4、L5、L10、L7、L8、L9、L12、L13的距離，升序排序后，前三個(gè)近鄰為L6、L12、L4。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)環(huán)境為16臺配備英特爾奔騰G3220雙核處理器，4 GB內(nèi)存，500 GB硬盤的計(jì)算機(jī)和16臺具有4 GB內(nèi)存的雙核虛擬機(jī)，它們具有相同Ubuntu16.04操作系統(tǒng)，編程環(huán)境為Eclipse10.0，編程語言為Java，集群環(huán)境為hadoop2.6。

實(shí)驗(yàn)所用數(shù)據(jù)集如表5所示。

Table 5 Datasets table表5 數(shù)據(jù)集表

真實(shí)數(shù)據(jù)集為外賣服務(wù)（take-out service，TS）中數(shù)據(jù)集。數(shù)據(jù)集為1 827個(gè)配送員在一周的軌跡數(shù)據(jù)，包含了107萬個(gè)坐標(biāo)。在刪除了方向、速度等因素后，篩選出了用戶有效屬性信息，共由bk id、date time、longitude、latitude這四部分組成，bk id為配送員的車輛編號，具有唯一性，對應(yīng)配送員身份的識別，date time 為位置上傳時(shí)間，longitude 為經(jīng)度，latitude為緯度。隨機(jī)選取其中84 h 的運(yùn)動(dòng)軌跡，并將這些數(shù)據(jù)按每10.5 h 為一個(gè)區(qū)間段進(jìn)行分割，共分為8組，每組數(shù)據(jù)包含6.68萬個(gè)坐標(biāo)。把每個(gè)區(qū)間段的所有坐標(biāo)進(jìn)行重新標(biāo)識，并使用mapgis 軟件進(jìn)行坐標(biāo)的轉(zhuǎn)換，作為每組的實(shí)驗(yàn)數(shù)據(jù)集。

模擬數(shù)據(jù)集（uniform dataset，UD）為含有x和y值的實(shí)體對象，隨機(jī)生成100萬個(gè)坐標(biāo)作為空間實(shí)體對象。為實(shí)現(xiàn)數(shù)據(jù)集變化，對應(yīng)的x和y值進(jìn)行加減，實(shí)現(xiàn)數(shù)據(jù)集的更新。在100萬個(gè)坐標(biāo)中，隨機(jī)選取6.68萬個(gè)坐標(biāo)為一個(gè)初始數(shù)據(jù)集，同時(shí)進(jìn)行x和y值的加減操作，將數(shù)據(jù)更新，得到8組變化的數(shù)據(jù)集。

5.2 索引

本節(jié)實(shí)驗(yàn)通過改變服務(wù)器中數(shù)據(jù)集的變化幅度和集群中節(jié)點(diǎn)的數(shù)量在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)，觀察VRI索引的創(chuàng)建時(shí)間。

在通過改變數(shù)據(jù)集變化幅度來觀察VRI、RTCAN和VoMR-tree創(chuàng)建索引的時(shí)間這一實(shí)驗(yàn)中，需要選取數(shù)據(jù)集的更新百分比為1%、5%、10%、15%、20%、25%、30%的7組數(shù)據(jù)集。在真實(shí)數(shù)據(jù)集中，以最初的實(shí)體對象為基礎(chǔ)，統(tǒng)計(jì)每分鐘內(nèi)變化的實(shí)體對象的數(shù)量，并計(jì)算變化的實(shí)體對象的數(shù)量占初始的實(shí)體對象的百分比，選取變化百分比為1%、5%、10%、15%、20%、25%、30%的7組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，觀察VRI 和ToSS-it創(chuàng)建索引的時(shí)間。在虛擬數(shù)據(jù)集中，以最初隨機(jī)生成的數(shù)據(jù)集為基礎(chǔ)，分別選取占總數(shù)據(jù)集百分比為1%、5%、10%、15%、20%、25%、30%的7組數(shù)據(jù)集，并將每組數(shù)據(jù)集的x和y值進(jìn)行加減，實(shí)現(xiàn)數(shù)據(jù)集的更新，以進(jìn)行實(shí)驗(yàn)，觀察VRI、RT-CAN和VoMR-tree創(chuàng)建索引的時(shí)間。其實(shí)驗(yàn)結(jié)果如圖10和圖11所示。

隨著數(shù)據(jù)更新幅度的增加，VRI創(chuàng)建索引的時(shí)間總體趨于平穩(wěn)，說明VRI索引結(jié)構(gòu)都適應(yīng)于隨機(jī)變化的位置數(shù)據(jù)對象，基于K-means算法進(jìn)行的不完全聚類比在隨機(jī)選取的數(shù)據(jù)間的距離和大者為關(guān)鍵點(diǎn)聚類的效果好，減少了局部Voronoi 生成過程中消息傳遞的數(shù)量，提高了索引創(chuàng)建的效率；RT-CAN 索引結(jié)構(gòu)隨著數(shù)據(jù)更新幅度的增加，索引的創(chuàng)建時(shí)間增長較大。因?yàn)殡S著更新量的增加，傳遞消息的總量以將近7倍的數(shù)量在增加，少量的更新都可能導(dǎo)致R樹的整體更新，所以RT-CAN索引結(jié)構(gòu)不適應(yīng)隨機(jī)變化的位置數(shù)據(jù)；而VoMR-tree索引的創(chuàng)建時(shí)間隨著數(shù)據(jù)更新幅度的增加而急劇增加，因?yàn)楦路鹊脑黾右馕吨枰黾踊騽h除的數(shù)據(jù)增加，所需要的時(shí)間也就增加了。

Fig.10 Creation time of index with data updating in uniformed dataset圖10 模擬數(shù)據(jù)集數(shù)據(jù)更新索引創(chuàng)建時(shí)間

Fig.11 Creation time of index with data updating in TS dataset圖11 真實(shí)數(shù)據(jù)集數(shù)據(jù)更新索引創(chuàng)建時(shí)間

在通過改變集群中節(jié)點(diǎn)數(shù)量來觀察索引創(chuàng)建時(shí)間這一實(shí)驗(yàn)中，在增加集群中節(jié)點(diǎn)數(shù)量的同時(shí)，需增加處理的實(shí)體對象的數(shù)量以進(jìn)行實(shí)驗(yàn)，即在分割的16組數(shù)據(jù)隨機(jī)選取需要的組數(shù)。在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集中，分別選取集群中4個(gè)節(jié)點(diǎn)、8個(gè)節(jié)點(diǎn)、16個(gè)節(jié)點(diǎn)和32個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)。其中對于真實(shí)數(shù)據(jù)集，在4個(gè)節(jié)點(diǎn)實(shí)驗(yàn)、8個(gè)節(jié)點(diǎn)實(shí)驗(yàn)、16個(gè)節(jié)點(diǎn)實(shí)驗(yàn)和32個(gè)節(jié)點(diǎn)實(shí)驗(yàn)中，其對應(yīng)的數(shù)據(jù)集分別為1組數(shù)據(jù)集、2組數(shù)據(jù)集、4組數(shù)據(jù)集和8組數(shù)據(jù)集；對于模擬數(shù)據(jù)集分別生成與真實(shí)數(shù)據(jù)集中同等數(shù)量的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，然后觀察索引的創(chuàng)建時(shí)間及變化曲線。如圖12、圖13為模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集中，索引創(chuàng)建時(shí)間的變化曲線。

Fig.12 Creation time of index with changes of nodes in uniformed dataset圖12 模擬數(shù)據(jù)集節(jié)點(diǎn)變化索引創(chuàng)建時(shí)間

Fig.13 Creation time of index with changes of nodes in TS dataset圖13 真實(shí)數(shù)據(jù)集節(jié)點(diǎn)變化索引創(chuàng)建時(shí)間

隨著集群中節(jié)點(diǎn)數(shù)量的增加，VRI結(jié)構(gòu)的創(chuàng)建時(shí)間基本沒有明顯的變化，而RT-CAN 和VoMR-tree 索引結(jié)構(gòu)在創(chuàng)建時(shí)間上增長較快，說明VRI空間索引結(jié)構(gòu)具有較好的性能，RT-CAN 和VoMR-tree 創(chuàng)建效率較低。同時(shí)，觀察到VRI總的索引創(chuàng)建時(shí)間隨著節(jié)點(diǎn)數(shù)量和數(shù)據(jù)集的增加，有一個(gè)稍微的增加，因?yàn)樵跀?shù)據(jù)重新分配階段和R樹生成階段中，距離的計(jì)算和面積組合的計(jì)算需要稍長的時(shí)間。

5.3 查詢

在評估KNN 查詢算法性能這一實(shí)驗(yàn)中，通過改變K值和數(shù)據(jù)集的數(shù)量來進(jìn)行查詢性能評估。分別在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)，觀察KNN查詢算法每秒處理的查詢的數(shù)量的曲線變化，來對KNN查詢算法的性能進(jìn)行評估。

將整數(shù)K值在1到32之間進(jìn)行變化，數(shù)據(jù)集不變，在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集中同時(shí)進(jìn)行實(shí)驗(yàn)，觀察每秒處理的KNN查詢量。圖14、圖15為模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集中，KNN 算法每秒處理的查詢量隨著整數(shù)K在1到32間變化的曲線。

Fig.14 K value diagram in uniformed dataset圖14 模擬數(shù)據(jù)集K值變化圖

Fig.15 K value diagram in TS dataset圖15 真實(shí)數(shù)據(jù)集K值變化圖

兩種數(shù)據(jù)集隨著K值的增加，每秒處理的查詢量逐漸減少，因?yàn)镵的值增加，意味著在每個(gè)查詢中，需要比較的實(shí)體對象的數(shù)量增加，從而增加了每個(gè)查詢處理的時(shí)間，降低了查詢的效率；VRI 索引結(jié)構(gòu)中KNN查詢處理速率高于ToSS-it和RT-CAN中的查詢處理速率，而且模擬數(shù)據(jù)集中的處理速率高于真實(shí)數(shù)據(jù)集中的處理速率，即模擬數(shù)據(jù)集中KNN 查詢算法的性能高于真實(shí)數(shù)據(jù)集中KNN查詢算法的性能。

在確定K值之后，選取集群中節(jié)點(diǎn)數(shù)量為8，數(shù)據(jù)集組數(shù)分別為1組、2組、4組和8組進(jìn)行實(shí)驗(yàn)，觀察KNN 查詢算法每秒處理的查詢的總量。圖16、圖17為模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集中，隨著節(jié)點(diǎn)數(shù)量的變化，KNN查詢算法每秒處理的查詢量的變化曲線。

Fig.16 Data sizes diagram in uniformed dataset圖16 模擬數(shù)據(jù)集數(shù)據(jù)量變化圖

Fig.17 Data sizes diagram in TS dataset圖17 真實(shí)數(shù)據(jù)集數(shù)據(jù)量變化圖

同等條件下，隨著數(shù)據(jù)集組數(shù)的增加，KNN查詢算法每秒處理的查詢量逐漸減少。在VRI中，數(shù)據(jù)集數(shù)量增加，意味著Voronoi圖中的Voronoi單元數(shù)量增加，基于Voronoi圖的R樹中節(jié)點(diǎn)的數(shù)量增加，需要進(jìn)行比較的區(qū)域和數(shù)據(jù)量增加，降低了KNN 查詢的處理速率，而且模擬數(shù)據(jù)集中，KNN查詢的處理速度高于真實(shí)數(shù)據(jù)集中的處理速度。

6 結(jié)論

隨著位置收集技術(shù)的日漸成熟，移動(dòng)位置數(shù)據(jù)爆炸式地增長，與之相對應(yīng)的空間索引技術(shù)和查詢方法也在不斷地改進(jìn)。KNN查詢作為空間數(shù)據(jù)查詢研究的重要內(nèi)容之一，在現(xiàn)實(shí)生活中得到廣泛應(yīng)用和迅速發(fā)展?；赩oronoi 劃分的位置數(shù)據(jù)的KNN查詢方法，將VHash 和VR 樹結(jié)合，構(gòu)建了一個(gè)二級索引結(jié)構(gòu)。其中，在一級索引結(jié)構(gòu)VHash 創(chuàng)建過程中，基于K-means 的重新分布，保持了位置數(shù)據(jù)的原有性，且VHash 存儲的是具有共享邊和共享點(diǎn)的鄰居，精確了查找；二級索引VR樹，自下而上地進(jìn)行節(jié)點(diǎn)結(jié)合，將重疊面積大者組合在一起，生成上層節(jié)點(diǎn)，由此實(shí)現(xiàn)了中間節(jié)點(diǎn)的聚類，加快查找，且彌補(bǔ)了R樹變體空間劃分中的兄弟節(jié)點(diǎn)交疊和覆蓋問題，使查詢路唯一，提高了查找效率。在KNN查詢中，利用VR樹進(jìn)行查詢點(diǎn)的定位，解決了頻繁定位及定位時(shí)間長的問題，同時(shí)在索引更新期間，對KNN查詢結(jié)果進(jìn)行近似查詢和精確查詢，滿足了多方查詢需求，確保了查詢的有效性。