Name
Abstract | ||
|---|---|---|
This invited paper summarizes our results on the “independent range sampling” problem in the RAM computation model. The input is a set P of n points in R. Given an interval q = [x, y] and an integer t ≥ 1, a query returns t elements uniformly sampled (with/without replacement) from P ∩ q. The sampling result must be independent from those returned by the previous queries. The objective is to store P in a structure for answering all queries efficiently. If no updates are allowed, there is a trivial O(n)-size structure that guarantees O(log n + t) query time. The problem is much more interesting when P is dynamic (allowing both insertions and deletions). The state of the art is a structure of O(n) space that answers a query in O(t log n) time, and supports an update in O(log n) time. We describe a new structure ofO(n) space that answers a query inO(log n+ t) expected time, and supports an update in O(log n) time. |
Year | Venue | Field |
|---|---|---|
2015 | IEEE Data Eng. Bull. | Integer,Data mining,Binary logarithm,Combinatorics,Computer science,Sampling (statistics),Computation |
DocType | Volume | Issue |
Journal | 38 | 3 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaocheng Hu | 1 | 218 | 11.94 |
| Miao Qiao | 2 | 90 | 5.04 |
| Yufei Tao | 3 | 7231 | 316.71 |