* Frederik Ramm <[email protected]> [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 of. -- ...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") ---- --- -- _______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
