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

[Nigel Magnay]

It's a bit more than that, and it's not about saving space - I'm quite happy
to pack the address into a 32-bit int or a 64-bit int or whatever. What I'm
saying is that not interleaving the quadtile addresses is a really really
bad idea. If you interleave, you need no invalidation table at all. We must
have a quadtile address that (in a bit packed world), uses 2 bits to store
1st level of detail location, next 2 bits for next level of detail, and so
on and so forth.

Say we choose 16 bits of granularity to store a tile address, and let's say
each tile covers an area of 1 square metre (you actually need more bits than
this I think, about 28 for a reasonable LOD) For each tile, I'm going to use
A B C or D (TL, TR, BL, BR). You could also use 00 01 10 11, and pack the
values together. The principle is the same.

So; someone does some editing, and invalidates tile ABCDAABC. This is fine.
But, say, my slippy map tiles don't store 1m squared tiles, because that
would mean it's wasting a *lot* of space, and invalidating too much. It
might know, for examplke, that tile ABCC is entirely ocean.

So, my map tiles are, say, 16 by 16. How do I know which tiles I need to
invalidate? With a quadtree, it's trivial! I invalidate tile ABCD (or any
tile starting in ABCD if I have variable sized tiles).I don't need an
invalidation table, I don't need to do any fancy masking, I can just examine
my cache hashmap (or hashtree, more likely), and remove any entries.

Also, conveniently, it gives you an automatic metric to work out to what
level of detail you need to cache, because you can see how many entries
there are in each bucket - if it breaches a certain size, next time you
invalidate it, you create 4 entries rather than 1. You don't need to work
out what the 'right level of tile size' is, because it can be dynamic
depending upon application and the actual data.

On 16/09/06, Nick Hill <nick at nickhill.co.uk> wrote:
>
> 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.
> >
> >
> >
> >
> >
> >
>
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20060917/dbe1f5c4/attachment.html>