Probabilistic top- k range query processing for uncertain databases

2.1 Uncertain Top-k query processing

While research works on conventional top-k queries are mostly based on some deterministic scoring functions, the new factor of tuple membership probability in uncertain database makes evaluation of probabilistic top-k queries very complicated since the top-k answer set depends not only on the ranking scores of candidate tuples but also their probabilities. As for uncertain databases, there exist all kinds of uncertain top-k query semantics, among which the most influential include U-Topk [17], U-kRanks [17], PT-k [12], Global-Topk [20], Expected Rank [6], E-Score Rank [6], PTkS [14], and PTI query [19] etc. U-Topk returns the most probable k-tuple vector with the maximum aggregated probability of being top-k over all possible worlds. U-kRanks returns a list of k tuples such that the i ^th -ranked tuple has the highest aggregated probability in all possible worlds. These two query algorithm proposed in [17] are of inefficient due to lacking of pruning rules with an increasing possible world space. PT-k query returns those tuples which their top-k probabilities across all possible worlds are no less than a given probabilistic threshold q, which makes for approving performance without unfolding all possible worlds. Furthermore, a sampling method is developed to quickly compute an approximation with quality guarantee to the answer set by extracting a small sample of the uncertain dataset. Though the sampling method can lower the accuracy of answers, it can improve efficiency to a large degree. In [20], Zhang etc propose a Global-Topk query semantic that returns k highest-ranked tuples on the basis of their probabilities of being top-k answer set in all possible worlds. In [6], the expected rank of each tuple over all possible worlds is regarded as the ranking function for obtaining the answer set. E-Score Rank query takes the E-Score of each tuple as the ranking function to find the final answers. Lian and Chen [14] propose the probabilistic top-k star (PTkS) query, which aims to retrieve k objects in an uncertain database that are “closest" to a static/dynamic query point, considering both distance and probability aspects. In [18], the authors present the problem of Top-K frequent itemsets mining in sliding windows. Xiao et al. proposed a probabilistic top-l influential (PTI) query to identify the l most favorite objects [19]. From these definitions, we can see that a pivotal problem of uncertain top-k query is the calculation of possible world probability. Provided there is no good pruning technology, the performance of query may be comparative low with an exponential growth large possible world space. Consequently, it is necessary to exploit some efficient pruning strategies to reduce the computing of top-k probability for improving the performance of algorithm.

2.2 Range-based query processing

Range-based query processing has recently more and more attention in various practical applications as a result of the uncertainty, such as moving object tracking [10], location-based services [15] and computer games [21] etc. For the uncertainty of object, or privacy reasons, the records we want to query usually locate in a finite range region, such as an interval range, rectangular or circular range. Existing some rage-based query algorithms, e.g., range-based kNN query [11], range-based skyline query [15] etc. In [11], Hu and Lee firstly presented the RkNN solution for rectangular ranges. Lin et al. proposed the first range-based skyline query in LBS [15]. In [5], Cheng et al. firstly put forward probabilistic range query based on one-dimensional space. Tao et al. studied the uncertain range query for arbitrary probability distribution function in multi-dimensional space. To the best of our knowledge, there is very little works that has studied range-based uncertain top-k queries. Brodal [1] and Tao [16] developed a static and dynamic structure for the top-k range reporting problem, respectively. In this paper, we propose an uncertain top-k range query based on score attribute range, which retrievals the uncertain database by appointing a score range.

3.1 Uncertain date model

The fundamental difference between a traditional deterministic database and an uncertain database is that an uncertain relation represents a set of possible relation instances, rather than a single one [2]. Suppose an uncertain database DB, which is composed of a set of n tuples t _i  (1 ≤ i ≤ n). The uncertainty of every tuple t _i in the uncertain database DB is mainly represented by a confidence, i.e., its existence probability P (t _i ) in DB. For a given score ranking function s (t), the score of each t _i is denoted by s (t _i ). In fact, many uncertain data processing, including top-k query processing, pay attention to mainly two types of uncertainty, i.e., tuple-level uncertainty and attribute-level uncertainty. For tuple-level uncertainty, every tuple is uncertain while its attribute value (i.e. score) is deterministic. For attribute-level uncertainty, every tuple is deterministic while its attribute value is uncertain, and every attribute value corresponds to a probability. In a probabilistic database, there may exist some generation rules between tuples, such as exclusion or coexistence, but almost tuples are independent of each other. In this paper, we only consider tuple-level uncertainty with all tuples mutually independent.

