Database Reference
In-Depth Information
Chapter 4
Top-
k
Typicality Queries on Uncertain Data
An uncertain object
O
can be modeled as a set of instances generated by an under-
lying random variable
.
If there are a large number of instances in an uncertain
object, how can we understand and analyze this object?
An effective way is to
find the most typical instances among all instances of the uncertain object. In Sec-
tion 2.2.1, we applied the idea of typicality analysis from psychology and cognitive
science to ranking uncertain data, and modeled typicality for instances in uncertain
objects systematically. Three types of top-
k
typicality queries are formulated.
X
•
To answer questions such as “
Who are the top-k most typical NBA players?
”, the
measure of
simple typicality
is developed.
•
To answer questions like “
Who are the top-k most typical guards distinguishing
guards from other players?
”, the notion of
discriminative typicality
is proposed.
•
To answer questions like “
Who are the best k typical guards in whole representing
different types of guards?
”, the notion of
representative typicality
is used.
Computing the exact answer to a top-
k
typicality query requires quadratic time
which is often too costly for online query answering on uncertain objects with large
number of instances. In this chapter, we develop a series of approximation methods
for various situations.
•
The randomized tournament algorithm has linear complexity though it does not
provide a theoretical guarantee on the quality of the answers.
•
The direct local typicality approximation using VP-trees provides an approxima-
tion quality guarantee.
•
A Local Typicality Tree data structure can be exploited to index a large set of
instances. Then, typicality queries can be answered efficiently with quality guar-
antees by a tournament method based on a Local Typicality Tree.
An extensive performance study using two real data sets and a series of synthetic
data sets clearly shows that top-
k
typicality queries are meaningful and our methods
are practical.
51
