Server side clustering with geohash

Question

I need help with clustering algorithm. I have a mysql database with lat, lng, geohash(12 chars).

I am usign this query to select all records for zoom level 2 (2 chars)

SELECT COUNT( id ) , LEFT(  `geohash` , 2 ) 
FROM server_cluster
GROUP BY LEFT(  `geohash` , 2 )

But how to select all records for bounding box?

mymap.getBounds()._northEast
M {lat: 42.51665075361143, lng: -87.95448303222658} (dp93yect2n0n)
mymap.getBounds()._southWest
M {lat: 42.313877566161864, lng: -88.36647033691406} (dp90tpj80n86)

UPD: here is how I use it now:

$bounds = explode(",", $bounds);
$NE = substr(GeoHash3::encode($bounds[0],$bounds[1]),0,$zoom);
$SW = substr(GeoHash3::encode($bounds[2],$bounds[3]),0,$zoom);
$sql = ' SELECT count(id) as count, LEFT(`geohash`, '.$zoom.') AS geo
            FROM server_cluster
            WHERE 
                LEFT(  `geohash` , '.$zoom.' ) <=  "'.$NE.'"
            AND 
                LEFT(  `geohash` , '.$zoom.' ) >=  "'.$SW.'"
            group by geo 
            ORDER BY  `geohash`
            ';

But it is not ok.

Or is there any simple server side clustering algorithm with php and mysql that can handle 60k markers on the 0 zoom level?

Answer 1

While the geohash representation is convenient, it is not designed with spatial queries in mind. From my understanding of the Geohash algorithm you can't just select all the points inside a given bounding box by simple string comparison.

This image might help understanding it a bit better:

(image from http://www.movable-type.co.uk/scripts/geohash.jpg)

If you have a bounding box going covering a region in Canada for instance within the c and f regions, string comparison would necessarily select regions in d and e regions as well, which are geographically at a very different place. So if you are able to design a correct query, it would probably be close to a Geohash decoding algorithm which is computationally quite expensive for big data sets.

For your question regarding a simple clustering algorithm, the problem is similar. Clustering algorithms all work based on some distance metrics. And a Geohash does not provide a generic way for conveniently computing the geographical distance between two far-away hashes.

However there are probably two paths you can take.

One option is to store your data (maybe additionally to the Geohash format, depending on your requirements), in simple indexed lat and lng columns, or as geometries (with a spatial index). In the case of using geometries, you can use the Spatial Relation Functions in MySQL (e.g. MBRContains).

The other option is if you only want to cluster the markers in Leaflet, similarly to the Leaflet MarkerClusterer, you could just group by the first character in the Geohash for zoom level 0. For more fine grained clustering, you might need more computation and be better off with the previous option.

Answer 2

The article "Contraction Clustering (RASTER): A Very Fast Big Data Algorithm for Sequential and Parallel Density-Based Clustering in Linear Time, Constant Memory, and a Single Pass" by Gregor Ulm et al (link here) describes a clustering method which maps each point (in this case a (lon, lat) geographic point) to some grid (in this case, a Geohash grid of some specified resolution) and then counts certain Geohashes as "significant" if it contains more points than some predetermined threshold. Then, once the solution space has been pruned to a few significant Geohashes, you implement a DBSCAN variant which groups neighbouring Geohashes together. This open-source package provides a Javascript implementation for finding Geohashes neighbours.