I have a POSTGIS database with geography points and I want to cluster the points using quad-tree. I have a map where I have to display the markers clustered or non clustered depending on the zoom level so I can't really use k-means algorithm because I can't fix k.

How can I implement quad-tree in my application?

Please tell me if I am wrong somewhere.

What I have tried
I have tried clustering in the front-end but it doesn't help to solve my problem. With a large number of markers that doesn't work. I want to send the clusters instead of all the markers.

  • This has been asked quad tree in Postgres and not answered. It involves knowing a fair bit of C. Another option would be to use something like Python, for which there are lots of examples and implementing it as is a plpythonu function. Apr 11, 2016 at 11:56

1 Answer 1


This will not be ideal, but it will produce results, and you could refine it to produce something closer to an idea result with some custom code:

  • add a column to your table ALTER TABLE foo ADD COLUMN geohash varchar
  • populate it with the geohash UPDATE foo SET geohash = ST_Geohash(geom)
  • query for different overview levels using substrings of the geohash SELECT Count(*), st_makepoint(avg(st_x(geom)), avg(st_y(geom))) as geom FROM foo GROUP BY substring(geohash,1,5)

The density of the overview levels will vary depending on what value you use for the substring (5 in this example), with larger numbers being more dense.

Geohash embeds as much information as it can in each character, so it's not an ideal key for overviews in powers-of-two based mapping apps. If you can make the example above work, you might consider writing your own hash key using something like the Bing Maps tile system (especially if you're mapping in web mercator)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.