Abstract
In the independent range sampling (IRS) problem, given an input set P of n points in R^d, the task is to build a data structure, such that given a range R and an integer t >= 1, it returns t points that are uniformly and independently drawn from P cap R. The samples must satisfy interquery independence, that is, the samples returned by every query must be independent of the samples returned by all the previous queries. This problem was first tackled by Hu, Qiao and Tao in 2014, who proposed optimal structures for onedimensional dynamic IRS problem in internal memory and onedimensional static IRS problem in external memory.
In this paper, we study two natural extensions of the independent range sampling problem. In the first extension, we consider the static IRS problem in two and three dimensions in internal memory. We obtain data structures with optimal spacequery tradeoffs for 3D halfspace, 3D dominance, and 2D threesided queries. The second extension considers weighted IRS problem. Each point is associated with a realvalued weight, and given a query range R, a sample is drawn independently such that each point in P cap R is selected with probability proportional to its weight. Walker's alias method is a classic solution to this problem when no query range is specified. We obtain optimal data structure for one dimensional weighted range sampling problem, thereby extending the alias method to allow range queries.
BibTeX  Entry
@InProceedings{afshani_et_al:LIPIcs:2017:7859,
author = {Peyman Afshani and Zhewei Wei},
title = {{Independent Range Sampling, Revisited}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {3:13:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7859},
URN = {urn:nbn:de:0030drops78592},
doi = {10.4230/LIPIcs.ESA.2017.3},
annote = {Keywords: data structures, range searching, range sampling, random sampling}
}
Keywords: 

data structures, range searching, range sampling, random sampling 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017) 
Issue Date: 

2017 
Date of publication: 

31.08.2017 