路網(wǎng)中位置不確定的二元反kNN查詢

徐 偉，李文根，張毅超，關(guān)佶紅

(同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，上海 201804)

(*通信作者電子郵箱jhguan@#edu.cn)

路網(wǎng)中位置不確定的二元反kNN查詢

徐 偉，李文根，張毅超，關(guān)佶紅*

(同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，上海 201804)

(*通信作者電子郵箱jhguan@#edu.cn)

針對(duì)路網(wǎng)限制和物體位置的不確定性，提出了路網(wǎng)中位置不確定的二元反kNN查詢(PBRkNN)，旨在查找一組位置不確定的點(diǎn),使得每個(gè)不確定點(diǎn)的kNN包含給定查詢點(diǎn)的概率大于一個(gè)閾值。為了解決該問(wèn)題，首先提出一種基于Dijkstra進(jìn)行剪枝處理的基本算法，即PE算法；接著在PE算法的基礎(chǔ)上通過(guò)預(yù)處理計(jì)算出每個(gè)點(diǎn)的kNN從而加快查詢速度，即PPE算法；而為了進(jìn)一步減小PPE算法中范圍查詢的開(kāi)銷(xiāo)，提出PPEE算法，利用網(wǎng)格索引來(lái)索引范圍查詢中要查詢的不確定空間點(diǎn)，從而提升算法的效率。最后，在北京和加州路網(wǎng)數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)，結(jié)果表明通過(guò)一些預(yù)處理的策略確實(shí)可以有效地處理路網(wǎng)中位置不確定的二元反kNN查詢。

反kNN查詢；路網(wǎng)；Dijkstra算法；不確定性

0 引言

隨著空間定位技術(shù)和移動(dòng)通信技術(shù)的發(fā)展，以及手機(jī)等智能設(shè)備的廣泛使用，各種基于位置的服務(wù)(Location Based Service, LBS)得到了越來(lái)越廣泛的應(yīng)用。作為基于位置應(yīng)用中重要的查詢之一，反kNN查詢(即尋找查詢點(diǎn)是哪些點(diǎn)的k最近鄰(k-Nearest Neighbor,kNN))[1]在現(xiàn)實(shí)生活中被廣泛用于諸如決策系統(tǒng)[1]、超市的選址、出租車(chē)的調(diào)度[2]和龍卷風(fēng)預(yù)測(cè)[2]等領(lǐng)域。

已有的關(guān)于反kNN查詢的研究主要分為三類(lèi)：基于歐氏距離的反kNN查詢[1,3-6]、基于路網(wǎng)距離的反kNN查詢[7-10]和不確定反kNN查詢[2,11-15]。不確定性的引入主要由于物體位置更新的時(shí)間間隔、網(wǎng)絡(luò)傳輸延遲、數(shù)據(jù)隱私保護(hù)和定位設(shè)備的誤差等因素會(huì)導(dǎo)致物體位置存在必然的不確定性。目前，不確定反kNN研究主要集中在歐氏空間?？紤]到物體的移動(dòng)受限于實(shí)際的路網(wǎng)，有必要進(jìn)行路網(wǎng)中不確定性的反kNN查詢研究。

反kNN查詢可以分為兩類(lèi)：一元反kNN查詢和二元反kNN查詢。其中一元反kNN查詢中的候選集合只有一種類(lèi)型，查詢目標(biāo)是計(jì)算查詢點(diǎn)是候選集中哪些點(diǎn)的kNN；二元反kNN查詢的查詢集合則分為兩類(lèi)A和B，查詢點(diǎn)與其中一個(gè)候選集A類(lèi)型相同，查詢目標(biāo)是計(jì)算查詢點(diǎn)是候選集B中哪些元素的kNN，值得注意的是，對(duì)于B中每個(gè)元素的kNN是指A中離其最近的k個(gè)元素。二元反kNN查詢?cè)趯?shí)際生活中有著廣泛的應(yīng)用，特別是結(jié)合路網(wǎng)和位置不確定性的二元反kNN更加符合現(xiàn)實(shí)生活。如在出租車(chē)的派單系統(tǒng)中，對(duì)于每個(gè)乘客的訂單派送選擇就可以看成是以乘客為查詢點(diǎn)的反kNN查詢；另外因?yàn)槌鲎廛?chē)一直運(yùn)動(dòng)，實(shí)時(shí)位置必然存在一定的不確定性。本文結(jié)合路網(wǎng)和位置的不確定性，旨在研究路網(wǎng)中位置不確定的二元反kNN查詢處理。

下面從歐氏空間中的反kNN查詢、路網(wǎng)中的反kNN查詢和不確定的反kNN查詢這三個(gè)方面介紹反kNN查詢的研究現(xiàn)狀。

