基于歷史結(jié)果緩存的路網(wǎng)k近鄰查詢算法

李佳佳，楊亞星，朱 睿，宗傳玉，夏秀峰

(沈陽航空航天大學(xué) 計算機(jī)學(xué)院，沈陽 110136)

路網(wǎng)中的k近鄰(kNearest Neighbor，kNN)查詢是在給定被查詢的興趣點(diǎn)(POI)集合中，返回路網(wǎng)中距離查詢點(diǎn)最近的k個POI對象。近年來，隨著網(wǎng)絡(luò)通信的發(fā)展，kNN查詢成了一個重要的研究課題，引起越來越多學(xué)者的關(guān)注，在地圖導(dǎo)航、救援服務(wù)、位置感知廣告服務(wù)等方面具有廣闊的應(yīng)用場景，例如用戶查找距離最近的酒店。

路網(wǎng)中每天存在大量的在線k近鄰查詢，現(xiàn)有研究中要么采用在線擴(kuò)展路網(wǎng)的查詢方式，要么采用基于索引結(jié)構(gòu)的查詢方式，通常關(guān)注基于單一查詢效率的提升，而沒有考慮大量集中查詢的效率。如在學(xué)校、小區(qū)等區(qū)域比較集中的查詢中，存在許多結(jié)果相似的查詢，但每次都需要向服務(wù)器發(fā)起查詢請求，重新進(jìn)行k近鄰查詢，大大增加了服務(wù)器的負(fù)擔(dān)。為此本文提出基于歷史結(jié)果緩存的k近鄰查詢算法(Cache basedkNN,CBkNN)，旨在重用緩存的歷史k近鄰查詢結(jié)果，減少服務(wù)器的查詢代價。

不同于現(xiàn)有的研究，本文研究的基于緩存的k近鄰查詢有以下特點(diǎn)：

(1)提出了共享前綴匹配模型，通過對緩存結(jié)果的共享匹配，提高緩存命中率。

(2)提出基于結(jié)點(diǎn)的緩存存儲結(jié)構(gòu)，快速查找可利用的歷史查詢結(jié)果，提高查詢共享匹配效率。

(3)通過在真實(shí)路網(wǎng)中進(jìn)行大量實(shí)驗(yàn)，結(jié)果表明，CBkNN算法比不使用緩存的INE算法快25%，比緩存算法MkNN響應(yīng)時間少15%。

1 相關(guān)工作

目前對基于路網(wǎng)的k近鄰查詢算法研究或采用無索引的在線擴(kuò)展方式，如INE算法、IER算法[1]；或利用預(yù)先計算的索引結(jié)構(gòu)來加快查找效率，如island[2]、S-GRID[3]、DisBrw[4]、ROAD[5-6]、G-tree[7-8]、TOAIN[9]等算法。前者只存儲路網(wǎng)中節(jié)點(diǎn)和邊的信息，需要大量在線計算；后者在存儲基本路網(wǎng)信息的同時，需要預(yù)先計算一些節(jié)點(diǎn)信息，需要較長的預(yù)處理時間及較大的存儲空間。2016年，發(fā)表在VLDB的文獻(xiàn)[10-11]對以上算法進(jìn)行了詳細(xì)的實(shí)驗(yàn)對比，實(shí)驗(yàn)結(jié)果表明INE算法在POI密度較高的情況下性能較優(yōu)。

基于INE算法，Thomsen等[12]提出了多步驟kNN查詢算法(MkNN)，通過歷史結(jié)果的選擇性存儲，在下一步查詢中重用存儲的歷史結(jié)果。MkNN算法中的歷史kNN結(jié)果只起到輔助作用，減少了在線擴(kuò)展路網(wǎng)中的節(jié)點(diǎn)，并沒有直接回答新查詢。同時，該算法依然存在INE算法的局限性，在POI稀疏的情況下，算法效率依舊較低。

