SPHLU: An Efficient Algorithm for Processing PRkNN Queries on Uncertain Data

WANG Shengsheng; LI Yang; CHAI Sheng; BOLOU Bolou Dickson

doi:10.1049/cje.2016.05.002

Volume 25 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2016 > 25(3): 403-406

WANG Shengsheng, LI Yang, CHAI Sheng, et al., “SPHLU: An Efficient Algorithm for Processing PRkNN Queries on Uncertain Data,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 403-406, 2016, doi: 10.1049/cje.2016.05.002

Citation:

WANG Shengsheng, LI Yang, CHAI Sheng, et al., “SPHLU: An Efficient Algorithm for Processing PRkNN Queries on Uncertain Data,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 403-406, 2016, doi: 10.1049/cje.2016.05.002

Citation:

PDF( 461 KB)

SPHLU: An Efficient Algorithm for Processing PRkNN Queries on Uncertain Data

doi: 10.1049/cje.2016.05.002

College of Computer Science and Technology, Key Laboratory of Symbolic Computing and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61133011, No.61303132, No.61103091, No.61202308), Science Technology Development Project of Jilin Province (No.20140101201JC, No.201201131), the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry of China and the Outstanding Youth Science Foundation of Jilin University.

More Information

Corresponding author: CHAI Sheng was born in Jilin Province, China, in 1976. He received the Ph.D. degree from Jilin University, China, in 2009. He is a lecturer in College of Computer Science and Technology of Jilin University. His main research interests include security software engineering and spatio-temporal database. (Email: chaisheng@jlu.edu.cn)
Received Date: 2014-04-14
Rev Recd Date: 2014-05-20
Publish Date: 2016-05-10

Abstract

Abstract

Query on uncertain data has received much attention in recent years, especially with the development of Location-based services (LBS). Little research is focused on reverse k nearest neighbor queries on uncertain data. We study the Probabilistic reverse k nearest neighbor (PRkNN) queries on uncertain data. It is succinctly shown that, PRkNN query retrieves all the points that have higher probabilities than a given threshold value to be the Reverse k-nearest neighbor (RkNN) of query data Q. The previous works on this topicmostly process with k > 1. Some algorithms allow the cases for k > 1, but the efficiency is inefficient especially for large k. We propose an efficient pruning algorithm-Spatial pruning heuristic with louer and upper bound (SPHLU) for solving the PRkNN queries for k > 1. The experimental results demonstrate that our algorithm is even more efficient than the existent algorithms especial for a large value of k.
- Spatial database,
- Uncertain data,
- R-tree,
- Probabilistic reverse k nearest neighbor queries

FullText(HTML)

References(12)

References

Flip Korn and S. Muth ukrishnan, "Influence sets based on reverse nearest neighbor queries", ACM SIGMOD International Conference on Management of Data, Dallas, Texas, USA, pp.201-212, 2000.

Anil Maheshwari, et al., "On reverse nearest neighbor queries", Proceedings of the 14th Canadian Conference on Computational Geometry, Alberta, Canada, pp.128-132, 2002.

I. Stanoi, M. Riedewald, D. Agrawal and A. El Abbadi, "Discovery of influence sets in frequently updated databases", Proceedings of the 27th International Conference on Very Large Data Bases, pp.99-108, 2001.

Y. Tao, D. Papadias and X. Lian," Reverse knn search in arbitrary dimensionality", Proceedings of the Thirtieth International Conference on Very Large Data Bases, pp.744-755, 2004.

Wei Wu, Fei Yang, et al., "Finch: Evaluating reverse knearestneighbor queries on location data", The International Journal on Very Large Data Bases, Vol.1, No.1, pp.1056-1067, 2008.

Y. Tong, L. Chen and B. Ding, "Discovering threshold-based frequent closed itemsets over probabilistic data", Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, pp.270-281, 2012.

Y. Tong, L. Chen, Y. Cheng and P. Yu, "Mining frequent itemsets over uncertain databases", The International Journal on Very Large Data Bases, Vol.5, No.11, pp.1650-1661, 2012.

X. Lian and L. Chen, "Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data", The International Journal on Very Large Data Bases, Vol.18, No.3, pp.787-808, 2009.

M. Cheema, et al., "Probabilistic reverse nearest neighbor queries on uncertain data", Proceedings of the 11th International Conference on Database Systems for Advanced Applications, pp.550-564, 2010.

T. Bernecker, et al., "Efficient probabilistic reverse nearest neighbor query processing on uncertain data", The International Journal on Very Large Data Bases, Vol.4, No.10, pp.669- 680, 2011.

Wang Shengsheng, CHAI Sheng and LV Qiannan, "A pruning based continuous RkNN query algorithm for large k", Chinese Journal of Electronics, Vol.21, No.3, pp.523-527, 2012.

Wang Shengsheng and Liu Dayou, "An efficient method for calculating qualitative spatial relations", Chinese Journal of Electronics, Vol.18, No.1, pp.42-46, 2009.

Relative Articles

Supplements(0)

Cited By

Proportional views