[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.

[Nick Hill]

Hello Nigel.
I think I understand that you are saying the character based system 
enables a description of a larger tile by using fewer characters.

The same effect can be achieved in the binary system using a bitmask. 
We'd need to find 4 bits for every 32 bits to describe the size of tile. 
4 bits describes 0-15, and there are 16 duples in a 32 bit word. In 
computational terms, binary comparisons using bitwise-and are easier 
than substring matches.

For a 64 bit word, the mask would need to be 5 bits,

If we could tolerate a grid as coarse as 8cm over a 64 bit lat/lon 
location, there would be enough space for a bitmask.


++However, I am not clear that there are practical benefits to have 
variable size tiles for invalidation quadtree-style.

There is a trade-off between size of tile and size of invalidation 
table. Smaller invalidation tiles present more records to process and a 
larger invalidation table. Larger tiles present a smaller invalidation 
table, but a change can invalidate a larger area, requiring unnecessary 
re-rendering. Tables of variable size invalidation tiles could become 
arbitrarily large.

A planet of 6553uD (MicroDegree) tiles sits very neatly in a 32 bit 
word. It also is 655m N-S and 0-655m E-W, so in terms of rendered area, 
is usually less than 12 streets. There isn't a strong incentive to 
complicate by having variable size invalidation tiles.

Also, if we store items in tiles of that 32 bit size, the number of 
tiles seems just about right. An update to Catford would invalidate a 
tile covering 1/36th of this area:

http://wiki.openstreetmap.org/images/6/65/Se6-cropped.png

So I propose that if we should use a quad-tree principle, it would be on 
the basis of coding complexity comparison, computing requirement, data 
locality in database (areas on the hard drive roughly corresponding to 
localities in real world) and whether the easier selection of larger 
areas is justifiable.


Nigel Magnay wrote:
> [inline]
> 
> On 16/09/06, *Nick Hill* <nick at nickhill.co.uk 
> <mailto:nick at nickhill.co.uk>> wrote:

> 
> This is required though, otherwise fetching supertiles (e.g. 'D' from my 
> example) can't be done with a range lookup.
> 
> e.g: As quadtiles
> AA AB BA BB
> AC AD BC BD
> CA CB DA DB
> CC CD DC DD
> 
> == as bits
> 
> 0000 0001 0100 0101
> 0010 0011 0110 0111
> 1000 1001 1100 1101
> 1010 1011 1110 1111
> 
> == as numbers
> 
> 0 1 4 5
> 2 3 6 5
> 8 9 12 13
> 10 11 14 15
> 
> Fetch the bottom-right quadrant of the map is either ' like D%' or 
> 'where val >= 12 and <= 15).
> 
> This is very important if you ever want tiles that are > than the 
> minimum size. If you're doing,say, tiles that are composed of some size 
> greater than the maximum resolution. For example, you have a tile address
> 
> AAAB
> 
> and a 'tile invalidated' message arrives, for tile AAABABFB, you know, 
> trivially, that your tile is now invalid. The same can be done with 
> pairs of numbers, (e.g tile 9 invalidated, my tile is >=0,<=15) but it's 
> a bit uglier.
> 
> 
> 
> 
> 
>