Efficient monochromatic and bichromatic probabilistic reverse top-k query processing for uncertain big data

摘要

There has been an increasing growth in numerous applications that naturally generate large volumes of uncertain data. By the advent of such applications, the support of advanced analysis query processing such as the top-k and reverse top-k for uncertain big data has become important. In this paper, we model firstly probabilistic reverse top-k queries over uncertain big data for the discrete situation, in both monochromatic and bichromatic cases, denoted by MPRT and BPRT queries, respectively. We determine the partitions of solution space of MPRT queries and provide in theory a mathematical model for solving arbitrary dimensional data space. Additionally, we propose effective pruning heuristics to reduce the search space of BPRT queries. Moreover, efficient query procedures are presented seamlessly with integration of the proposed pruning strategies. Extensive experiments demonstrate the efficiency and effectiveness of our proposed approaches with various experimental settings.