With the rapid growth of uncertain data, query processing on uncertain data has become an important research area. Although considerable efforts have been devoted to answering certain types of queries on uncertain data, how to perform restricted skyline (rskyline) queries on uncertain data remains an open problem. To fill the gap, this paper studies the all rskyline probabilities (ARSP) problem, which aims to compute the probability of each uncertain tuple appearing in the rskyline, and the most-likely rskyline (MLRS) problem, which aims to identify a set of uncertain tuples with the highest probability of being the rskyline. We prove that no algorithm can solve the ARSP problem in strongly subquadratic time, unless the orthogonal vectors conjecture fails and the MLRS problem is NP-hard. When $$\mathcal {F}$$ is a set of linear scoring functions subject to a set of linear constraints on weights, we propose two efficient algorithms for solving the ARSP problem. For a special linear constraint, we further develop an algorithm with sublinear query time. For the MLRS problem, we first design a series of data reduction rules to reduce the input data size. Then, we propose two exact algorithms with different search strategies, as well as a local search based approximation algorithm to further improve the time efficiency. Experimental results show that these two problems provide complementary and comprehensive perspectives on rskylines of uncertain datasets, and demonstrate the effectiveness and efficiency of the proposed algorithms.

Multi-criteria decision-making usually requires finding a small representative set from the database. A popular method, the regret minimization set (RMS) query, returns a size$r$subset$S$of the full dataset$D$that minimizes the regret-ratio (the difference between the scores of top-1 in$S$and top-1 in$D$, for any utility function). RMS is not shift invariant, causing inconsistency in results. Further, the regret-ratio is often a “made up” number and users may mistake its absolute value. Instead, users do understand the notion of rank. Therefore, in this paper, we consider finding a fixed-size set$S$to minimize the maximum rank-regret (the rank of top-1 of$S$in the sorted list of$D$) over all possible utility functions, called the rank-regret minimization (RRM) problem, which is shift invariant. In 2D space, we design an exact algorithm 2DRRM for RRM. In HD space, we propose an approximate algorithm HDRRM with theoretical guarantees on rank-regret. It combines the ideas of space discretization and clustering. Extensive experiments verify the efficiency and effectiveness of our algorithms. In particular, HDRRM always has the best output quality in experiments.

A top-k query retrieves the k tuples with highest scores according to a user preference, defined as a scoring function. It is difficult for a user to precisely specify the scoring function. Instead, obtaining the distribution on scoring functions, i.e., the preference distribution, has been extensively explored in many fields. Motivated by this, we introduce the uniform (r,k)-hit (UrkHit) problem. Given a preference distribution, UrkHit aims to select a representative set of r tuples to maximize the probability of containing a tuple attractive to the user. We say a tuple attracts a user, if it is a top-k tuple for the scoring function adopted by the user. Further, we generalize UrkHit and propose the (r,k)-hit (rkHit) problem with an additional penalty function to model the user satisfaction with the tuple ranked i-th. rkHit aims to maximize the expected user satisfaction with the representative set. In 2D space, we design an exact algorithm 2DH for rkHit, indicating rkHit is in P for d=2. We show that rkHit is NP-hard when d\ge3. In 3D space, assuming a uniform preference distribution, we propose a (1-1/e)-approximation algorithm 3DH based on space partitioning. In addition, we propose an approximate algorithm MDH suitable for any dimension and distribution, which creatively combines the ideas of sampling and clustering. It relaxes the approximation guarantee slightly. Comprehensive experiments demonstrate the efficiency and effectiveness of our algorithms.

Multi-criteria decision-making often requires finding a small representative set from the database. A recently proposed method is the regret minimization set (RMS) query. RMS returns a size$r$subset$S$of dataset$D$that minimizes the regret- ratio (the difference between the score of top-1 in$S$and the score of top-l in$D$, for any possible utility function). RMS is not shift invariant, causing inconsistency in results. Further, existing work showed that the regret-ratio is often a “made up” number and users may mistake its absolute value. Instead, users do understand the notion of rank. Thus it considered the problem of finding the minimal set$S$with a rank-regret (the rank of top-l tuple of$S$in the sorted list of$D$) at most$k$, called the rank-regret representative (RRR) problem. Corresponding to RMS, we focus on the min-error version of RRR, called the rank-regret minimization (RRM) problem, which finds a size$r$set to minimize the maximum rank-regret for all utility functions. Further, we generalize RRM and propose the restricted RRM (i.e., RRRM) problem to optimize the rank-regret for functions restricted in a given space. Previous studies on both RMS and RRR did not consider the restricted function space. The solution for RRRM usually has a lower regret level and can better serve the specific preferences of some users. Note that RRM and RRRM are shift invariant. In 2D space, we design a dynamic programming algorithm 2DRRM to return the optimal solution for RRM. In HD space, we propose an algorithm HDRRM that introduces a double approximation guarantee on rank-regret. Both 2DRRM and HDRRM are applicable for RRRM. Extensive experiments on the synthetic and real datasets verify the efficiency and effectiveness of our algorithms. In particular, HDRRM always has the best output uuality in experiments.