Continuous Ranking Queries on Uncertain Streams - Ranking Queries on Uncertain Data - page 129

Chapter 6
Continuous Ranking Queries on Uncertain
Streams

The uncertain data stream model developed in Section 2.3.1 characterizes the dy-
namic nature of uncertain data. Conceptually, an uncertain data stream contains a
set of (potentially) infinite instances. To keep our discussion simple, we assume a
synchronous model in this chapter. That is, at each time instant t

( t > 0 ) , an instance

is collected for an uncertain data stream. A sliding window W t
ω

selects the set of in-

stances collected between time instants t and t . The instances of each uncertain

data stream in the sliding window can be considered as an uncertain object. We as-
sume that the membership probabilities of all instances are identical. Some of our
developed methods can also handle the case of different membership probabilities,
which will be discussed in Section 6.5. A continuous probabilistic threshold top- k
query reports, for each time instant t , the set of uncertain data streams whose top- k
probabilities in the sliding window W t

− ω

are at least p .
In this chapter, we develop four algorithms systematically to answer a proba-
bilistic threshold top- k query continuously: a deterministic exact algorithm, a ran-
domized method, and their space-efficient versions using quantile summaries. An
extensive empirical study using real data sets and synthetic data sets is reported
to verify the effectiveness and the efficiency of our methods. Although we focus
on monitoring probabilistic threshold top- k queries, the developed techniques can
be easily extended to monitor other probabilistic ranking queries defined in Sec-
tion 2.2.2 using the similar methods discussed in Chapter 5.

ω ( O )

6.1 Exact Algorithms

In this section, we discuss deterministic algorithms to give exact answers to prob-
abilistic threshold top- k queries. First, we extend the exact algorithm discussed in
Section 5.2 in answering a probabilistic threshold top- k query in one sliding window.
Then, we discuss how to share computation among overlapping sliding windows.

129