WANG Shengsheng, LI Yang, CHAI Sheng, BOLOU Bolou Dickson. SPHLU: An Efficient Algorithm for Processing PRkNN Queries on Uncertain Data[J]. Chinese Journal of Electronics, 2016, 25(3): 403-406. doi: 10.1049/cje.2016.05.002
Citation: WANG Shengsheng, LI Yang, CHAI Sheng, BOLOU Bolou Dickson. SPHLU: An Efficient Algorithm for Processing PRkNN Queries on Uncertain Data[J]. Chinese Journal of Electronics, 2016, 25(3): 403-406. doi: 10.1049/cje.2016.05.002

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

doi: 10.1049/cje.2016.05.002
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (197) PDF downloads(761) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return