Grouping search results on a map

Question

I am building a mobile app which lets users search for POIs around them on a map. I am curious to know what would be the best way to "group/paginate" these results in order to avoid downloading hundreds of search results at once from the server?

I looked at Google Maps as an example and the way they seem to do it is they only return a fixed number of results, spread across the map and once you start zooming in somewhere, you start to see more results in that area. In other words, they show one search result per a certain size of area. This seems like a good approach, but I don't know how would I implement such behaviour on the server-side.

Any input is highly appreciated!

Answer 1

An approach to this is to use Geohashes as a way of encoding locations.

This encoding technique subdivides a space into squares and assigns each of those squares an alphanumeric code.

Subdivide each square again and do the same and keep recursing down to the point that you can resolve the longitude / latitude of the location in question to the desired level of accuracy.

You then end up with a Geohash for the location similar to gbsuv7zt and that is effectively an encoding of the location in ascending accuracy from left to right.

The centre of the map and the zoom level can then be encoded as a geohash too and you can compare hashes by the amount of matching leading characters. Location gbsut7zt matches the first 4 characters and means it is relatively close.

There are some edge cases where locations sit just outside the enclosing box of a geohash, and that requires looking in the neighbouring squares to find nearby results.

Code approach (image from https://www.joinc.co.kr)

Answer 2

To implement something like this, you'd use a tree where each node represents a grid area representing a piece of the parent grid area. Each of these nodes would have also a list of markers with coordinates that you would show once a certain zoom is achieved. This lets you, say, have a parent node with only important markers for the whole area, and the child nodes have markers for the less important areas pertaining to that particular area.

As you zoom in, you simply show the markers of all the nodes in the zoomed in area. You probably don't want to subsection your grid more than 3 by 3, and you simply add more layers so that the effect is more gradient and you don't have to zoom in to a tiny little area before you begin seeing the markers in that area.

Though since some zoomed-in regions could be in completely different sections in your tree, the regions should also be organized by ids in a hash map. This will also enable you to request markers of a given region and performance shouldn't suffer as a consequence. And since each region knows about its subregions via your tree, you shouldn't have any issues retrieving the zoomed in markers for each region.