1)歐氏空間中的反kNN查詢?，F(xiàn)有的基于歐氏空間的反kNN查詢的算法主要分為三步：1)建立索引；2)在已構(gòu)建好的索引結(jié)構(gòu)的基礎(chǔ)上通過(guò)一些剪枝過(guò)濾策略，剪掉一些不可能的空間點(diǎn)；3)對(duì)剩下的候選點(diǎn)進(jìn)行驗(yàn)證，得到最終滿足條件的結(jié)果。具體地，索引主要有R樹(shù)、R+-樹(shù)和R*樹(shù)；剪枝策略則主要分為基于自身限制的剪枝[1,3]和基于其他元素限制的剪枝[4-6]；候選點(diǎn)的驗(yàn)證主要采用kNN查詢或者range-k查詢。但是這類(lèi)查詢沒(méi)有考慮移動(dòng)物體位置的不確定性。

2)路網(wǎng)中的反kNN查詢。Yiu等[7]第一次提出了基于路網(wǎng)的反kNN查詢，其處理流程與歐氏空間中的反kNN類(lèi)似。不過(guò)，針對(duì)路網(wǎng)中的反kNN查詢的特點(diǎn)，索引方面主要采用泰森多邊形(Voronoi圖)[8]和鄰接表[9-10]；剪枝則根據(jù)更近鄰原則[8]實(shí)現(xiàn)；驗(yàn)證同樣使用kNN查詢。這類(lèi)查詢雖然將反kNN查詢引入到路網(wǎng)中，但是沒(méi)有考慮到路網(wǎng)中移動(dòng)物體的不確定性問(wèn)題。

3)不確定的反kNN查詢。Lian等[11]第一次提出了基于位置不確定性的反kNN查詢。這類(lèi)問(wèn)題的主要難點(diǎn)在于位置不確定性的表示和基于這種表示的高效索引與剪枝。這類(lèi)問(wèn)題主要分為四步：1)不確定性的表示,主要有最小邊界圓[11]和最小邊界矩形[2,11-15]；2)基于空間位置的剪枝，即不考慮它們的概率分布，主要是基于半分策略[12-14]；3)基于概率的剪枝,主要是劃分圓[2,15]；4)驗(yàn)證采用kNN查詢。這類(lèi)查詢雖然引入了移動(dòng)物體位置的不確定性，但是并沒(méi)有考慮路網(wǎng)中位置不確定性的反kNN查詢。

綜上所述，已有的反kNN查詢算法沒(méi)有同時(shí)考慮路網(wǎng)限制和物體位置的不確定性，不能直接用于解決本文所提出的路網(wǎng)中位置不確定的反kNN查詢問(wèn)題。

1 問(wèn)題定義

首先給出路網(wǎng)和空間點(diǎn)的定義。

定義1 路網(wǎng)(Road Network)。路網(wǎng)本質(zhì)上一個(gè)圖G=〈V,E〉。其中:V代表節(jié)點(diǎn)的集合，表示路網(wǎng)中道路的拐點(diǎn)或交叉點(diǎn)；E是邊的集合，每條邊連接兩個(gè)節(jié)點(diǎn)。

定義2 空間點(diǎn)(PointOnNetwork,PON)。一個(gè)空間點(diǎn)表示為p=〈e,pos〉。其中:e表示空間點(diǎn)所在的邊，pos表示空間點(diǎn)p到e的開(kāi)始端的偏移。

在定義不確定空間點(diǎn)(UncertainPON，UPON)之前，先描述不確定空間點(diǎn)的表現(xiàn)形式。在歐氏空間中，物體的不確定位置表示為一個(gè)橢圓或多邊形。如圖1，物體在a處的不確定表示就是圍繞a點(diǎn)的橢圓。然而，在路網(wǎng)中，物體運(yùn)動(dòng)受限于路網(wǎng)。例如，圖1存在著實(shí)際路網(wǎng)bd和ce，歐氏空間中陰影的范圍在路網(wǎng)中的不確定性表示就是4個(gè)路段即ab、ac、ad和ae。因此，在路網(wǎng)中UPON位置由多個(gè)路段來(lái)表示。把組成不確定空間點(diǎn)的路段稱(chēng)為不確定路段(UncertainSegment)。下面給出不確定路段和不確定空間點(diǎn)的定義。

定義3 不確定路段。不確定路段表示為us=〈edge,fromPos,toPos〉。其中:edge表示該不確定路段所在的邊,fromPos和toPos分別表示該確定性路段首尾位置。

圖1 不確定區(qū)域

定義4 不確定空間點(diǎn)。一個(gè)不確定空間點(diǎn)表示為up=〈us0,us1,…,usm-1〉,其中usi表示物體可能出現(xiàn)不確定路段。

定義5 不確定空間點(diǎn)的范圍長(zhǎng)度ul(UPONlength)。一個(gè)不確定空間點(diǎn)up=〈us0,us1,…,usm-1〉的范圍長(zhǎng)度ul為：

