宋寶燕，孟彥偉，丁琳琳

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

1 引言

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

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

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

本文借助于Voronoi 圖[5]在空間區(qū)域劃分方面的優(yōu)勢，提出了一種基于Voronoi劃分的位置數(shù)據(jù)KNN查詢處理方法，解決了大規(guī)模位置數(shù)據(jù)的KNN 查詢問題。首先，針對數(shù)據(jù)的原有性保持問題，提出了基于K-means算法的位置數(shù)據(jù)重新分布方法，實現(xiàn)了空間數(shù)據(jù)的不完全聚類。其次，提出了一個二級空間索引結(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查詢算法及動態(tài)維護算法，采用VR樹進行定位，VHash查找K近鄰，能夠有效地對查詢點定位，查找速度快。最后，針對數(shù)據(jù)更新的情況，索引結(jié)構(gòu)也能夠及時更新，在更新的時間段內(nèi)，對于位置數(shù)據(jù)隨時間變化的KNN查詢，提出了利用記錄表進行有效查詢的方法。

2 相關(guān)工作

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

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

2.2 KNN查詢

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

3 Voronoi劃分的空間索引

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

3.1 分布式Voronoi空間劃分

3.1.1 重新分布

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

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

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

隨機分布的位置數(shù)據(jù)進行重新分布前后的存儲結(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ù)歐式距離進行空間區(qū)域劃分的，可將空間劃分為相鄰而互不重疊的區(qū)域，隱含地構(gòu)建了離散點之間的鄰近關(guān)系，可有效支持K近鄰的快速查找。本文對每個服務(wù)器上重新分布的位置數(shù)據(jù)創(chuàng)建局部Voronoi圖。

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

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

3.1.3 Voronoi優(yōu)化

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

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

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

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

Fig.5 Voronoi boundary圖5 Voronoi 邊界

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

Voronoi 優(yōu)化的另一個方面是不準確Voronoi 單元的識別和修復(fù)，利用影響區(qū)域[18]對各服務(wù)器邊界點所在的Voronoi 單元進行識別和修復(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，具有共享邊和共享頂點VC 的生成點為該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表進行存儲，本文直鄰表示存儲的是具有共享邊和共享點的生成點。如圖8中，查詢點q為配送員的位置，其余為需要派送訂單的商家的位置，當(dāng)配送員選擇多個派送訂單時，在第二個訂單的選擇時，若只考慮共享邊為其鄰居的因素時，在o2的鄰居中，配送員位置q到o1的距離最近，因此配送員需要派送的第二單為o1，而實際存在配送員位置q到商家o4的距離小于到o1的距離。只考慮共享邊會導(dǎo)致查詢結(jié)果的不準確，因此本文選取具有共享邊和共享點的生成點為直鄰判斷的依據(jù)。

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

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 圖的生成和近心點Voronoi 的優(yōu)化后，各個服務(wù)器完成了分布式的Voronoi劃分，各個服務(wù)器存放的信息是（重新分布后的位置數(shù)據(jù)，邊界點，近心點，VHash 表）。這些信息的全局概要，即全局信息，為各個服務(wù)器的（鄰居，近心點）信息。通過全局信息，獲得各服務(wù)器的相對位置和服務(wù)器間的Voronoi 邊界，方便了優(yōu)化和查找。

3.2 Voronoi劃分的R樹索引

3.2.1 Voronoi單元的最小矩形覆蓋

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

3.2.2 組合表示（VR）生成

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

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

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

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

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

VR 樹的主要實現(xiàn)步驟是將數(shù)據(jù)集中的每個位置數(shù)據(jù)所在Voronoi 單元的矩形區(qū)域，與具有共享邊的Voronoi 單元所在矩形區(qū)域重疊的面積比較，選取最大的重疊面積，并記錄對應(yīng)的Voronoi單元；將所有的重疊面積快速排序，按照從大到小的順序，兩兩組合，在組合過程中，刪除已經(jīng)組合的數(shù)據(jù)，依次組合。對于每個服務(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ù)器中每個位置數(shù)據(jù)所在的矩形區(qū)域及重疊面積的初始化，時間復(fù)雜度為O(1);第7行至第17行為選取某位置數(shù)據(jù)與其具有共享邊的Voronoi單元所在矩形區(qū)域的重疊面積的最大值，并記錄其矩形區(qū)域，算法的時間復(fù)雜度為O(n)；第18行至第21行為每個服務(wù)器中所有位置數(shù)據(jù)對應(yīng)的最大重疊面積，并記錄該數(shù)據(jù)與其重疊面積最大的Voronoi 單元所在的矩形區(qū)域，完成了整個服務(wù)器中數(shù)據(jù)集的最大重疊面積。該算法整體的時間復(fù)雜度為O(n2)，第22行為快排，算法的時間復(fù)雜度為O(nlgn)，第23行至第28行為VR樹非葉節(jié)點和葉子節(jié)點的生成，算法的時間復(fù)雜度為O(n2lgn)，第29行至第31行為每個服務(wù)器中數(shù)據(jù)集的遍歷，由此整個VR樹生成算法的時間復(fù)雜度為O(n3lgn)。

3.2.3 VR全局信息

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

3.3 二級索引動態(tài)維護

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

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

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

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

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

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

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

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

4.1 KNN查詢

4.1.1 查詢點定位

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

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

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

4.1.2 近鄰確定

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

算法3KNN查詢

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

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

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

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

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

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

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

4.2 動態(tài)維護

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

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

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

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

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

4.2.2 近似結(jié)果

當(dāng)KNN查詢結(jié)果只作為對整體趨勢的一個參考時，已有的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ū)域時，利用回溯方法找到KNN查詢結(jié)果對應(yīng)的上一層節(jié)點區(qū)域，判斷新增加的位置數(shù)據(jù)是否在該區(qū)域中，若在該區(qū)域，則保存，并刪除已有結(jié)果中的位置數(shù)據(jù)，找出滿足需求的一個二級近似結(jié)果。

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

4.2.3 精確結(jié)果

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

算法4精確查詢

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

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

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

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

5 實驗

5.1 實驗環(huán)境

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

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

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

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

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

5.2 索引

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

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

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

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

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

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

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

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

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

5.3 查詢

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

將整數(shù)K值在1到32之間進行變化，數(shù)據(jù)集不變，在真實數(shù)據(jù)集和模擬數(shù)據(jù)集中同時進行實驗，觀察每秒處理的KNN查詢量。圖14、圖15為模擬數(shù)據(jù)集和真實數(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ù)據(jù)集K值變化圖

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

在確定K值之后，選取集群中節(jié)點數(shù)量為8，數(shù)據(jù)集組數(shù)分別為1組、2組、4組和8組進行實驗，觀察KNN 查詢算法每秒處理的查詢的總量。圖16、圖17為模擬數(shù)據(jù)集和真實數(shù)據(jù)集中，隨著節(jié)點數(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ù)據(jù)集數(shù)據(jù)量變化圖

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

6 結(jié)論

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