I implelemented a reversible jump MCMC sampler  for two dimensional Mondrian Processes  in R.
Mondrian Processes are a kind of nonparametric Bayesian model for relational learning. The samples drawn from Mondrian Processes are kd-trees. Below is a plot of a sample drawn from a two dimensional Mondrian Process.
As a special case, two dimensional Mondrian Processes can be used for nonparametric Bayesian co-clustering, where the number of co-clusters can be inferred from observed data. I used reversible jump MCMC  for Mondrian Process inference.
 Daniel M. Roy and Yee W. Teh. The Mondrian Process. NIPS. 2008.
 Pu Wang, Kathryn B. Laskey, Carlotta Domeniconi and Michael I. Jordan. Nonparametric Bayesian Co-clustering Ensembles. SDM. 2011.
 Peter J. Green. Reversible Jump Markov Chain Monte Carlo Computation and Bayesian Model Determination. Biometrika. 82(4):711-732. 1995.