|
中山大学学报(自然科学版) 2015
不确定性键值对数据模型及改进Top-k查询算法Keywords: 不确定性数据,Top-k查询,MapReduce,大数据,键值对数据 Abstract: 摘要 现有基于可能世界建模的Top-k算法难以适应大数据量和键值对(Key-Value)数据模型下的不确定性Top-k查询.研究首先建立了不确定性Key-Value数据模型;随后在已有U-TopK查询语义的基础上,提出了优化的EU-TopK(Early Terminated Uncertain Top-k Query)算法,该算法优先建立以最可能的Top-k元组为树根的可能世界树形结构,并利用两种优化策略来优化算法,降低了元组访问深度,使得该算法在时间复杂度上较原算法有所改进.此外采用MapReduce实现EU-TopK算法,使EU-TopK能够适应大数据分析.最后,通过实验验证EU-TopK算法功能性,并对其查询时间、扫描深度进行评价
|