There exist many works on modeling uncertain data. One of the most popular is the model based on possible world semantics [7], where an uncertain database is regarded as a set of possible world instances associated with their probabilities. Each possible world W is a subset of uncertain database tuples, and the set of all worlds is denoted by the possible world space Ω. The probability of each world is computed as the joint probability of the existence of the world’s tuples and the absence of all other database tuples. Since all tuples are mutually independent, we can obtain P ( W ) = ∏ t ∈ W P ( t ) ∏ t ∉ W P - ( t ) ,(1) where P - ( t ) = 1 - P ( t ), and ∑_W∈ΩP (W) =1.

With the aforementioned introductions and possible world semantics, in this subsection, we put forward the query semantics concerning probabilistic top-(k,l) query based on a given probability threshold q and Refs. [9, 20].

Definition 1. (Score dominating) Let s (t) be a score ranking function, for arbitrary two tuples t _i , t _j , if s (t _i ) > s (t _j ), then t _i  ≻  _s t _j .

Definition 2. (Top-k probability) Let DB be an uncertain database with possible world space Ω, k be a positive integer, s (t) be a score ranking function, and Top _k (W) be a set of k tuples in the front of possible world W on the basis of scoring function s (t). Then the probability of any tuple t in DB P_top-k (t, DB) can be defined as the summation of the probabilities of all possible worlds whose top-k answer set Top _k (W) contains t, i.e., P top - k ( t , DB ) = ∑ W ∈ Ω , t ∈ Top k ( W ) P ( W ) .(2)

Note that top-k answer sets may be of cardinality less than k for some possible worlds. We call such possible worlds as small worlds [20].

Definition 3. (Probabilistic top-(k, l) range query, PTR query) Let DB be an uncertain database, l be a positive integral number, s be a given score range constraint (e.g., s = [s₁, s₂]), q be a probability threshold, and P_top-k (t, DB) be the top-k probability of tuple t in DB. Then the top-(k,l) query over uncertain database DB returns l tuples which meet constraint s and have the maximum top-k probabilities but no less than q, i.e., { t | s ( t ) ∈ s , P top - k ( t , DB ) ≥ q } ,(3) and | { t | s ( t ) ∈ s , P top - k ( t , DB ) ≥ q } | = l .(4)

5.1 The algorithm framework

We now describe the probabilistic top-(k,l) range (i.e., PTR) query processing algorithm. The algorithm is presented in Algorithm 1. Initially, we empty a queue Q for saving the answer set (line 1). Clearly, one straightforward way to answer the uncertain query is in terms of its semantics and pruning techniques we proposed. That is, for each uncertain tuple in the uncertain database DB, we firstly remove some tuples which do not meet the score range constraint and probability upper bound constraint (i.e., probability threshold), based on Lemmas 1 and 2 (lines 2–6). After that, we can obtain a compact database with smaller cardinality. Then, we sort the database in accordance with the decreasing order based on

Algorithm 1.   PTR Query Processing

Input:

   an uncertain database DB with the cardinality n, an score ranking function s (t), a probability threshold q, a score range [s₁,s₂], two integral numbers k and l

Output;

   top-(k,l) query answer set Q

1:   initialize the top-(k,l) answer set Q← ∅;

2:   for each tuple t in DB do

3:     if (s (t) ∉ s or P (t) < q) then

4:       remove t from the database DB;

5:   sort for remaining tuples in DB in the decreasing order of the scoring function s (t);

6:   if∑ j = 0 k - 1 x t i , j < qthen

7:     prune the tuples which rank lower than t _i from the DB;

8:   for the remaining tuples in DB, compute the lower bound LB of top-k probability of tuple t _i in DB;

9:   ifLB ≥ qthen

10:     put t _i into top-(k,l) answer set Q;

11:   for the remaining tuples in DB, compute top-k probability of tuple tP_top-k (t, DB);

12:   select l tuples which have the maximum top-k probabilities but no less than q, and put them into the answer set Q;

13:   returnQ.

the scoring function s (t) and sequentially scan tuples in the database (line 7). Next, we further prune the dataset in light of the upper bound of top-(k,l) answer set (lines 8–10). Then for the remaining tuples in DB, we compute the lower bound of their top-k probability and insert the tuples whose LB are no less than q into answer set Q (lines 11–14). After that, for the remaining tuples in the uncertain database, we compute their probabilities of being top-k (line 15). Last but not least, on the basis of the top-k probabilities and q, we select l tuples which have the maximum top-k probabilities but no less than q, and put them into the answer set Q (line 16). Finally, the algorithm returns l as its output. Its correctness and complexity analysis are demonstrated in the following subsection.

