Conclusions - Ranking Queries on Uncertain Data - page 214

mileage”. Then we should return all used cars that best match the user's preference.
Although there are many studies on preference queries on deterministic data [198,
199, 200, 201, 197], to the best of our knowledge, there are very limited related
studies on preference queries on uncertain data.
Let us take skyline queries, an important category of preference queries, as an ex-
ample. In a deterministic data set, given two tuples t 1 and t 2 in attributes A 1 ,···, A m ,

. ≺ . ≤ ≤ ≺

t 1 dominates t 2 if t 1 denotes the preference order in

attribute a i . A skyline query returns the tuples that are not dominated by any other
tuple in the data set. Pei et al. [21] extend skyline queries from deterministic data
to the basic uncertain object model. Given a set of independent uncertain objects,
the skyline probability of an object O is the probability that O is a skyline object in
possible worlds. Given a probability threshold p , a probabilistic threshold skyline
query finds the objects whose skyline probabilities are at least p .
As future study, it is interesting to examine how to answer probabilistic threshold
skyline queries on the three extended uncertain data models proposed in this work.
First, a continuous probabilistic threshold skyline query on a set of uncertain data
streams returns, for each time instant, the objects whose skyline probabilities in the
sliding window are at least p . This is useful for applications where data is dynamic
and uncertain in nature.
Moreover, the probabilistic linkage model proposed in our study is an extension
of the basic uncertain object model by considering inter-object dependencies. Sky-
line queries are useful in some applications of the probabilistic linkage model. For
instance, in Example 2.12, a medical expert may be interested in finding the skyline
patients in two attributes age of hospitalization and age of death . It is non-trivial to
compute object skyline probabilities in the probabilistic linkage model due to the
inter-object dependencies.
Last, in the uncertain road network model, there are multiple paths between two
end vertices specified by users. Sometimes, we may want to find the skyline paths
that have short travel time and short geographic distances. Therefore, probabilistic
skyline queries are highly useful in such applications.

A i t 2 A i (1 i m ), where