[OSM-dev] Optimizing map tile trees

Frederik Ramm frederik at remote.org
Sat Aug 20 01:07:15 BST 2011

I am relaying this question by Michael Katz from help.openstreetmap.org:

----------------------- quote ------------------

I am building my own map tiles using the OSM data, with PostGIS and 
Mapnik (as explained, for instance, here).

I am going to be serving these tiles from my own server, so I have a lot 
of flexibility in how I process a request for a tile.

I have a few closely related questions:

(1) When I'm running the script to generate the tiles 
(generate_tiles_multiprocess.py, in my case), for a huge percentage of 
the output tiles it writes "Empty Tile" to the script output line. My 
understanding is that "Empty Tile" actually means "a tile of just one 
color". So it might be all blue in a water area, or all green in a park 
area, or all gray in some other area. My question is whether there is a 
deeper meaning to "Empty Tile", specifically whether it means that all 
sub-tiles generated at higher levels will also be empty? For instance, 
if I generate a level 16 tile that is a gray "Empty Tile", does it mean 
when I generate level 17, and I am generating the four level 17 tiles 
that correspond to that one level 16 tile, that those four tiles will 
also be gray "Empty Tile", and the same for the 16 sub-tiles at level 
18? Or, in contrast, is it possible for features that weren't visible in 
the level 16 tile to "appear" in that area at level 17 or level 18? 
Another way of saying it: Does "Empty Tile" mean that the tile is "empty 
all the way down"?

(2) Regardless of the answer to question to (1) above, suppose I have 
generated a full tree of tiles for a given area, all the way to level 
18. Suppose there is a tile on level 15 that is all gray, and it turns 
that the four corresponding tiles on level 16, the 16 corresponding 
tiles on level 17, and the 64 corresponding tiles on level 18, are also 
all gray. A natural optimization of the tree is just to delete those 
level 16, 17, and 18 tiles (84 total tiles) from the tree altogether. 
Then, when the server goes to serve a tile and it's not present in the 
tree, it knows to "look up" to the parent levels of the tree as far as 
necessary until it finds a tile, and it knows that that tile (the all 
gray tile in this case) is good to use for the originally requested 
tile. My questions are: what is that optimization called? Is it commonly 
used? Is it discussed somewhere?

(3) Finally, I notice that many of the output tiles are very simple. 
First of all there is the huge number of one-color tiles. But there are 
also many two-color tiles with a very simple shape, such as a single 
line dividing a blue area from a gray area. I see that the one-color 
tiles are 103 byte .png files. The simple two-color tiles are typically 
anywhere from 1.0k to 1.5k. So it seems like a natural compression 
technique for these would be to use just three bytes ( R, G, B ) for the 
one-color files, and a simple run-length encoding scheme for the 
two-color files. Of course, to make this really save space on the disk 
it would be necessary to combine lots of these small files into some 
kind of multi-file that would be cached in memory on the server. But 
anyway for both storage and transmittal (as well as helping reduce cache 
missing when actually serving the data) it seems like there are many 
optimizations like this that could be employed. Can you tell me if these 
optimizations make sense, and where I can find documentation of how 
others have implemented stuff like this?

Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00'09" E008°23'33"

More information about the dev mailing list