文獻(xiàn)[13]和[14]利用歷史最短路徑結(jié)果回答最短路徑查詢。通過子路徑匹配，即在緩存的最短路徑中匹配新查詢的起點(diǎn)和終點(diǎn)，用于回答新的查詢。文獻(xiàn)[15]提出緩存路徑規(guī)劃(PPC)算法，與前者的僅當(dāng)緩存與新查詢完全匹配時才使用緩存的方法不同，PPC算法利用部分匹配的緩存路徑來回答新查詢的一部分，剩余部分重新查詢。雖然基于緩存的最短路徑算法并不能直接應(yīng)用于kNN查詢算法，但為本文研究提供了一些靈感。

綜上所述，現(xiàn)有的kNN查詢技術(shù)大多只關(guān)注單次查詢效率，并沒有考慮查詢結(jié)果的重用問題。盡管有些工作提出了基于緩存的最短路徑查詢優(yōu)化方式，但最短路徑查詢和kNN查詢具有本質(zhì)上的不同，并不能直接應(yīng)用在kNN查詢上。因此，研究基于緩存的kNN查詢具有非常重要的意義。

2 問題定義

定義1路網(wǎng)。路網(wǎng)G由集合V、E和W組成，記為G(V,E,W)，其中V{v1,…,vn}表示節(jié)點(diǎn)的集合，E{(vi,vj)|vi,vjV,i≠j}表示連接兩個不同節(jié)點(diǎn)的邊的集合，W={(vi,vj)|vi,vj∈V,i≠j}表示邊的長度。圖1所示為一個路網(wǎng)圖。

圖1 路網(wǎng)圖

定義2 路網(wǎng)k近鄰查詢。給定POI集合P和查詢點(diǎn)q，返回路網(wǎng)中距離查詢點(diǎn)q最近的k個POI的結(jié)果集合R，其形式化定義為：kNN(q)={p∈R, R?P|?v∈P-R,dist(q,p)≤dist(q,v)}

定義3緩存C。緩存是kNN查詢結(jié)果的集合。

定義4查詢?nèi)罩綫logs。查詢?nèi)罩臼怯蛇^去用戶發(fā)布的帶有時間戳的查詢集合。

3 CBkNN查詢框架

CBkNN查詢框架主要分為k近鄰共享檢測、緩存結(jié)構(gòu)、緩存管理和緩存命中k近鄰結(jié)果計算，如圖2所示。

當(dāng)用戶發(fā)起查詢請求，首先需要查找共享檢測產(chǎn)生的共享記錄表，確定可以重利用緩存中的歷史kNN結(jié)果。如果能夠利用緩存結(jié)果，即緩存命中，則可以根據(jù)已有的歷史kNN結(jié)果計算新查詢的kNN結(jié)果，并返回給用戶。如果不能重用歷史結(jié)果，即緩存未命中，則需要向服務(wù)器發(fā)起查詢請求，使用其它算法(INE)進(jìn)行kNN查詢來獲取結(jié)果，同時需要更新緩存，對查詢結(jié)果進(jìn)行共享檢測。

4 CBkNN算法

本文的主要目的是通過利用緩存的kNN查詢結(jié)果來回答新的kNN查詢，從而減少在線查詢時服務(wù)器的工作量。最直接的解決方案是新查詢和緩存的歷史查詢完全匹配，即歷史查詢點(diǎn)和新查詢點(diǎn)相同，并且歷史查詢的k值大于等于新查詢的k值，這種匹配通常被稱為緩存命中；反之，稱為緩存未命中。而在實(shí)際應(yīng)用中，歷史查詢點(diǎn)和新查詢點(diǎn)相同的情況并不多見，因此提高歷史查詢結(jié)果的重復(fù)利用是本文的工作重點(diǎn)。

4.1 k近鄰緩存結(jié)果共享檢測

