3

I have table in PostGIS where I store coordinates in the 4326 lng/lat SRID, to make it easy to store GPS coordinates collected from mobile devices. I'm using the coordinates to query the table based on distance from a point (with the ST_DWithin function), so I can filter only the results in reach of a distance parameters.

After some thinking I came to the conclusion that I need to cluster the results, so that when I have N points close to each other I will get the centroid of the cluster and the first entry (based on some sorting I will implement later) and then iterate over the others asynchronously (effectively paginating them).

I'm not so practical with coordinate systems, but after some research I found an algorithm available in PostGIS that I can use to cluser the results: ST_ClusterDBSCAN. This function uses the DBSCAN algorithm to cluster the results based on maximum distance and minimum number of points. The problem here is that since I'm using the 4326 coordinate system I have to input the max distance parameter in degrees unit, but I have no use of such a query, since I need to input the distance in metric units (meters).

So I thought of two alternatives:

  • Transforming the meters in degrees based on the point I'm making the query from (the ST_DWithin center point), but that means I can't cache the results in advance, because the clusters will depend on the center location I'm making the query from, or at least it will be technically difficult to do so. So the query has to be run every time, and it's an expensive query.
  • Using another coordinate system in addition to the lat/lng one. I've seen that the UTM system is in meters but it divides the earth in 60 slices of 6° of longitude each, also excluding the poles. Since my use case potentially has no geographic boundaries, this means I would need to store 60 additional columns and choose the right one every time I store the coordinate. This also means that for points at the edges of a slice there would be no clustering with points of the next slice)

Is there any other coordinate system that fits this use case? Or do you have any other suggestion on how can I solve this problem?

Edit:

I will add some context to my requirements, as requested in the comments.

I have an Android/iOS client application that features a map displaying markers fetched from a backend server.

My requirements are that the client shall continuously fetch the clusters from the backend server, every time the map is panned, and for every zoom level range there's a different clustering applied (let's say 10-12 will have the points clustered with distance 10 km, 12-14 will have them clustered by 1 km and so on. I have not tested these numbers so they are just an example).

After a cluster is opened (with a tap on the marker), one item of the cluster is fetched singularly and shown to the user, and the next one will be fetched with pagination (let's say cluster 10 entry 1, then 2, 3, and so on) based on a previously estabilished sorting clause.

To accomplish these requirements I could do the clustering client-side, but I was exploring server-side clustering to have more control on the pagination. For server-side clustering I could effectively apply it using degrees on lng-lat coordinates using the DBSCAN algorithm but I would have inconsistent clustering at different latitudes, so using meters or another spatial unit is the only way.

Since there will be a lot of requests (each time the map is panned, with throttling in place) I have to cache the results in an intermediate table (I was planning to use a materialized view), and entries will be inserted fairly often, so the view would be refreshed fairly often.

This part of the problem is almost settled up, but I still can't find a solution for the db-side clustering. I don't need extreme precision, so I need a coordinate system based on meters that I can use to do the clustering with the aforementioned algorithm, and the only one I found (UTM) spans for only 6° longitude but I need one that spans across the entire globe.

6
  • The key information needed to answer this Question is not yet present: How many features in the table? What is the extent of the features? What is the maximum search distance? How many features are returned? How long does it take? What is your performance requirement? Please Edit the Question.
    – Vince
    Mar 19, 2023 at 13:29
  • I have added more info to the problem as you requested, I hope I've been clear since the requirements are still being developed
    – Paolo
    Mar 19, 2023 at 18:31
  • You missed the feature count, and the extent ("entire globe" seems unlikely, since mapping to the poles isn't common), and features returned, and the search distance, and the timing, and the timing requirement. It makes no sense whatsoever to cache results in a materialized view by web client. And you don't need a projected coordinate system to compute distances in meters using PostGIS.
    – Vince
    Mar 19, 2023 at 18:52
  • the entire globe is a requirement, it's a social media app. sure it can be partitioned but I'd like if possible a solution independent of the geographic location. As for the feature count it could be very variable, 5 to potentially 500 per km squared. The search distance is what can be viewed on the map at a minimum zoom level, so up to 10 km probably. The cache should be in place exactly for the timing, that should be as low as possible. For what I can think of a materialized view should be optimal for caching the clustering computations., why it makes no sense?
    – Paolo
    Mar 19, 2023 at 22:48
  • Web apps are asynchronous. Giving permission to create new data tables to a client app is a security nightmare, a denial-of-service waiting to happen. Caching happens app side, not in the server. And especially not by creating a new table on the server. Don't optimize before you encounter a performance problem.
    – Vince
    Mar 19, 2023 at 23:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.