Independent range sampling, revisited

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review



  • Peyman Afshani
  • ,
  • Zhewei Wei, Renmin University of China

In the independent range sampling (IRS) problem, given an input set P of n points in Rd, 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 ∩ R. The samples must satisfy inter-query 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 et al. [15], who proposed optimal structures for one-dimensional dynamic IRS problem in internal memory and one-dimensional 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 space-query tradeoffs for 3D halfspace, 3D dominance, and 2D three-sided queries. The second extension considers weighted IRS problem. Each point is associated with a real-valued weight, and given a query range R, a sample is drawn independently such that each point in P∩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.

Original languageEnglish
Title of host publication25th European Symposium on Algorithms, ESA 2017
EditorsKirk Pruhs, Christian Sohler
Number of pages14
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publication year1 Sep 2017
Article number3
ISBN (Electronic)9783959770491
Publication statusPublished - 1 Sep 2017
Event25th European Symposium on Algorithms, ESA 2017 - Vienna, Austria
Duration: 4 Sep 20176 Sep 2017


Conference25th European Symposium on Algorithms, ESA 2017
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • Data structures, Random sampling, Range sampling, Range searching

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 118168513