引理1 給定查詢點(diǎn)q，路網(wǎng)節(jié)點(diǎn)v和興趣點(diǎn)p。如果p是q的k近鄰結(jié)果之一，并且q到達(dá)p的最短路徑經(jīng)過v，那么p也是v的k近鄰結(jié)果之一。引理1的示意圖如圖3所示。

圖3 近鄰共享

證明 假設(shè)p不是v的k近鄰結(jié)果，那么dist(v,p)>dist(v,pk)，pk表示第k個近鄰結(jié)果。因?yàn)閜是q的k近鄰結(jié)果之一，即dist(q,p)≤dist(q,pk),p{p1,…,pk}，q到達(dá)p的最短路徑經(jīng)過v，那么dist(q,p)=dist(q,v)+dist(v,p)，所以dist(v,p)≤dist(q,pk)dist(q,v)≤dist(v,pk),與dist(v,p)>dist(v,pk)相矛盾，因此p也是v的k近鄰結(jié)果之一。

基于引理1作進(jìn)一步延伸，如果q到k個近鄰結(jié)果的最短路徑都經(jīng)過v，那么q的k近鄰結(jié)果也是v的k近鄰結(jié)果。

定義5 共享前綴。給定路網(wǎng)節(jié)點(diǎn)q和v，以及POI集合P={p1,p2,…,pk}。如果P是q的k近鄰結(jié)果，且q到前k′個近鄰POI的路徑經(jīng)過v，其中1≤k′≤k，那么v是q的共享前綴，k′是共享結(jié)果值。

如圖4所示，v2是v1的共享前綴。證明，已知v1的3NN結(jié)果是p1,p2,p3，v1到前2個近鄰結(jié)果的最短路徑都經(jīng)過v2，即：

圖4 共享前綴

dist(v1,p1)≤dist(v1,p2)≤dist(v1,p3)

(1)

dist(v1,p1)=dist(v1,v2)+dist(v2,p1)

(2)

dist(v1,p2)=dist(v1,v2)+dist(v2,p2)

(3)

由公式(1)(2)(3)可知，

dist(v1,p1)-dist(v1,v2)

≤dist(v1,p2)-dist(v1,v2)

(4)

即：

dist(v2,p1)≤dist(v2,p2)

(5)

那么p1,p2也是v2的2近鄰結(jié)果,所以v2是v1的共享前綴。

通過對歷史結(jié)果進(jìn)行共享前綴檢測，使更多的查詢節(jié)點(diǎn)重利用歷史結(jié)果，提高緩存命中率。首先，獲取q的第一個近鄰結(jié)果的最短路徑；然后，依次獲取路徑上的節(jié)點(diǎn)v，確認(rèn)其他近鄰結(jié)果的路徑是否經(jīng)過v，確定v共享結(jié)果的個數(shù)k′；最后，將(q,k′,dist(q,v))放入緩存的共享記錄表L中，其偽代碼如算法1所示。

算法1:共享前綴檢測輸入:q,kNN(q)輸出:L1.path1←kNN(q)//從kNN(q)中獲取第一個近鄰結(jié)果的路徑2.forv∈path13.k′=0//共享值初始化4.for1≤j≤k5. ifv∈pathj//確定近鄰路徑中經(jīng)過相同的節(jié)點(diǎn)v6. k′←k′+1;7. ifk′≥k′min8. L.v←(q,k′,dist(q,v))//將(q,k′,dist(q,v))加入v的共享表L中9.returnL

4.2 緩存結(jié)構(gòu)

緩存結(jié)構(gòu)包括歷史查詢?nèi)罩颈鞶Logs和共享記錄表L。歷史查詢?nèi)罩颈泶鎯v史查詢的詳細(xì)結(jié)果，共享記錄表基于節(jié)點(diǎn)的存儲結(jié)構(gòu)，存儲每個節(jié)點(diǎn)可以共享的歷史查詢集合，允許新查詢快速查找歷史查詢?nèi)罩颈碇锌衫玫臍v史結(jié)果。

