  We study coresets for various types of range counting queries on uncertain
data. In our model each uncertain point has a probability density describing
its location, sometimes defined as k distinct locations. Our goal is to
construct a subset of the uncertain points, including their locational
uncertainty, so that range counting queries can be answered by just examining
this subset. We study three distinct types of queries. RE queries return the
expected number of points in a query range. RC queries return the number of
points in the range with probability at least a threshold. RQ queries returns
the probability that fewer than some threshold fraction of the points are in
the range. In both RC and RQ coresets the threshold is provided as part of the
query. And for each type of query we provide coreset constructions with
approximation-size tradeoffs. We show that random sampling can be used to
construct each type of coreset, and we also provide significantly improved
bounds using discrepancy-based approaches on axis-aligned range queries.
