Probabilistic bichromatic reverse-kNN query on road network

doi:10.11772/j.issn.1001-9081.2017.02.0341

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (2): 341-346.DOI: 10.11772/j.issn.1001-9081.2017.02.0341

Previous Articles Next Articles

Probabilistic bichromatic reverse-kNN query on road network

XU Wei, LI Wengen, ZHANG Yichao, GUAN Jihong

Department of Computer Science and Technology, Tongji University, Shanghai 201804, China

Received:2016-08-12 Revised:2016-09-13 Online:2017-02-10 Published:2017-02-11
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61373036), the Program of Shanghai Subject Chief Scientist (15XD1503600).

路网中位置不确定的二元反kNN查询

徐伟, 李文根, 张毅超, 关佶红

同济大学计算机科学与技术系, 上海 201804

通讯作者: 关佶红,jhguan@tongji.edu.cn
作者简介:徐伟(1991-),男,江苏淮安人,硕士研究生,CCF会员,主要研究方向:空间关键词查询、数据挖掘;李文根(1987-),男,四川南充人,博士研究生,CCF会员,主要研究方向:空间数据库、数据挖掘;张毅超(1982-),男,上海人,助理教授,博士,CCF会员,主要研究方向:复杂网络、数据挖掘;关佶红(1969-),女,辽宁开原人,教授,博士生导师,博士,CCF高级会员,主要研究方向:空间数据库、数据挖掘。
基金资助:
国家自然科学基金资助项目（61373036）；上海市优秀学术带头人计划项目（15XD1503600）。

Abstract

Abstract:

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.

Key words: reverse-kNN query, road network, Dijkstra algorithm, uncertainty

摘要：

针对路网限制和物体位置的不确定性，提出了路网中位置不确定的二元反kNN查询（PBRkNN），旨在查找一组位置不确定的点，使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题，首先提出一种基于Dijkstra进行剪枝处理的基本算法，即PE算法；接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度，即PPE算法；而为了进一步减小PPE算法中范围查询的开销，提出PPEE算法，利用网格索引来索引范围查询中要查询的不确定空间点，从而提升算法的效率。最后，在北京和加州路网数据集上进行了大量实验，结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。

关键词: 反kNN查询, 路网, Dijkstra算法, 不确定性

CLC Number:

XU Wei, LI Wengen, ZHANG Yichao, GUAN Jihong. Probabilistic bichromatic reverse-kNN query on road network[J]. Journal of Computer Applications, 2017, 37(2): 341-346.

徐伟, 李文根, 张毅超, 关佶红. 路网中位置不确定的二元反kNN查询[J]. 计算机应用, 2017, 37(2): 341-346.

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, 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.

Probabilistic bichromatic reverse-kNN query on road network

路网中位置不确定的二元反kNN查询

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CAO Yuhong, XU Hai, LIU Sun'ao, WANG Zixiao, LI Hongliang. Review of deep learning-based medical image segmentation [J]. Journal of Computer Applications, 2021, 41(8): 2273-2287.
[2]	PEI Yiyao, GUO Huiming, ZHANG Danpu, CHEN Wenbo. Robust 3D object detection method based on localization uncertainty [J]. Journal of Computer Applications, 2021, 41(10): 2979-2984.
[3]	FU Yu, WANG Hong. Virtual trajectory filling algorithm for location privacy protection [J]. Journal of Computer Applications, 2019, 39(8): 2318-2325.
[4]	HUO Zheng, ZHANG Kun, HE Ping, WU Yanbin. Crowdsourcing location data collection for local differential privacy [J]. Journal of Computer Applications, 2019, 39(3): 763-768.
[5]	YANG Chen, WANG Jieting, LI Feijiang, QIAN Yuhua. Support vector data description method based on probability [J]. Journal of Computer Applications, 2019, 39(11): 3134-3139.
[6]	FENG Jun, LI Dingsheng, LU Jiamin, ZHANG Lixia. Spatio-temporal index method for moving objects in road network based on HBase [J]. Journal of Computer Applications, 2018, 38(6): 1575-1583.
[7]	XIANG Min, CHEN Cheng. Traffic scheduling strategy based on improved Dijkstra algorithm for power distribution and utilization communication network [J]. Journal of Computer Applications, 2018, 38(6): 1715-1720.
[8]	WANG Wei, PEI Dong, FENG Zhang. The shortest path planning for mobile robots using improved A^* algorithm [J]. Journal of Computer Applications, 2018, 38(5): 1523-1526.
[9]	ZHAI Junhai, ZHANG Sufang, WANG Cong, SHEN Chu, LIU Xiaomeng. Big data active learning based on MapReduce [J]. Journal of Computer Applications, 2018, 38(10): 2759-2763.
[10]	HUO Zheng, CUI Honglei, HE Ping. k-CS algorithm: trajectory data privacy-preserving based on semantic location protection [J]. Journal of Computer Applications, 2018, 38(1): 182-187.
[11]	LI Jiajia, LIU Xiaojing, LIU Xiangyu, XIA Xiufeng, ZHU Rui. Improved time dependent fast travel time algorithm by dynamically selecting heuristic values [J]. Journal of Computer Applications, 2018, 38(1): 120-125.
[12]	HUO Zheng, WANG Weihong, CAO Yuhui. PTDC:privacy-aware trajectory data collection technology under road network constraint [J]. Journal of Computer Applications, 2017, 37(9): 2567-2571.
[13]	TANG Jianguo, WANG Jianghua. Classical cipher model based on rough set [J]. Journal of Computer Applications, 2017, 37(4): 993-998.
[14]	ZHANG Jie, YANG Chunyu, JU Fei, XU Xiaolong. Optimization of ordered charging strategy for large scale electric vehicles based on quadratic clustering [J]. Journal of Computer Applications, 2017, 37(10): 2978-2982.
[15]	BU Yu, REN Xiaofang, TANG Xuejun, SUN Ting. Face recognition method based on uncertainty measurement combined with 3D features extraction using active appearance model [J]. Journal of Computer Applications, 2016, 36(7): 1971-1975.