Would it be possible to use geohash for proximity searches?

Question

I'm looking to optimize point proximity geo searches time.

My input is lat,lng point and I'm searching on a precomputed set of locations to n nearest points.

I don't care how much time/space the building of the precomputed index of locations will take but I do care the queries will be super fast.

I'm thinking about using geohash as the search key, where I would fist check if I get results for X chars of the key and then continue to trim down chars from the end of the key until I start to see results.

To my (very sparse for now) understanding of geo index techniques this approach should be able to produce the fastest results (in terms of query time) compared to all other known implementations (such as R Tree and co.)

// this post should probablly be tagged: geohash, hilbert-curve, research

Answer 1

The question could be read in several ways. I interpret it to mean you have a large number of points and you intend to probe them repeatedly with arbitrary points, given as coordinate pairs, and wish to obtain the n nearest points to the probe, with n fixed beforehand. (In principle, if n will vary, you could set up a data structure for every possible n and select it in O(1) time with each probe: this could take a very long setup time and require a lot of RAM, but we are told to ignore such concerns.)

Build the order-n Voronoi diagram of all the points. This partitions the plane into connected regions, each of which has the same n neighbors. This reduces the situation to the point-in-polygon problem, which has many efficient solutions.

Using a vector data structure for the Voronoi diagram, point-in-polygon searches will take O(log(n)) time. For practical purposes you can make this O(1) with an extremely small implicit coefficient simply by creating a raster version of the diagram. The values of the cells in the raster are either (i) a pointer to a list of the n nearest points or (ii) an indication that this cell straddles two or more regions in the diagram. The test for an arbitrary point at (x,y) becomes:

Fetch the cell value for (x,y).
If the value is a list of points, return it.
Else apply a vector point-in-polygon algorithm to (x,y).

To achieve O(1) performance, the raster mesh has to be sufficiently fine that relatively few probe points will fall in cells that straddle multiple Voronoi regions. This can always be accomplished, with a potentially great expense in storage for the grids.

Answer 2

I use geohashes for exactly this. The reason I am is because I needed to implement proximity searches using a pyramid style information system.. where geohashes with an 8th level precision were the 'base' and formed new totals for geohashes of the 7th precision.. and so on and so forth. These totals were area, types of ground cover, etc.. It was a very fancy way to do some very fancy stuff.

So 8th level geohashes would contain information like:

type: grass acres: 1.23

and 7th, 6th.. etc.. would contain information like:

grass_types: 123 acres: 6502

This was always built up from the lowest precision. This allowed me to do all sorts of fun statistics very quickly. I was also able to assign a geometry reference to each geohash reference using GeoJSON.

I was able to write several functions to find the largest geohashes that make up my current viewport and then use those to find geohashes of the the second largest precision within the viewport. This could easily be extended to indexed range queries where I would query for a minimum of '86ssaaaa' and a maximum of '86sszzzz' for whatever precision I wanted.

I'm doing this using MongoDB.