ul(up)=∑len(usi)

(1)

其中l(wèi)en(usi)=toPosi-fromPosi。

下面給出路網(wǎng)中位置不確定的二元反kNN查詢的定義。

定義6 路網(wǎng)中位置不確定的二元反kNN查詢(Probabilistic Bichromatic Reverse-kNN query on road network, PBR-kNN)。給定路網(wǎng)G，空間點(diǎn)PON集合A={p0,p1,…,pn-1},不確定空間點(diǎn)UPON集合B={up0,up1,…,upm-1},一個(gè)概率閾值? 和一個(gè)查詢點(diǎn)q∈A,PBR-kNN查詢的目標(biāo)是查找B的一個(gè)子集Bp,滿足:

Bp={up|P(q∈PkNN(up))≥?,up∈B}

(2)

其中P(q∈PkNN(up))表示q為up的kNN概率,即：

(3)

其中，{p|q∈kNN(p),p∈up}得到的點(diǎn)集合剛好可以組成若干個(gè)連續(xù)的路段。在PBR-kNN查詢中，集合A中的元素與查詢點(diǎn)q是競(jìng)爭(zhēng)關(guān)系，所以A的元素與q一樣為PON。

2 PE算法

為了有效解決路網(wǎng)中位置不確定的二元反kNN查詢，首先設(shè)計(jì)了Probabilistic Eager(PE)算法，作為解決此問(wèn)題的一個(gè)基本方法。PE算法的思想是基于Dijkstra算法加剪枝。

2.1 索引結(jié)構(gòu)

為了節(jié)省空間，便于每條邊上的PON和UPON的索引，PE算法采取類(lèi)鄰接表的方法存儲(chǔ)路網(wǎng)。在鄰接表中每個(gè)節(jié)點(diǎn)都會(huì)有個(gè)鄰接節(jié)點(diǎn)表，本文采用另外獨(dú)立索引每條邊的方式將鄰接節(jié)點(diǎn)表變成鄰接邊表。如圖2所示路網(wǎng)建立索引，其中：q1和q2為興趣點(diǎn)，q為查詢點(diǎn)，s1n7、s2n7、s3n7組成up1,s4n5、s5n5組成up2,q1n1=2,q2n2=3,qn2=2,s1n7=1,s2n7=2,s3n7=3,s4n5=1,s5n5=2。假設(shè)邊n1n2、n1n6、n2n4和n2n7的ID分別為e1、e2、e3和e4,則n1、n2的鄰接表如圖3。

PE算法給每條邊編一個(gè)ID，每條邊會(huì)記錄這條邊兩端節(jié)點(diǎn)的編號(hào)。對(duì)于每條邊上的空間點(diǎn)，會(huì)有一個(gè)PONlist表按照距離邊起始端的距離排序。對(duì)于每條邊上的不確定路段，會(huì)有一個(gè)UncertainList表記錄在這個(gè)邊上出現(xiàn)過(guò)的不確定空間點(diǎn)。對(duì)于不確定空間點(diǎn)，用一個(gè)單獨(dú)的鏈表來(lái)索引每個(gè)不確定空間點(diǎn)的路段。圖2的索引結(jié)果如圖4所示。

圖2 一個(gè)路網(wǎng)的例子

圖3 路網(wǎng)索引

圖4 邊及不確定空間點(diǎn)索引

2.2 查詢算法

引理1 對(duì)于不確定路段us(edge〈n1,n2,length〉,fromPos,toPos)和查詢點(diǎn)q，如果n1?BRkNN(q),n2?BRkNN(q),則有：

P(us∈BRkNN(q))=0

(4)

引理2 對(duì)于一條邊(edge〈n1,n2,length〉),所有滿足{p|q∈BRkNN(p),p∈edge}條件的PON構(gòu)成的區(qū)域剛好是整個(gè)edge的所有范圍或者兩個(gè)分開(kāi)的路段s1〈edge,fromPos1,toPos1〉,s2〈edge,fromPos2,toPos2〉滿足fromPos1=0,toPos2=length,并且toPos1

證明 反證法：假設(shè)存在一個(gè)路段s〈edge,fromPos,toPos〉包含所有滿足條件的PON點(diǎn)，且fromPos不等于0，toPos不等于length。假設(shè)d(q,n1)

dist(p,p1)=min(dist(p,n1)+dist(n1,p1),

dist(p,n2)+dist(n2,p1))

情況一dist(p,p1)=dist(p,n1)+dist(n1,p1)。

dist(p,n1)+dist(n1,p1)

dist(p,n1)=dist(p,p1)-dist(n1,p1)>

dist(q,p1)-dist(n1,p1)=dist(q,n1)

所以n1也是滿足條件的點(diǎn)，與fromPos=0矛盾。

情況二dist(p,p1)=dist(p,n2)+dist(n2,p1)。

