Computer Science ›› 2016, Vol. 43 ›› Issue (3): 225-230.doi: 10.11896/j.issn.1002-137X.2016.03.041

Previous Articles     Next Articles

Top-k Query Calculation of Uncertain Data Based on Uncertainty Theory

GUO Chang-you, ZHENG Xue-feng and GAO Xiu-lian   

  • Online:2018-12-01 Published:2018-12-01

Abstract: The Top-k query in the uncertain data set based on parametric ranking function has been focused in recent years.This paper gave out a new solution.The tuples of uncertain data set is modeled as uncertain network,Top-k query of the orderly tuples is transformed equivalently into uncertain measure relations of edges in corresponding sample fi-gures,and the sample figures are classified according the ranking position of edge contained in them.So the Top-k query in the uncertain data set based on parametric ranking function is transformed equivalently into different limited query with different Top-k value.The proposed algorithm avoids calculating the ranking uncertain measure values of all tuples in the sample figures,and improves the computation efficiency of Top-k query in uncertain figure.Theoretical analysis and experimental results show that the proposed Top-k query algorithm can solve Top-k query calculation of uncertain data from the uncertainty perspective.

Key words: Uncertain networks,Uncertain measure,Sample graph index, Top-k query

[1] Adar E,Re C.Managing Uncertainty in Social Networks[J].IEEE Data Engineering Bulletin,2007,0(2):15-22
[2] Ghosh J,Ngo H,Yoon S,et al.On a Routing Problem Within Probabilistic Graphs and Its Application to Intermittently Connected Networks[C]∥Proceedings of INFOCOM’07.[S.1.]:IEEE Press,2007:216-222
[3] Potamias M,Bonchi F,Gionis A,et al.Nearest-neighbor Queries in Probabilistic Graphs[EB/OL].(2009-10-21).http://www.cs.bu.edu
[4] Soliman M A’Ilyas I F.Ranking with Uncertain Scores[C]∥Proc of the 25th IEEE International Conference on Data Engineering.Shanghai,China,2009:317-328
[5] Hua Ming,Pei Jian,Liu Xue-min.Ranking Queries on UncertainData[J].The International Journal on Very Large Data Bases,2011,20(1):129-153
[6] Jestes J,Cormode G,Li Fei-fei,et al.Semantics of Ranking Queries for Probabilistic Data[J].IEEE Trans on Knowledge and Data Engineering,2011,23(12):1903-1917
[7] Ge Tingj-ian,Zdonik S,Madden S.Top-k Queries on Uncertain Data:On Score Distribution and Typical Answers[C]∥Proc of the ACM SIGMOD International Conference on Management of Data.Providence,USA,2009:375-388
[8] Li Jian,Saha B,Deshpande A.An Unified Approach to Ranking in Probabilistic Databases[J].The VLDB Journal,2011,20(2):249-275
[9] Li Jian,Deshpande A.Ranking Continuous Probabilistic Datasets[J].Proceedings of the VLDB Endowment,2010,3(1/2):638-649
[10] Wang Chong-hai,Yuan Li-yan,You Jia-huai,et al.On Pruning for Top-k Ranking in Uncertain Databases[J].Proceedings of the VLDB Endowment,2011,4(10):598-609
[11] Lu Xin,Chen Hua-hui,Dong Yi-hong,et al.Top-k Query Calculations on Uncertain Dataset under MapReduce Framework[J].Pattem Recognition and Aitificial Intelligence,2013(7):695-704(in Chihese) 卢鑫,陈华辉,董一鸿,等.MapReduce框架下的不确定数据Top-k查询计算[J].模式识别与人工智能,2013(7):695-704
[12] Liu B.Uncertainty Theory(2nd edition)[M].Springer-Verlag,Berlin,2007
[13] Liu B.Uncertainty Theory:A Branch of Mathematics for Mo-deling Human Uncertainty[M].Springer-Verlag,Berlin,2010
[14] Liu Bao-ding.Uncertainty Distribution and Independence of Uncertain Processes[J].Fuzzy Optimization and Decision Making,2014,13(3):259-271
[15] Zhou Jian,Chen Lu,Wang Ke.Path Optimality Conditions for Minimum Spanning Tree Problem with Uncertain Edge Weights,International Journal of Uncertainty[J].Fuzziness and Knowledge-Based Systems,2015,23(1):49-71
[16] Gao X L.Uncertain relations on a finite set and their properties[J].Pure and Applied Mathematics Journal,2014, 3(1):13-19
[17] Gao X L,Gao Y.Connectedness Index of Uncertainty Graphs,International Journal of Uncertainty[J].Fuzziness and Know-ledge-Based Systems,2013,21(1):127-137
[18] Gao X.Some properties of continuous uncertain measure,International Journal of Uncertainty[J].Fuzziness and Knowledge-Based Systems,2009,17(3):419-426
[19] Gao X,Gao Y,Ralescu D.On Liu’s Inference Rule for Uncertain Systems,International Journal of Uncertainty[J].Fuzziness and Knowledge-Based Systems,2010,18(1):1-11
[20] Gao Y,Yang L X,et al.On Distribution Function of the Diameter in Uncertain Graph[J].Information Sciences, 2015,296(1):61-74
[21] Gao Y.Shortest Path Problem with Uncertain Arc Lengths[J].Computers and Mathematics with Applications,2015,296(1):61-74
[22] Liu B.Some research problems in uncertainty theory[J].Journal of Uncertain Systems,2009,3(1):3-10
[23] Luo Jun-zhou,Jin Jia-hui,Song Ai-bo,et al.Cloud computing:architecture and key technologies[J].Journal on Communications,2011,2(7):3-21(in Chinese) 罗军舟,金嘉晖,宋爱波,等.云计算:体系架构与关键技术[J].通信学报,2011,2(7):3-21
[24] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113
[25] Zaharia M,Chowdhury M,Franklin M J,et al.Spark:clustercomputing with working sets[C]∥Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.2010:10
[26] Neumeyer L,Robbins B,Nair A,et al.S4:Distributed stream computing platform[C]∥2010 IEEE International Conference on Data Mining Workshops (ICDMW).IEEE,2010:170-177
[27] Wieder A,Bhatotia P,Post A,et al.Brief announcement:modelling MapReduce for optimal execution in the cloud[C]∥Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing.New York,NY,USA:ACM,2010:408-409
[28] Zheng Q.Improving MapReduce fault tolerance in the cloud[C]∥2010 IEEE International Symposium on Parallel & Distributed Processing,Workshops and Phd Forum (IPDPSW).Atlanta,GA:IEEE,2010:1-6
[29] Ding Lin-lin,Xin Jun-chang,Wang Guo-ren,et al.Efficient Skyline Query Processing of Massive Data Based on Map-Reduce[J].Chinese Journal of Computers,2011,34(10):1785-1796(in Chinese) 丁琳琳,信俊昌,王国仁,等.基于Map-Reduce的海量数据高效 Skyline查询处理[J].计算机学报,2011,34(10):1785-1796
[30] Li Ling-juan,Zhang Min.Research on Algorithms of Mining AssociationRule under Cloud Computing Environment[J].Computer Technology and Development,2011,21(2):43-46(in Chinese) 李玲娟,张敏.云计算环境下关联规则挖掘算法的研究[J].计算机技术与发展,2011,21(2):43-46
[31] Zeng Qing-sen,Huang Xian-ying.Fast Data Mining AlgorithmBased on FP-tree[J].Journal of Chongqing Institute of Techno-logy(Natural Science),2009,3(10):72-76(in Chinese) 曾庆森,黄贤英.基于FP-tree的快速数据挖掘算法[J].重庆工学院学报(自然科学版),2009,23(10):72-76

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!