Generalized Stratified Sampling Using the Hilbert Curve

Mauro Steigleder and Michael McCool
University of Waterloo

This paper appears in issue Volume 8, Number 3.
Purchase this issue from the akpeters.com web site.

Abstract

Stratified sampling is a widely used strategy to improve convergence in Monte Carlo techniques. The efficiency of a stratification technique mainly depends on the coherence of the strata. This paper presents an approach to generate an arbitrary number of coherent strata, independently of the dimensionality of the domain, using the Hilbert space-filling curve. Using this approach, it is possible to draw an arbitrary number of stratified samples from higher dimensional spaces using only one-dimensional stratification. This technique can also be used to generalize nonuniform stratified sampling. Source code is available online.

Author Information

Mauro Steigleder, School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada msteigleder@cgl.uwaterloo.ca

Michael McCool, School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada mmccool@cgl.uwaterloo.ca

Source Code

The following C source file contains an implementation of the stratified sampling technique described in the paper, in a demo program that samples a combination of Gaussians: hilbert.c (4K HTML text)

BibTeX Entry

@article{SteiglederMcCool03,
  author = "Mauro Steigleder and Michael McCool",
  title = "Generalized Stratified Sampling Using the Hilbert Curve",
  journal = "journal of graphics, gpu, and game tools",
  volume = "8",
  number = "3",
  pages = "41-47",
  year = "2003",
}