徐 偉，李文根，張毅超，關佶紅

(同濟大學 計算機科學與技術系，上海 201804)

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

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

徐 偉，李文根，張毅超，關佶紅*

(同濟大學 計算機科學與技術系，上海 201804)

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

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

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

0 引言

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

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

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

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

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

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

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

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

1 問題定義

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

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

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

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

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

圖1 不確定區(qū)域

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

定義5 不確定空間點的范圍長度ul(UPONlength)。一個不確定空間點up=〈us0,us1,…,usm-1〉的范圍長度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，空間點PON集合A={p0,p1,…,pn-1},不確定空間點UPON集合B={up0,up1,…,upm-1},一個概率閾值? 和一個查詢點q∈A,PBR-kNN查詢的目標是查找B的一個子集Bp,滿足:

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

(2)

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

(3)

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

2 PE算法

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

2.1 索引結構

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

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

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

圖3 路網(wǎng)索引

圖4 邊及不確定空間點索引

2.2 查詢算法

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

P(us∈BRkNN(q))=0

(4)

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

證明 反證法：假設存在一個路段s〈edge,fromPos,toPos〉包含所有滿足條件的PON點，且fromPos不等于0，toPos不等于length。假設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也是滿足條件的點，與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也是滿足條件的點，與fromPos=0矛盾。

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

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

P(us∈BRkNN(q))=0

(5)

證明 因為n1和n2到q點的最短路徑都要經過n,由文獻[7]中引理1得n1?BRkNN(q),n2?BRkNN(q),由本文中的引理1得P(us∈BRkNN(q))=0。

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

1)尋找可能的upi。

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

1)初始化一個小頂堆。

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

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

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

假設訪問到了節(jié)點n:

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

b)對于pi驗證在range(n,q)范圍內的邊上是否有滿足條件的us(實際上是再次計算pi的kNN)。

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

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

2)驗證候選者upi。

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

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

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

3 PPE算法和PPEE算法

3.1 PPE算法

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

在預處理中，k設為可能取到的最大值。在實際生活中，k一般取到20就可以了。為了實驗需求，本文k取100。

3.2 PPEE算法

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

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

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

圖5 網(wǎng)格劃分

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

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

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

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

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

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

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

圖6 不確定性的索引

3.2.2 查詢算法

PPEE算法在PPE算法的基礎上對不確定性空間點作索引，它們的不同之處在于尋找候選不確定空間點集合?；诰W(wǎng)格索引的尋找候選不確定空間點的算法如下：

輸入 節(jié)點n;

輸出 候選不確定空間點。

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

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

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

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

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

4 實驗結果與分析

4.1 實驗數(shù)據(jù)

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

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

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

表1 實驗數(shù)據(jù)集

實驗參數(shù)設置如表2所示。

表2 實驗參數(shù)設置

實驗運行于配置為IntelCorei7- 4790KCPU@ 4.00GHz16GBRAM的計算機，采用Java環(huán)境。實驗結果為100次實驗的平均值。

4.2 實驗結果分析

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

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

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

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

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

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

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

圖9 集合A的個數(shù)與查詢時間的關系

圖10 集合B的個數(shù)與查詢時間的關系

圖11 UPON平均長度與查詢時間的關系

5 結語

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

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。

國家自然科學基金資助項目(61373036);上海市優(yōu)秀學術帶頭人計劃項目(15XD1503600)。

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

1001- 9081(2017)02- 0341- 06

10.11772/j.issn.1001- 9081.2017.02.0341

TP311.13; TP392

A