dist(p,n1)+dist(n1,p1)>dist(p,n2)+dist(n2,p1)

dist(p,n1)>dist(p,p1)-dist(n1,p1)>

dist(q,p1)-dist(n1,p1)=dist(q,n1)

所以n1也是滿足條件的點(diǎn)，與fromPos=0矛盾。

綜上所述，不存在這樣的路段s，所以問(wèn)題得證。

推理1q為查詢點(diǎn)，n為路網(wǎng)節(jié)點(diǎn)，由文獻(xiàn)[7]中引理1和本文中引理1可以得到，如果存在k個(gè)空間點(diǎn)p0,p1,…,pk-1滿足d(n,pi)

P(us∈BRkNN(q))=0

(5)

證明 因?yàn)閚1和n2到q點(diǎn)的最短路徑都要經(jīng)過(guò)n,由文獻(xiàn)[7]中引理1得n1?BRkNN(q),n2?BRkNN(q),由本文中的引理1得P(us∈BRkNN(q))=0。

PE算法的基本邏輯其實(shí)非常簡(jiǎn)單，就是不停地在集合B中尋找可能是結(jié)果的upi,然后判斷P(q∈PkNN(upi))的值是否大于?。

1)尋找可能的upi。

最簡(jiǎn)單的辦法就是根據(jù)距離q點(diǎn)的距離，由近及遠(yuǎn)進(jìn)行遍歷作為候選者upi,那么就可以使用Dijkstra算法進(jìn)行擴(kuò)展。但是由推理1，可以從節(jié)點(diǎn)n處剪枝掉很多不可能的節(jié)點(diǎn)，提高尋找候選者的效率。所以算法的主要流程如下：

1)初始化一個(gè)小頂堆。

2)將查詢點(diǎn)q〈edge,pos〉所在邊的兩個(gè)端點(diǎn)加入堆中，即〈n1,pos〉和〈n2,edge.length-pos〉。

3)驗(yàn)證edge上是否有符合條件的不確定性路段。

4)基于Dijkstra算法對(duì)路網(wǎng)進(jìn)行擴(kuò)展，對(duì)符合推理1的節(jié)點(diǎn)進(jìn)行剪枝。

假設(shè)訪問(wèn)到了節(jié)點(diǎn)n:

a)計(jì)算n的kNN(n)={p1,p2,…,pk};

b)對(duì)于pi驗(yàn)證在range(n,q)范圍內(nèi)的邊上是否有滿足條件的us(實(shí)際上是再次計(jì)算pi的kNN)。

c)如果q?kNN(n),根據(jù)推理1剪掉節(jié)點(diǎn)n,否則將n的鄰接節(jié)點(diǎn)加入到堆中。

說(shuō)明：PE算法以不確定性路段作為最基本的單位分開(kāi)計(jì)算每個(gè)路段成為q的RkNN的概率，一個(gè)不確定性空間點(diǎn)的所有不確定性路網(wǎng)都計(jì)算完，或者程序結(jié)束前，就會(huì)計(jì)算每個(gè)被訪問(wèn)過(guò)的不確定空間點(diǎn)成為q的RkNN的概率，并篩選出概率值大于設(shè)定的概率閾值的。

2)驗(yàn)證候選者upi。

如前面所說(shuō)，對(duì)于候選者upi的驗(yàn)證，先計(jì)算組成upi的usi0,usi1,…,usi(m-1)的概率，然后再驗(yàn)證upi是否滿足要求。對(duì)于路網(wǎng)的同一條邊上可能會(huì)有多個(gè)us，而對(duì)于每個(gè)us的驗(yàn)證都與該邊的兩個(gè)端點(diǎn)有關(guān)，所以對(duì)于同一條邊上的us,它們的驗(yàn)證計(jì)算可能差不多。為了提高計(jì)算效率，PE算法先計(jì)算出us所在的邊edge上哪些區(qū)域段中的點(diǎn)是滿足為q點(diǎn)RkNN的，即

UAR={us|?p∈us,q∈BRkNN(p),us∈edge}

然后再計(jì)算usij中有多少包含在集合UAR中。假設(shè)計(jì)算的邊為edge〈n1,n2,len〉,計(jì)算UAR的算法主要包括以下步驟：計(jì)算kNN(n1)和kNN(n2);如果q不在kNN(n1)和kNN(n2)中，則返回空；根據(jù)引理2，UAR分成從n1起始的路段us1和從n2起始的路段us2計(jì)算；驗(yàn)證us1和us2是否要合并，并返回結(jié)果。

3 PPE算法和PPEE算法

3.1 PPE算法

