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 the kNN 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 the kNN 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.
[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, ZVFLE 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 textual k nearest 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 reverse k nearest 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 reverse k-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 reverse k nearest 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.
2017, Vol. 37 