歷史查詢?nèi)罩颈碛涗浟藲v史查詢點(diǎn)的詳細(xì)查詢結(jié)果，包括k個POI和查詢點(diǎn)到POI的最短路徑。其結(jié)構(gòu)為：nodeID:r1,r2,…,ri,…,rk，其中ri的結(jié)構(gòu)是ri:,pathi，poii表示POI，dist表示POI到查詢點(diǎn)的路網(wǎng)距離，pathi表示查詢點(diǎn)到POI的路徑，其結(jié)構(gòu)為path:,…,。在歷史查詢表中存儲v16、v11的2NN結(jié)果，具體如表1所示。

表1 歷史查詢?nèi)罩颈?/p>

根據(jù)共享前綴檢測算法，對于歷史查詢?nèi)罩颈碇械拿總€記錄，路徑中的每個節(jié)點(diǎn)都能重利用歷史結(jié)果。所以可以根據(jù)共享前綴檢測算法對歷史查詢?nèi)罩颈碇械拿總€結(jié)果進(jìn)行共享前綴檢測，同時共享記錄表升序記錄共享歷史查詢點(diǎn)和共享結(jié)果個數(shù)。共享記錄表的結(jié)構(gòu)為：nodeID:,…,，如表2所示，v16能夠共享v16的2NN結(jié)果，v12能夠共享v11的2NN結(jié)果。

表2 共享記錄表

4.3 緩存的更新維護(hù)

由于緩存大小有限，因此在緩存已滿時，必須刪除某個使用效率低的歷史k近鄰查詢記錄，替換使用效率高的查詢記錄。本節(jié)通過探索路網(wǎng)中kNN查詢的獨(dú)特特征來提出一種新的緩存替換策略。

查詢點(diǎn)的k值越大，查詢結(jié)果中查詢點(diǎn)到POI的最短路徑經(jīng)過的節(jié)點(diǎn)越多，查詢結(jié)果中共享前綴節(jié)點(diǎn)可能會越多，同時k值越大，代表kNN結(jié)果能夠服務(wù)的k值范圍越大，那么歷史結(jié)果被利用的可能性越大。因此，歷史查詢點(diǎn)的k值越大，歷史結(jié)果被重利用的可能性越大，緩存的命中率越高。為了提高緩存的命中率，本文用k值較大的結(jié)果替換k值較小的緩存結(jié)果。當(dāng)新查詢點(diǎn)q的k值大于緩存中相同的歷史查詢點(diǎn)q′的k值時，用q的結(jié)果替換q′的結(jié)果，提高緩存的命中率。其算法的偽代碼如算法2所示。

算法2:緩存構(gòu)建和更新輸入:q,kNN(q),C輸出:C1.ifCisnotfullthen2. Insertq.resultintoC//放入緩存3. L←kNN(q)//q結(jié)果共享檢測4. returnC5.else6. ifq.kq′.k,q′∈Cthen7. q′.result←q.result//更新緩存8. else9. C←LRU,LFU//LRU或者LFU策略更新10. L←kNN(q)//q結(jié)果共享檢測11. endif12.endif13.returnC

4.4 CBkNN算法

基于共享前綴檢測，更多的節(jié)點(diǎn)能夠重利用歷史kNN查詢結(jié)果，提高了緩存命中率。為了方便討論，本文對緩存命中的概念進(jìn)行了如下定義：

定義6緩存命中。給定一個k近鄰查詢q，如果緩存中存在一個歷史查詢q′，q是q′的共享前綴，且共享結(jié)果值k′ ≥k，則稱為緩存命中。

本文根據(jù)緩存的歷史結(jié)果，計算新查詢的kNN結(jié)果。由定義5可知，新查詢到POI的路網(wǎng)距離計算模型為:

dist(q,pi)=dist(q′,pi)-dist(q′,q)

(6)