PE算法包含大量?jī)蓚€(gè)路網(wǎng)節(jié)點(diǎn)間的最短距離計(jì)算，而在路網(wǎng)上計(jì)算兩點(diǎn)距離的算法比歐氏空間中的距離計(jì)算復(fù)雜很多。為了提高PE算法的效率，采用文獻(xiàn)[7]的方法提前算出每個(gè)節(jié)點(diǎn)的kNN(這里的kNN是指k最近鄰的PON點(diǎn))，稱(chēng)之為Pre-compute Probabilistic Eager (PPE)算法。這樣，PE算法中尋找可能upi的第4.a)步和驗(yàn)證候選者upi的第4.b)步，每次計(jì)算節(jié)點(diǎn)的kNN就可以省去，能極大地提高算法效率。

在預(yù)處理中，k設(shè)為可能取到的最大值。在實(shí)際生活中，k一般取到20就可以了。為了實(shí)驗(yàn)需求，本文k取100。

3.2 PPEE算法

在尋找候選upi的過(guò)程中，第4)步中的a)、b)可以同時(shí)計(jì)算，但是經(jīng)過(guò)PPE算法的改進(jìn)，b)還需要重新獨(dú)立地計(jì)算才能得到候選者。為此提出基于網(wǎng)格劃分索引的策略，從快速計(jì)算出候選者的角度來(lái)進(jìn)一步提高查詢的效率，稱(chēng)為Pre-computeProbabilisticEagerExternal(PPEE)算法。

3.2.1 數(shù)據(jù)索引

1)網(wǎng)格劃分。PPEE算法按照物體點(diǎn)的平面坐標(biāo)劃分網(wǎng)格，這樣可以方便數(shù)據(jù)的管理和查詢，便于數(shù)據(jù)的網(wǎng)格定位和快速找到每個(gè)網(wǎng)格四周的網(wǎng)格。對(duì)于一個(gè)不確定性路段可能出現(xiàn)在多個(gè)網(wǎng)格中的情況，PPEE算法采取多冗余化簡(jiǎn)便的辦法，在包含該不確定性路段的所有網(wǎng)格中都添加該不確定性路段。如圖5是圖2路網(wǎng)的一個(gè)網(wǎng)格劃分。

圖5 網(wǎng)格劃分

2)不確定性路段索引。因?yàn)橐粭l邊上可能會(huì)出現(xiàn)多個(gè)不確定性路段，而且在處理不確定性路段時(shí)，同一條邊上的多個(gè)不確定性路段同時(shí)處理效率會(huì)更高，所以PPEE算法對(duì)不確定性路段的索引是對(duì)含有不確定性路段的邊進(jìn)行索引。這樣既可以減小檢索塊的尺寸又可以提高索引查找的效率。使用圖5的劃分規(guī)則，得到的索引如圖6。

3)不確定性索引的更新。由于不確定性索引的更新可能會(huì)很快也可能很慢，為此PPEE算法采取類(lèi)似于內(nèi)存管理的策略。針對(duì)每一條邊，不確定性路段的更新包括以下四種情況：

1)該邊上增加了新的不確定性路段，但增加之前該邊上已有不確定性路段；

2)該邊上增加了新的不確定性路段，但是增加之前該邊上沒(méi)有不確定性路段；

3)該邊上減少了不確定性路段，但是減少之后該邊上還有不確定性路段；

4)該邊上減少了不確定性路段，減少之后該邊上就不存在不確定性路段了。

對(duì)于情況1)和3)，索引不需要作任何改變；對(duì)于情況2)，則需要把該邊添加到該邊所在網(wǎng)格的索引表中；對(duì)于情況4)，本來(lái)應(yīng)該從該邊所在網(wǎng)格的索引表中把該邊刪除，但是考慮到接下來(lái)可能還會(huì)有不確定性路段更新，因而采取延遲更新的策略，即在后來(lái)的查詢算法中查找到該邊時(shí)，如果該邊上沒(méi)有不確定性路段，就把它從索引表中刪除。

圖6 不確定性的索引

3.2.2 查詢算法

PPEE算法在PPE算法的基礎(chǔ)上對(duì)不確定性空間點(diǎn)作索引，它們的不同之處在于尋找候選不確定空間點(diǎn)集合。基于網(wǎng)格索引的尋找候選不確定空間點(diǎn)的算法如下：

輸入 節(jié)點(diǎn)n;

輸出 候選不確定空間點(diǎn)。

1)令d為kNN(n)中距離n點(diǎn)最遠(yuǎn)的距離。

2)定位n所在的網(wǎng)格為gridn。

3)計(jì)算到gridn的四邊的距離小于等于d的所有網(wǎng)格集合Grids。

4)遍歷Grids中所有的grid。對(duì)于gridi,遍歷gridi索引中的每條邊edgei中索引的不確定路段作為候選者。對(duì)于edgei如果不包含不確定路段，則從索引表中刪除。

