A mechanism is provided for spatial annotated graph queries. A geomap query is received to identify a number K-closest geometry objects within a distance D to a geo-location L. A geohash is computed for the geo-location L. A set of geometry objects are identified from an indexed set of geometry objects having at least NB common-prefix bits to a number of bits NB of the geo-location L. K-closest geometry objects are identified from the set of geometry objects that are closest to the geo-location L. The K-closest geometry objects are then returned to a user who submitted the geomap query.