3

We're building a mapping application for voter data using PostGIS and Leaflet. It has a web interface. Our voter file will have several million entries. In our app you can select a subset of the voter file and display it.

It works fine when you're zoomed in because the result set is small. The challenge is to figure out what to do when the result set is large. As I see it, we have multiple options:

  1. Just bail out when result sets exceed X records. The user would receive an error message: "Too many records to display. Zoom in or narrow your search criteria." This isn't ideal.

  2. Try to do client-side clustering and just display the clusters. This won't work because it's not possible to transfer very large result sets to the browser quickly. No amount of compression will get a million records down to an acceptable size.

  3. Try to do server-side clustering. We've done that using the techniques found here: Spatial clustering with PostGIS? The difficulty is, again, speed; you can't aggregate millions of locations and calculate cluster centroids and counts quickly. Maybe we're doing it wrong.

  4. Do some kind of aggregation using zip codes. This is faster; essentially you do a select zipcode, count(*) from voters where (some predicate) group by zipcode. You then look up the zipcode centroid separately. It's faster because it's a covered query which can usually be answered by hitting indexes alone. But zipcodes don't display well because they're dense in a city and not so dense elsewhere.

  5. Aggregate based on some other field, maybe something related to tiles. I haven't fully thought this one through.

  6. Exploit some property of the GiST index on the location. This is theoretically possible; a GiST index already "clusters" points internally in the R Tree. I don't know where to start with this idea.

How do other people solve the problem of summarizing millions of points, dynamically, quickly, for presentation to an end user?

  • Would it be possible to show a static image at a certain scale, and then switch to display of points as the user moves into the area they are interested in? – Keagan Allan Oct 21 at 23:07
  • Yes, if I could render that static image dynamically on the server side very fast. It's not possible to precalculate it because I don't know what the predicate will be. – ccleve Oct 21 at 23:33
  • 2
    Do you have to calculate that very fast? What if, every hour, you ran a process over the main table and outputted the "generalised" results to another table that could be read independently? I assume this is possible in PostGIS, we use it a lot with SQL Server. – user25730 Oct 22 at 0:02
  • I'd love to be able to precalculate tiles, but I can't. Imagine this query: where sex=male and age > 25 and age < 40 and likelihood_to_vote > 0.5. It's not possible to precalculate every possible criteria in every possible combination. – ccleve Oct 22 at 1:03
  • You're attempting to violate a basic law of engineering here, but with large, dynamic, and fast instead of good, cheap, and fast. I've usually used scale dependency to negate the dynamic option, pre-processing my points into multipoints, so that tens of thousands of points are in each feature (potentially partioned for symbology), and turning off the individual feature rendering until there are only a few thousand in the viewfield. – Vince Oct 22 at 1:04
4

It is common to aggregate by rounded up coordinates. I.e. call ST_SnapToGrid with some precision, that will return identical points for close-enough points, then group by the resulting point. Another way to do the same, but with less control, is to compute geohash - length of geohash determines the snap distance in this case.

1

If your table doesn't change, you can try to create clusters with for example ST_ClusterDBScan (see for example this question), to mimic the behaviour of leaflet marker cluster by displaying only one point for each cluster on dezoom. You would have to store one table for each wanted zoom level, and use different parameters to create each table. This is relatively efficient ways to do it, but if your data is constently modified it can become difficult.

Else, as Michael said, what I would do is to rasterize, for exemple using rounded coordinates (but be sure to have projected coordinates or x and y can have big differences and your grid will not look squared) or also geohash: you just add a few column (for exemple for each wanted level of geohash, like 6, 5, 4 and 3 should be enough). This way you can add an index on these columns to efficiently count the number of points inside each geohash, and display a rasterized map depending on the level by grouping on the geohash that correspond to your zoom level.

You can also use the raster extension of Postgis to store your data, but if you want to filter on multiple column it may not be the best way.

Lastly, I would say that the "best" way to display rasterized data should be the hexagonal grid (for mathematical reasons), and I know that it's possible in Postgis (exemple here) but I don't know if you can do it in an efficent way.

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.