在PPEE算法中，每條邊和每個(gè)劃分網(wǎng)格都會(huì)記錄是否被訪問(wèn)過(guò)，以防止重復(fù)訪問(wèn)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用北京和加州的路網(wǎng)，其中北京路網(wǎng)的節(jié)點(diǎn)和邊的數(shù)目分別為84 084和104 313；加州路網(wǎng)的節(jié)點(diǎn)和邊的數(shù)目分別為21 048和21 693。

1)北京路網(wǎng)PON和UPON生成：實(shí)驗(yàn)采用北京出租車(chē)數(shù)據(jù)，包含11 716輛出租車(chē)2012年某個(gè)月的采樣數(shù)據(jù)。將給定時(shí)刻叫車(chē)的乘客作為PON空間點(diǎn)集合，此時(shí)刻的空出租車(chē)則作為UPON集合。生成規(guī)則如下：選取一個(gè)打車(chē)比較多的時(shí)間點(diǎn)t，如果出租車(chē)在t時(shí)刻前后30min內(nèi)有載新乘客的動(dòng)作，說(shuō)明這個(gè)點(diǎn)有一個(gè)乘客，則將其加入到A集合；如果在這個(gè)時(shí)間點(diǎn)前后兩個(gè)采樣點(diǎn)都是空車(chē)的狀態(tài)，那就生成一個(gè)UPON，UPON的中心點(diǎn)就是距t最近的采樣點(diǎn)的位置，范圍為這兩個(gè)采樣點(diǎn)的距離。生成好之后就可以加入到UPON集合中。最終生成的空間點(diǎn)集合A共866個(gè)元素，不確定性區(qū)域集合B共3 994個(gè)元素，不確定性路段數(shù)為785 125。

2)加州路網(wǎng)上的PON和UPON生成：以加州路網(wǎng)為基礎(chǔ)，運(yùn)用隨機(jī)函數(shù)根據(jù)一定的限制生成，生成方法則模擬前面北京路網(wǎng)真實(shí)數(shù)據(jù)的生成。首先，按照集合A要求的元素個(gè)數(shù)，對(duì)集合A中每個(gè)點(diǎn)p〈edge,pos〉，按照edgeId和pos隨機(jī)生成。然后，按照集合B要求的元素個(gè)數(shù)，先按照生成集合A的辦法，生成|B|個(gè)點(diǎn)p0,p1,…,p|B|-1;接著，按照平均不確定性長(zhǎng)度ul,生成|B|個(gè)長(zhǎng)度值ul0,ul1,…,ul|B|-1,使得它們的平均值為ul;最后，以pi為中心，不確定性長(zhǎng)度為uli,按照前面真實(shí)數(shù)據(jù)的生成方法生成upi。該實(shí)驗(yàn)數(shù)據(jù)集如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)運(yùn)行于配置為IntelCorei7- 4790KCPU@ 4.00GHz16GBRAM的計(jì)算機(jī)，采用Java環(huán)境。實(shí)驗(yàn)結(jié)果為100次實(shí)驗(yàn)的平均值。

4.2 實(shí)驗(yàn)結(jié)果分析

1)k值大小對(duì)算法查詢時(shí)間的影響：本組實(shí)驗(yàn)分別在兩個(gè)數(shù)據(jù)集上進(jìn)行。從圖7、8可以看出，當(dāng)k較小時(shí)，三個(gè)算法的時(shí)間開(kāi)銷(xiāo)差異很小。隨著k的增加，三種算法的時(shí)間開(kāi)銷(xiāo)均在增加，PE算法進(jìn)行的range查詢按照訪問(wèn)節(jié)點(diǎn)的平方數(shù)增長(zhǎng)，而PPE算法是線性增長(zhǎng)的，所以這兩條線中PE算法曲線變化比PPE算法更明顯；而PPEE算法進(jìn)行range查詢的花費(fèi)為0，但隨著k的增加，訪問(wèn)的grid數(shù)也隨訪問(wèn)的節(jié)點(diǎn)數(shù)線性增長(zhǎng)，而訪問(wèn)grid的花費(fèi)明顯比range查詢少很多，所以PPEE算法的曲線變化更小。在實(shí)際的生活中，k可能只會(huì)取到40，由圖7可以看出，在k<40時(shí)，最快的查詢算法即PPEE算法可以在100ms之內(nèi)計(jì)算出結(jié)果。

2)PON數(shù)量對(duì)算法查詢時(shí)間的影響：本組實(shí)驗(yàn)使用加州路網(wǎng)的數(shù)據(jù)集C2。由圖9可以看出，在PON數(shù)量(即集合A中元素的個(gè)數(shù))比較小時(shí)，PON分布比較稀疏，這樣利用推理1進(jìn)行剪枝的效果會(huì)比較差，仍然需要進(jìn)行多次range查詢，所以PE算法和PPE算法的效果在A的個(gè)數(shù)小于100時(shí)并不明顯；但對(duì)于PPEE算法，因?yàn)椴恍枰M(jìn)行range查詢，所以影響不大。