5.2 Correctness and complexity analysis

In this section, we will concentrate on the proof of correctness of the PTR query processing algorithm and the analysis of complexity.

Theorem 3. The algorithm of top-(k,l) range query processing, i.e., PTR query processing, on the basis of pruning rules we proposed can accurately find out the optimal tuples we wanted.

Proof. From the definition of top-(k,l) range query, we can know that, for a score range constraint s and a probability threshold q, the query returns l tuples which meet constraint s and have maximum top-k probabilities but no less than q, i.e., { t | s ( t ) ∈ s , P top - k ( t , DB ) ≥ q } ,(5) and | { t | s ( t ) ∈ s , P top - k ( t , DB ) ≥ q } | = l .(6)

Note that the top-(k,l) range query processing functions only on remaining dataset after Pruning Rules 1, 2 and 3, so the three pruning techniques do not have an effect on the accuracy of the query. On the other hand, as previously mentioned, the number of PTR query answer set may larger than l on account of adding some tuples whose LB are no less than q. But however it happens, the answer set of the PTR query always reports the optimal tuples we wanted.

Thus, as long as Line 11 of Algorithm 1, correctly calculates the top-k probability of tuples, the query can return a valid top-(k,l) answer set. Based on the Proposition 1 in Ref. [4], we can know that Algorithm 2 accurately compute the probability of being top-k of tuples in Equation (4). □

Theorem 4. The complexity of PTR query processing algorithm, in the worst case, is max [O (n) , O (n₁ * n₁) , O (kn₂) , O (n₂logn₂)], where, n, n₁, n₂ are the cardinality of original uncertain database, compact database based on score value constraint pruning and probability threshold pruning, and dataset on the grounds of the upper bound of answer set pruning and top-k probability lower bound pruning, respectively.

Proof. Now we consider the complexity of the PTR query processing algorithm in the following. The most complicated operations are sorting the uncertain database, the upper bound of answer set pruning and the calculation of probability of being top-k of tuples. Assume that the cardinality of original indeterminate database is n, then the complexity of Pruning Rules 1 and 2 based on score range constraint and probability threshold is O (n). Next, we need to sort the remaining tuples in compact database, and the worst sorting operation is O (n₁ * n₁), where n₁ is the cardinality of the compact database. Then, the upper bound of answer set pruning takes O (n₁ * n₁) in the worst case to compute a dynamic programming table. The following lower bound pruning cost, in the worst case, is O (n₁ * n₁/2). In practice, the cost is far from it because the LB value may be zero for the lower-ranked tuples. Suppose the number of tuples in database is n₂ this moment. Then, Algorithm 2 takes O (kn₂) to calculate a dynamic programming table for the computing of top-k probability of tuples. Finally, the query algorithm takes O (n₂logn₂) in the worst case to maintain the sets Q. Consequently, the worst case time complexity of PTR query processing algorithm is max [O (n) , O (n₁ * n₁) , O (kn₂) , O (n₂logn₂)]. □

We use the International Ice Patrol (IIP) Iceberg Sightings Database1 to evaluate the effectiveness of PTR query over uncertain data in real-world applications. This dataset was used in previous works on ranking queries in uncertain data [12]. The IIP collects information on iceberg activity in the North Atlantic. Its mission is to measure, plot and predict iceberg drift, and broadcasting all known ice to prevent icebergs threatening. In this database, each sighting record is regarded as a tuple, including some of importance attributes, such as sighting source, position (longitude and latitude) and the number of the drifted days etc. Among them, the number of days of iceberg drift is dated from the IIP drift and deterioration computer model, which is pivotal in determining the status of icebergs. It is interesting to find the icebergs drifting for a long period. In this real experiment, we consider drifted days as attribute score of tuples for top-k queries, and the larger the score value is, the more important the tuple is.

Moreover, each sighting record in this database is associated with a confidence-level in terms of the source of sighting. There are six types of sighting source, including R/V (radar and visual), VIS (visual only), RAD (radar only), SAT-LOW (low earth orbit satellite), SAT-MED (medium earth orbit satellite) and SAT-HIGH (high earth orbit satellite). The differences in confidence-level of these sighting sources are classified and presented by probability values which are 0.8, 0.7, 0.6, 0.5, 0.4 and 0.3 to the six confidence-levels aforementioned, respectively.

