We present a novel “hybrid Hessian” six-degrees-of-freedom simultaneous localization and mapping (SLAM) algorithm. Our method allows for the smooth trade-off of accuracy for efficiency and for the incorporation of GPS measurements during real-time operation, thereby offering significant advantages over other SLAM solvers. Like other stochastic SLAM methods, such as SGD and TORO, our technique is robust to local minima and eliminates the need for costly relinearizations of the map. Unlike other stochastic methods, but similar to exact solvers, such as iSAM, our technique is able to process position-only constraints, such as GPS measurements, without introducing systematic distortions in the map. We present results from the Google Street View database, and compare our method with results from TORO. We show that our solver is able to achieve higher accuracy while operating within real-time bounds. In addition, as far as we are aware, this is the first stochastic SLAM solver capable of processing GPS constraints in real-time.