算法3展示了基于緩存的k近鄰查詢算法。步驟(1)為從共享表中獲取查詢共享的歷史查詢結(jié)果。步驟(2～3)是在緩存中查找共享的結(jié)果。步驟(4～7)是根據(jù)歷史結(jié)果計算查詢點(diǎn)q的k近鄰結(jié)果。步驟(8)是在緩存未命中的情況下，使用其他方法計算查詢的k近鄰結(jié)果，并更新緩存和共享表。

算法3:基于緩存的k近鄰查詢輸入:q,k,G,C輸出:R1.qAC←L //從L中獲取q的共享緩存結(jié)果2.ifqAC?andk′k//獲取第一個緩存歷史點(diǎn)3. Rq′←Qlogs //獲取qAC中歷史查詢k′值最大記錄4.fori=1tok,pi∈Rq′5. dist(q′,pi),dist(q′,q)←Rq′6. dist(q,pi)=dist(q′,pi)-dist(q′,q)7. R←(pi,dist(q,pi))8.elseR←INE // INE方法計算結(jié)果,并更新緩存9.returnR

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

5.1 實(shí)驗(yàn)參數(shù)

本文使用真實(shí)的德國奧爾登堡地圖數(shù)據(jù)集對算法性能進(jìn)行全面的評估。地圖具有6 105個節(jié)點(diǎn)和7 035條邊，如表3所示，實(shí)驗(yàn)的默認(rèn)參數(shù)用加粗字體表示。其中緩存大小|C|是地圖數(shù)據(jù)的12%。

表3 實(shí)驗(yàn)參數(shù)

為了模擬真實(shí)情景，保證實(shí)驗(yàn)的真實(shí)性，本文在路網(wǎng)中設(shè)置集中查詢區(qū)域，并隨機(jī)模擬產(chǎn)生POI、查詢點(diǎn)和查詢k值。同時為了測試CBkNN算法的性能，本文使用了不同的緩存策略LRU(Least recently used)和LFU(Least frequently used)。LRU會將近期最不會訪問的數(shù)據(jù)淘汰掉，LFU淘汰近期使用頻率最小的數(shù)據(jù)。同時與INE和MkNN[1]算法進(jìn)行比較，INE算法是非緩存算法，MkNN算法是重用歷史結(jié)果的算法。文獻(xiàn)[10]對非索引的kNN算法進(jìn)行了詳細(xì)的實(shí)驗(yàn)對比，INE算法的綜合性能最優(yōu)，所以本文的非緩存算法采用INE算法?；诰彺娴淖疃搪窂讲樵兯惴╗11-12]使用時間節(jié)省率和命中率作為評估性能的重要指標(biāo),所以本文主要比較兩個性能參數(shù)：時間節(jié)省率和命中率。查詢時間節(jié)省率是緩存算法相對于非緩存算法的節(jié)省時間的比值，其計算公式為

(7)

其中timeno_cache是沒有使用緩存的INE算法響應(yīng)時間，timecache是使用緩存算法的響應(yīng)時間，時間節(jié)省率越大代表性能越好。命中率是緩存使用效率重要指標(biāo),命中率的計算公式為

(8)

其中hitcache是緩存命中的次數(shù)，Q是查詢總數(shù)量。

5.2 實(shí)驗(yàn)結(jié)果

本文以INE算法作為基礎(chǔ)對比實(shí)驗(yàn),通過測量緩存命中率和時間節(jié)省率檢測MkNN算法和CBkNN算法的性能，然而MkNN算法中每次查詢需要使用多個緩存結(jié)果，并不能統(tǒng)計出緩存命中率，所以本文并不比較MkNN算法的命中率。每組實(shí)驗(yàn)只改變一個參數(shù)，其余參數(shù)設(shè)置為表3的默認(rèn)值。通過實(shí)驗(yàn)，本文測量了多個參數(shù)對算法性能的影響。

(1)查詢數(shù)量

圖5展示了查詢數(shù)量對算法性能的影響。從圖5中可以看出，隨著查詢數(shù)量的增多，CBkNN算法的命中率和時間節(jié)省率都在提高，最終趨于穩(wěn)定。這是由于查詢數(shù)量較少時，緩存中的結(jié)果并不是集中區(qū)域的查詢，所以緩存命中率較低，時間節(jié)省率也處于較低水平。隨著查詢數(shù)量的增加，緩存中的結(jié)果經(jīng)過替換變成常用查詢，命中率不斷提高，查詢時間節(jié)省率也不斷提高。圖5a中可以看出，查詢數(shù)量到達(dá)5k和15k后，LRU策略緩存和LFU策略緩存的緩存命中率以及時間節(jié)省率都趨于穩(wěn)定。

圖5 查詢數(shù)量

同時也可以發(fā)現(xiàn)，LFU策略的緩存性能優(yōu)于LRU策略，這是由于查詢集中頻率較高的區(qū)域，LFU策略側(cè)重于查詢的頻率，而LRU側(cè)重于查詢的最近時間。從圖5b可以看出本文的CBkNN算法優(yōu)于MkNN算法。這是由于MkNN算法只是使用歷史結(jié)果作為候選結(jié)果，減少查詢擴(kuò)展的節(jié)點(diǎn)，而本文的CBkNN算法直接使用歷史結(jié)果，減少更多的擴(kuò)展節(jié)點(diǎn)。

(2)緩存大小

緩存的大小直接決定了系統(tǒng)可存儲最大k近鄰結(jié)果的數(shù)量，圖6展示了緩存大小對算法性能的影響，可以看出本文的CBkNN算法性能最優(yōu)。

從圖6a中可以看出，隨著緩存的增大，所有算法的緩存命中率在逐步提高。這是因?yàn)榫彺嬖酱螅鎯Φ臍v史結(jié)果越多，緩存中可以命中的查詢越多，所以緩存命中率越高。

圖6 緩存大小

圖6b中可以發(fā)現(xiàn)，隨著緩存的增大，查詢時間節(jié)省率會逐漸減少。這是因?yàn)榫彺嬖龃?，命中率提高，能夠利用緩存直接得到更多查詢結(jié)果，所以計算量減少，查詢時間節(jié)省率提高。

圖7 共享最小k′值

從圖7可知，共享最小k′值越大，CBkNN算法的命中率越低，查詢節(jié)省時間率越低。這是因?yàn)閷彺嬷械臍v史結(jié)果進(jìn)行共享匹配時，共享k′值越大，緩存中單個緩存能夠共享緩存結(jié)果的節(jié)點(diǎn)越少，導(dǎo)致命中率降低，節(jié)省時間率降低。

(4)POI密度

圖8為不同POI密度下的命中率和時間節(jié)省率。

從圖8中可以看出，隨著POI密度增加，CBkNN算法的命中率降低，查詢時間節(jié)省率也隨之降低。這是因?yàn)镻OI密度增加，查詢點(diǎn)到POI的路網(wǎng)距離減小，單個緩存結(jié)果共享前綴節(jié)點(diǎn)減少，所以命中率降低，時間節(jié)省率也隨之降低。

圖8 POI密度

6 結(jié)論

本文提出了一種基于歷史結(jié)果緩存的路網(wǎng)kNN查詢算法，提出了共享前綴匹配模型，通過對緩存結(jié)果的共享匹配，提高緩存命中率。提出基于節(jié)點(diǎn)的緩存存儲結(jié)構(gòu)，快速查找可利用的歷史查詢結(jié)果，提高查詢共享匹配效率。實(shí)驗(yàn)表明，本文的CBkNN算法與沒有緩存的INE算法相比，系統(tǒng)減少25%的時間延遲，與緩存算法MkNN相比響應(yīng)時間減少10%。