In this talk we address the problem of object recognition in 3D point cloud data. We first present a novel interest point extraction method that operates on range images generated from arbitrary 3D point clouds. Our approach explicitly considers the borders of the objects according transitions from foreground to background. We furthermore introduce a corresponding feature descriptor. We present rigorous experiments in which we analyze the usefulness our method for object detection. We furthermore describe a novel algorithm for constructing a compact representation of 3D point clouds. Our approach extracts an alphabet of local scans from the scene. The words of this alphabet are then used to replace recurrent local 3D structures, which leads to a substantial compression of the entire point cloud. We optimize our model in terms of complexity and accuracy by minimizing the Bayesian information criterion (BIC). Experimental evaluations on large real-world data show that our method allows us to accurately reconstruct environments with as few as 70 words. We finally discuss how this method can be utilized for object recognition and loop closure detection ind SLAM (Simultaneous Localization and Mapping).