This paper presents results of a system performing visual 6-D relocalisation at every single frame and in real time, such as is useful in re-exploration of scenes or for loop-closure in earnest. Our method uses ideas from fast state-of-the-art binary descriptors combined with a Locality-Sensitive-Hashing technique to perform nearest-neighbour search as well as a 3D validation and sampling strategy. Albeit appealing for speed and memory footprint reasons, binary descriptors lead to a weak discrimination response which produces several false positive matches. This results in having to invest longer in removing outliers to compute a valid pose than when using more expensive descriptors. To alleviate this problem we propose a geometric validation stage that assists in the selection of good sample matches and benefits from the depth information available in depth cameras such as RGB-D or stereo. Our experiments suggest the feasibility of our approach with a relocalisation performance of 73% while running at 54Hz. Furthermore, in our tests, our system reduces in 95% the memory footprint compared to a system using conventional floating-point descriptors.