Pervasive Augmented Reality (AR) requires accurate pose registration of the device in real-time at a neighbourhood-to-city scale. At such a scale, most pose registration techniques suffer from exponential computational and storage costs and a significant data collection burden. This paper introduces AnchorLoc, a framework that relies on visual anchors (stable and highly recognisable visual elements in a scene) to perform fast and accurate pose registration. Anchorloc automatically identifies these anchors from large image sequences to optimise the search space in later image retrieval and pose registration. As such, it significantly improves the computational efficiency of existing hierarchical localisation pipelines without compromising accuracy. We collect a large-scale localisation dataset consisting of image sequences and 3D reconstruction of a university campus. AnchorLoc reduces localisation runtime by 83% on our campus dataset and 69% on the Cambridge Landmarks dataset without significantly increasing mean pose estimation errors. It is also more accurate and faster than SLD, a localisation algorithm that takes a comparable approach at the keypoint level. This work informs the development of more efficient pervasive AR applications that rely on both absolute and relative camera pose tracking on image sequences.