Database Reference
In-Depth Information
•
The
object set
probabilistic ranking queries apply the query condition to each
object set and return the object set that satisfy the query. We defer the discussion
on ranking uncertain object sets to Section 2.3.3 in the context of uncertain road
networks.
2.2.1 Ranking Instances in An Uncertain Object
Given an uncertain object with a large number of instances that are samples taken
from an underlying random variable, how can we understand and analyze this ob-
ject? An effective way is to find the most typical instances among all instances of
the uncertain object. We develop a class of top-
k
typicality queries which can serve
for this purpose.
Example 2.4 (Top-k typicality queries).
Jeff is a junior basketball player who dreams to play in the NBA. As the NBA has
more than
400
active players, they are quite diverse. Jeff may want to know some
representative examples of NBA players. Top-k typicality queries can help.
We can model the group of NBA players as an uncertain object in the space of
technical statistics, which can be described by a likelihood function. Each player is
an instance of the uncertain object.
•
Top-k simple typicality queries.
Jeff asks, “
Who are the top-3 most typical NBA players?
” The player who has
the maximum likelihood of being NBA players is the most typical. This leads to
our first typicality measure - the
simple typicality
. A top-k simple typicality query
finds the k most typical instances in an uncertain object.
•
Top-k discriminative typicality queries.
Jeff is particularly interested in becoming a guard. “
Who are the top-3 most
typical guards distinguishing guards from other players?
” Simple typicality on
the set of guards is insufficient to answer the question, since it is possible that a
typical guard may also be typical among other players. Instead, players that are
typical among all guards but are not typical among all non-guard players should
be found.
In order to address this demand, we can model the group of guards as a target
uncertain object O
g
and the set of other players as the other uncertain object
O. The notion of
discriminative typicality
measures how an instance is typical in
one object but not typical in the other object. Given two uncertain objects O and
S, let O be the target object, a top-k discriminative typicality query finds the k
instances with the highest discriminative typicality values in O.
•
Top-k representative typicality queries.
NBA guards may still have some sub-groups. For example, the fresh guards and
the experienced guards, as well as the shooting guards and the point guards. Jeff
wants to learn different types of guards, without a clear idea about what types