3)UPON數(shù)量對(duì)算法查詢時(shí)間的影響：本組實(shí)驗(yàn)使用加州路網(wǎng)的數(shù)據(jù)集C3。三種算法遍歷的路網(wǎng)節(jié)點(diǎn)的個(gè)數(shù)沒(méi)有變化，變化的只是需要驗(yàn)證的邊的個(gè)數(shù)。由圖10可以看出，在UPON的數(shù)量(即集合B元素中元素的個(gè)數(shù))大于10 000時(shí)，PPEE算法的花費(fèi)明顯大于PPE，這是因?yàn)殡S著B(niǎo)中元素個(gè)數(shù)的增加，PPEE算法需要驗(yàn)證的UPON數(shù)量增長(zhǎng)的速度比算法PE和PPE快很多。

注意：在圖9～11中為了更好地展示結(jié)果，橫軸都采用指數(shù)的形式來(lái)表示。

4)不確定路段范圍長(zhǎng)度對(duì)查詢時(shí)間的影響：本組實(shí)驗(yàn)使用加州路網(wǎng)的數(shù)據(jù)集C4。集合B中UPON平均長(zhǎng)度的增加不會(huì)顯著影響三個(gè)算法訪問(wèn)的節(jié)點(diǎn)個(gè)數(shù)，但是會(huì)增加待驗(yàn)證的邊上不確定性路段的個(gè)數(shù)。從圖11可以看出，當(dāng)平均區(qū)域長(zhǎng)度大于100 000時(shí)，PPEE算法的時(shí)間曲線變化非常明顯，查詢時(shí)間比PE和PPE更長(zhǎng)，這是因?yàn)镻PEE算法采用劃分網(wǎng)格的策略尋找那些需要驗(yàn)證的不確定性路段，這樣使得需要驗(yàn)證的數(shù)量比另外兩種算法大幅增加。

圖7 北京路網(wǎng)數(shù)據(jù)集查詢時(shí)間與k的關(guān)系

圖8 加州路網(wǎng)數(shù)據(jù)集查詢時(shí)間與k的關(guān)系

圖9 集合A的個(gè)數(shù)與查詢時(shí)間的關(guān)系

圖10 集合B的個(gè)數(shù)與查詢時(shí)間的關(guān)系

圖11 UPON平均長(zhǎng)度與查詢時(shí)間的關(guān)系

5 結(jié)語(yǔ)

本文結(jié)合路網(wǎng)和物體位置的不確定性研究了路網(wǎng)中位置不確定的二元反kNN查詢問(wèn)題。為了解決該問(wèn)題，首先針對(duì)路網(wǎng)中位置不確定性提出了一個(gè)表示模型，并在此基礎(chǔ)上提出了一個(gè)基本的查詢處理算法即PE算法；在PE算法的基礎(chǔ)上，又進(jìn)一步提出了兩種改進(jìn)的處理算法，即PPE算法和PPEE算法。實(shí)驗(yàn)結(jié)果表明，PE算法適合處理k值較小的查詢，因?yàn)樗臅r(shí)間開(kāi)銷(xiāo)隨著k的增加呈現(xiàn)指數(shù)增長(zhǎng)；PPE算法的時(shí)間開(kāi)銷(xiāo)則隨著k的增加線性增長(zhǎng)，適合處理具有較大k值的查詢；PPEE算法性能最好，隨著k的增加，它的時(shí)間開(kāi)銷(xiāo)增長(zhǎng)非常緩慢，算法總的處理時(shí)間小于100 ms，能夠很好地滿足實(shí)時(shí)查詢的要求。

References)

[1] KORN F, MUTHUKRISHNAN S.Influence sets based on reverse nearest neighbor queries[J].ACM Sigmod Record, 2000, 29(2): 201-212.

[2] NIEDERMAYER J, ZüFLE A, EMRICH T, et al.Probabilistic nearest neighbor queries on uncertain moving object trajectories [J].Proceedings of the VLDB Endowment, 2013, 7(3): 205-216.

[3] LU J, LU Y, CONG G.Reverse spatial and textualknearest neighbor search [C]// SIGMOD 2011: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data.New York: ACM, 2011: 349-360.

[4] YANG S, CHEEMA M A, LIN X, et al.SLICE: reviving regions-based pruning for reverseknearest neighbors queries [C]// ICDE 2014: Proceedings of the 2014 IEEE 30th International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2014: 760-771.

[5] WU W, YANG F, CHAN C-Y, et al.FINCH: evaluating reversek-nearest-neighbor queries on location data [J].Proceedings of the VLDB Endowment, 2008, 1(1): 1056-1067.

[6] CHEEMA M A, LIN X, ZHANG W, et al.Influence zone: Efficiently processing reverseknearest neighbors queries [C]// Proceedings of the 2011 IEEE 27th International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2011: 577-588.

