Top-k Query Calculations on Uncertain Dataset under MapReduce Framework
Hua Chen · 2013
Top-k query is commonly used in the management and application on uncertain data.And the Top-k query semantics base on parameterized ranking functions(PRF) is the unified approach of various query semantics proposed in recent years.Aiming at the massive uncertain dataset,an effective method for the Top-k query based on MapReduce is proposed.Through the analysis on the Top-k query semantics of parameterized ranking functions,an algorithm is presented to get the upper bound of an un-retrieved tuple.In this way,the pruning strategy is used to get the Top-k tuples without retrieving every tuple in the dataset.Furthermore,two different strategies are presented to implement the proposed algorithm under the MapReduce computing model in Hadoop.Finally,two groups of experiments are performed aiming at a single-machine environment and the Hadoop distributed computing platform.The experimental results show that the proposed algorithm is more effective to deal with the Top-k queries for the massive uncertain data on running time.