Chromosomal aberrations or copy number variations (CNV), essentially large indels, are found by Comparative Genomic Hybridization (CGH) experiments, either ArrayCGH, SNPArrays or by mapping single reads from next generation sequencing experiments to a reference genome. Hidden Markov Models (HMM) are often used for identifying these CNV by segmenting observation sequences coming from CGH experiments. For efficiency reasons the parameters of a HMM are often estimated with maximum likelihood (EM-algorithm) and a segmentation is obtained with the Viterbi algorithm. This introduces considerable uncertainty in the segmentation, which can be avoided with Bayesian approaches integrating out HMM parameters using Markov Chain Monte Carlo (MCMC) sampling. While the advantages of Bayesian approaches have been clearly demonstrated, the likelihood based approaches are still preferred in practice for their lower running times; datasets coming from high-density arrays and next generation sequencing amplify these problems. We propose an approximate sampling technique, inspired by compression of discrete sequences in HMM computations and by kd-trees to leverage spatial relations between data points in typical data sets, to speed up the MCMC sampling. We achieve speed-ups of up to 90 on SNParrays.