[7] YIU M L, PAPADIAS D, MAMOULIS N, et al.Reverse nearest neighbors in large graphs [J].IEEE Transactions on Knowledge & Data Engineering, 2006, 18(4): 540-553.

[8] SAFAR M, IBRAHIMI D, TANIAR D.Voronoi-based reverse nearest neighbor query processing on spatial networks [J].Multimedia Systems, 2009, 15(15): 295-308.

[9] BORUTTA F, NASCIMENTO M A, NIEDERMAYER J, et al.Monochromatic RkNN queries in time-dependent road networks [C]// MobiGIS ’14: Proceedings of the 2014 ACM SIGSPATIAL International Workshop.New York: ACM, 2014: 26-33.

[10] GAO Y, QIN X, ZHENG B, et al.Efficient reverse top-k boolean spatial keyword queries on road networks [J].IEEE Transactions on Knowledge & Data Engineering, 2015, 27(5):1205-1218.

[11] LIAN X, CHEN L.Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data [J].The VLDB Journal, 2009, 18(3): 787-808.

[12] BERNECKER T, EMRICH T, KRIEGEL H-P, et al.Efficient probabilistic reverse nearest neighbor query processing on uncertain data [J].Proceedings of the VLDB Endowment, 2011, 4(10): 669-680.

[13] YU G, GU Y, QIAO J, et al.Interval reverse nearest neighbor queries on uncertain data with Markov correlations [C]// ICDE ’13: Proceedings of the 2013 IEEE International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2013: 170-181.

[14] EMRICH T, KRIEGEL H-P, MAMOULIS N, et al.Reverse-nearest neighbor queries on uncertain moving object trajectories [M]// DASFAA 2014: Proceedings of the 19th International Conference on Database Systems for Advanced Applications, LNCS 8422.Berlin: Springer-Verlag, 2014: 92-107.

[15] JAMPANI R, XU F, WU M, et al.MCDB: a Monte Carlo approach to managing uncertain data[C]// SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.New York: ACM, 2008: 687-700.

This work is partially supported by the National Natural Science Foundation of China (61373036), the Program of Shanghai Subject Chief Scientist (15XD1503600).

XU Wei, born in 1991, M.S.candidate.His research interests include spatial keyword query, data mining,

LI Wengen, born in 1987, Ph.D.candidate.His research interests include spatial database, data mining.

ZHANG Yichao, born in 1982, Ph.D., assistant professor.His research interests include complex network, data mining.

GUAN Jihong, born in 1969, Ph.D., professor.Her research interests include spatial database, data mining.

Probabilistic bichromatic reverse-kNN query on road network

XU Wei, LI Wengen, ZHANG Yichao, GUAN Jihong*

(DepartmentofComputerScienceandTechnology,TongjiUniversity,Shanghai201804,China)

Considering the road network constraint and the uncertainty of moving object location, a new reverse-kNN query on road network termed Probabilistic Bichromatic Reverse-kNN (PBRkNN) was proposed to find a set of uncertain points and make the probability which thekNN of each uncertain point contains the given query point be greater than a specified threshold.Firstly, a basic algorithm called Probabilistic Eager (PE) was proposed, which used Dijkstra algorithm for pruning.Then, the Pre-compute Probabilistic Eager (PPE) algorithm which pre-computes thekNN for each point was proposed to improve the query efficiency.In addition, for further improving the query efficiency, the Pre-compute Probabilistic Eager External (PPEE) algorithm which used grid index to accelerate range query was proposed.The experimental results on the road networks of Beijing and California show that the proposed pre-computation strategies can help to efficiently process probabilistic bichromatic reverse-kNN queries on road networks.

reverse-kNN query; road network; Dijkstra algorithm; uncertainty

2016- 08- 12;

2016- 09- 13。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61373036);上海市優(yōu)秀學(xué)術(shù)帶頭人計(jì)劃項(xiàng)目(15XD1503600)。

徐偉(1991—),男,江蘇淮安人,碩士研究生,CCF會(huì)員,主要研究方向:空間關(guān)鍵詞查詢、數(shù)據(jù)挖掘; 李文根(1987—),男,四川南充人,博士研究生,CCF會(huì)員,主要研究方向:空間數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘; 張毅超(1982—),男,上海人,助理教授,博士，CCF會(huì)員,主要研究方向:復(fù)雜網(wǎng)絡(luò)、數(shù)據(jù)挖掘; 關(guān)佶紅(1969—),女,遼寧開(kāi)原人,教授,博士生導(dǎo)師,博士，CCF高級(jí)會(huì)員,主要研究方向:空間數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘。

1001- 9081(2017)02- 0341- 06

10.11772/j.issn.1001- 9081.2017.02.0341

TP311.13; TP392

A