osm-search / Nominatim-Data-Analyser

QA Tool for Nominatim. Helps to improve the OpenStreetMap data quality and therefore the Nominatim search results.
GNU General Public License v2.0
10 stars 3 forks source link

Optimized vector tiles generation by switching to recursion #14

Closed AntoJvlt closed 3 years ago

AntoJvlt commented 3 years ago

Fixes #9

The generation of vector tiles by clustering-vt has been greatly optimized. Instead of iterating over 2^zoom * 2^zoom for each zoom level (which was increasing exponentially) the algorithm now generates the tiles recursively with a divide-and-conquer algorithm.

For each tile, if Supercluster generated features for it and if there is at least one cluster, we generate the four sub-tiles of this tile by calling the same function recursively:

sub-tiles

By generating the tiles recursively like that, we can easily stop the zoom descent for a specific tile if it contains no features or no clusters (if there is no clusters we just need to generate the features as they are, only once). This greatly reduce the amount of operations, for example:

If we have a max zoom + 1 of 12, stopping one tile at zoom level 2 will prevent the processing of 4^10 = 1048576 tiles.

This allows us to now have a max zoom of 13 for clustering-vt, we could easily set an higher number but we don't want to generate clusters to far. The global tiles generation duration has been greatly reduced.

AntoJvlt commented 3 years ago

Currently one problem still remains, everything works perfectly for the average rules but this new tiles generation doesn't work well for the addr_street_wrong_name rule (which is the biggest rule with 4 millions + results), for this rules the processing time is increased a lot (more than 1 hour). This problem still needs to be solved.