The IIP_2009 database which contains 13,095 tuples is used to conduct the real experiment. We apply our PTR query and two other queries, i.e., PT-k query and Global-Topk query, on the uncertain dataset. The ranking order is the number of days of iceberg drift descending order. For PTR query, we set k = l = 10, q = 0.3 and s = [100, 500], that is, the researchers would want to observe those records whose drifted days are located at between 100 and 500, and their probabilities of being top-10 are no less than 0.3. We set k = 10 and q = 0.3 for PT-k query and k = 10 for Global-Topk query. The detailed information about the result sets of these three queries are showed in Tables 2 and 3, including attribute scores (drifted days), presence probabilities, top-10 probabilities and the corresponding ranks.

All tuples with top-10 probability at least 0.3 and drifted days between 100 and 500 are reported by the PTR query. As is shown in Table 1, the PTR query returns a set of 12 tuples {t₆₉₀₃, t₃₆₁₀, t₃₆₁₂, t₆₉₂₈, t₄₁₇₄, t₄₀₂₀, t₈₃₁₃, t₈₄₁₂, t₈₄₁₁, t₈₄₀₉, t₈₄₁₀, t₈₄₀₈} as the top-(10,10) answer set, among which t₆₉₀₃ and t₃₆₁₀ (as shown in bold) are obtained by probability lower bound pruning (Pruning Rule 4). Table 2 illustrates the results of PT-k query and Global-Topk query. Although tuple t₃₆₀₁ (as shown in bold) has the relatively low presence probability, it is regarded as a member of the answer set for the reason that its score (drifted days) is larger or equal than that of tuples in the result set. However, the tuple t₃₆₀₁ is not included in the answer set of the PT-k query and Global-Topk query despite the fact that t₃₆₀₁ has the largest score in the given score range. In other words, the two queries lose some relatively important tuples. From an real experiment viewpoint, it verifies also the effectiveness of PTR query, that is, the query can accurately report those optimal tuples users wanted.

The pruning ratios of the score range pruning and probability threshold pruning (i.e., pruning rules 1 and 2), the upper bound pruning of answer set (i.e., pruning technique 3) and probability lower bound pruning (i.e., pruning strategy 4) are 78.68%, 99.46% and 13.33%, respectively. The upper bound pruning of result set has a super pruning effect with the pruning ratio at least 99%. The effects of pruning of pruning techniques 1 and 2 rests with the score range and probability threshold user selected. Although the pruning rule 4 has a relatively lower pruning effect, it contributes to our PTR query capturing those important tuples missed by some uncertain top-k queries such as the PT-k query and Global-Topk query.

Furthermore, for the real-world uncertain database, we also conduct several experiments to evaluate the efficiency and effectiveness of PTR query under different parameter settings. The experimental results are shown in Figs. 1–3. Figure 1 pictures the query running time of the query with k value up to 1K (K = 1000, similarly hereinafter), where s = [100, 500], q = 0.3 and l = 100. As illustrated in this picture, the time increases almost linearly with k value, which is intuitive. In the other one trial, we illustrate the influence of probability threshold on the efficiency and effectiveness of PTR query. Figure 2 describes the experimental results under the setting of s = [100, 500] and k = l = 100. We can see intuitively from the picture that the execution time decreases as q value increases. However, the tendency of decreasing is not obvious for the reason that the size of IIP_2009 database is too small. In order to study the extendibility of PTR query, we will test the PTR query on massive synthetic data in the next subsection. In the last one experiment, we illustrate the effect of various score range s on the query time, where q = 0.3 and k = l = 100. The experimental result is described in Fig. 3. As shown, we can evaluate the performance of PTR query based on different score range users given. As a matter of fact, users can decide the range interval on the basis of their own preference.

In summary, our PTR query captures those important tuples missed by the PT-k query and Global-Topk query with better effectiveness. This experiment on real-world database elaborates also the differences among the various kinds of top-k queries for uncertain data. In the following, we will test the PTR query on synthetic datasets for evaluating its scalability and performance further.

6.2 Results on the synthetic dataset

In order to evaluate the query answering quality and the scalability of our proposed algorithms, we generate some kinds of synthetic data. Since uncertain top-(k,l) query algorithm needs to balance scores and probabilities of tuples, the experimental data should consider different distribution with respect to the scores and probabilities. In this section, we conduct the experiments on some synthetic datasets under different distributions. Their scores all follow the uniform distribution between zero and one hundred, and their probabilities obey uniform distribution, normal distribution and exponent distribution, respectively. There is no correlation between the score and the probability. Table 3 illustrates the experimental datasets we adopted under various distributions.

We still take query running time as the primary performance metric under different parameter settings. Note that the time includes the sorting time after Pruning Rules 1 and 2.