Math @ Duke

Publications [#235556] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Cheng, SW; Yi, K, Range searching on uncertain data,
ACM Transactions on Algorithms, vol. 8 no. 4
(2012), ISSN 15496325 [doi]
(last updated on 2017/12/15)
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 onedimensional 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 nearlinear 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. © 2012 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

