[OSM-dev] Optimizing map tile trees

Phil! Gold phil_g at pobox.com
Sat Aug 20 15:46:52 BST 2011

* Frederik Ramm <frederik at remote.org> [2011-08-20 02:07 +0200]:
> (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?

This would be a quad tree[0].  I know that osm2pgsql uses a quad tree to
track expired tiles in a reasonably memory-efficient way.

  [0]: http://en.wikipedia.org/wiki/Quad_tree

Whether it's useful to you depends greatly on how your tiles are
retrieved.  Typically, they're stored in a filesystem and addressed
directly by zoom, x, and y coordinates, not down a tree.  A quad tree
would only be a space optimization if you were retrieving tiles through
the tree.

A common space optimization for the one-tile-per-file filesystem layout is
to link together identical tiles (either via hard- or soft links),
although some filesystems have limits on the maximum number of links to a
given file.  You could certainly use a quad-tree-like process of checking
all the tiles at a given level against their children at the next level
and linking them together if they're identical.

> (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?

I don't know whether anyone else has implemented space optimizations such
as these.  Since these would tend to incur more overhead during tile
rendering or retrieval or both, I suspect that most of the bigger tile
servers choose not to pursue space optimizations such as these in order to
better optimize rendering and retrieval time.  (Although I believe
mod_tile stores metatiles in the filesystem and extracts the individual
tiles on the fly.  This undoubtedly saves disk space as compared to
storing the tiles individually, both for reasons of file cluster size and
better compression.)

The one rendering setup that I know of that does space optimization is
TopOSM, which uses JPEG for its color relief layer and runs optipng over
the other layers' tiles after generating them.  This is mostly aimed at
reducing bandwitch rather than storage space, though.

Certainly some of your ideas could result in a lot of space savings
(particularly over oceans), but you would have to implement a very
different tile retrieval method than any of the existing ones that I know

...computer contrarian of the first order... / http://aperiodic.net/phil/
PGP: 026A27F2  print: D200 5BDB FC4B B24A 9248  9F7A 4322 2D22 026A 27F2
--- --
  "Ah!  He has become one with his inner self!"
  "He's passed out."
  "That too."
                       -- Vir and Garibaldi discuss Londo.  (Babylon 5,
                          "The Parliament of Dreams")
---- --- --

More information about the dev mailing list