FAST AND ACCURATE GEOMAPPING

摘要

A system and method are provided for discovering k-nearest-neighbors to a given point within a certain distance d. The method includes constructing an index of geometries using geohashes of geometries as an indexing key to obtain an indexed set of geometries, and calculating a geohash representation of the given point with a resolution equal to a magnitude value of d. The method includes searching for a closest-prefix geometry from the indexed set using the geohash representation of the given point, and identifying geometries from the indexed set having a same prefix as the closest-prefix geometry. The method further includes calculating distances between the given point and the geometries identified from the indexed set having the same prefix as the closest-prefix geometry, and determining k geometries with respective shortest distances less than d from the geometries identified from the indexed set having the same prefix as the closest-prefix geometry.

主权项

1. A method for discovering k-nearest-neighbors to a given point within a certain distance d, the method comprising the steps of:
constructing an index of geometries using geohashes of geometries as an indexing key to obtain an indexed set of geometries; calculating a geohash representation of the given point with a resolution equal to a magnitude value of the certain distance d; searching for a closest-prefix geometry from the indexed set of geometries using the geohash representation of the given point; identifying geometries from the indexed set of geometries that have a same prefix as the closest-prefix geometry; calculating distances between the given point and the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry; and determining k geometries with respective shortest distances less than d from the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry.