Name
Abstract | ||
|---|---|---|
Querying uncertain data has emerged as an important problem in data management due to the imprecise nature of many measurement data. In this article, we study answering range queries over uncertain data. Specifically, we are given a collection P of n uncertain points in ℝ, each represented by its one-dimensional probability density function (pdf). The goal is to build a data structure on P such that, given a query interval I and a probability threshold τ, we can quickly report all points of P that lie in I with probability at least τ. We present various structures with linear or near-linear space and (poly)logarithmic query time. Our structures support pdf's that are either histograms or more complex ones such as Gaussian or piecewise algebraic. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2344422.2344433 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
one-dimensional probability density function,measurement data,probability threshold,uncertain data,query interval,logarithmic query time,collection p,n uncertain point,data structure,data management,range searching,data structures | Histogram,Data structure,Range searching,Range query (data structures),Theoretical computer science,Uncertain data,Logarithm,Probability density function,Piecewise,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 4 | 1549-6325 |
Citations | PageRank | References |
9 | 0.53 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Siu-Wing Cheng | 2 | 973 | 94.74 |
| Ke Yi | 3 | 1659 | 77.79 |