|
Published Articles >> Table of Contents >> Abstract
18th International Conference on Scientific and Statistical Database Management (SSDBM'06)
pp. 169-178
Probabilistic Ranking Queries on Gaussians
Christian Bohm, University of Munich, Germany
Alexey Pryakhin, University of Munich, Germany
Matthias Schubert, University of Munich, Germany
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SSDBM.2006.40
Send link to a friend
| Abstract |
|
In many modern applications, there are no exact values
available to describe the data objects. Instead, the feature
values are considered to be uncertain. This uncertainty is
modeled by probability distributions instead of exact feature
values. A typical application of such an uncertainty model
are moving objects where the exact position of each object
can be determined only at discrete time intervals. Queries
often involve the positions of objects between two such time
stamps or after the last known time stamp. Then the objects
are essentially uncertain unless the pattern of movement
is very simple (e.g. linear). One of the most important
probability density functions for those applications is the
Gaussian or normal distribution which can be defined by
a mean value and a standard deviation. In this paper, we
examine a new type of queries on uncertain data objects,
called probability ranking queries (PRQ). A PRQ retrieves
those k objects which have the highest probability of being
located inside a given query area. To speed up probabilistic
queries on large sets of uncertain data objects described
by Gaussians, we introduce a novel index structure called
Gauss-tree. Furthermore, we provide an algorithm for employing
the Gauss-tree to answer PRQs. In our experimental
evaluation, we demonstrate that the Gauss-tree achieves
a considerable efficiency advantage with respect to PRQs
compared to other applicable methods.
|
 Additional Information
|
Citation:
Christian Bohm, Alexey Pryakhin, Matthias Schubert,
"Probabilistic Ranking Queries on Gaussians,"
ssdbm,
pp. 169-178,
18th International Conference on Scientific and Statistical Database Management (SSDBM'06),
2006
|
|
