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

[Etienne]

On 9/16/06, Nick Hill <nick at nickhill.co.uk> wrote:
>
> Nick Hill wrote:
>
> > 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.
> >
>
> Developing this still further, we will want to have a scalable map which
> operates over a wide range of zooms. At close zoom levels, fie features
> are selected and shown. At lower zoom levels, large lakes and parks, A,
> B, Motorways and rail lines shown. At lower level, A, Motorway and
> intercity rail network shown. Lower level, Motorways and intercity
> lines. Lowest zooms, very large features such as huge inland lakes. All
> zooms, country outlines.
>
> By using a quad-tree style tile to represent the 16
> most-significant-bits of objects lat and lon (32 bits), the selection of
> areas on a regional and country scale would be made simpler and less DB
> intensive.
>
> To achieve this sort of scalability, we would need a table with
> basically 3 fields. Quadtree-style tile 32 bit (with interleaved
> lat/lon), Object zoom value (the maximum zoom level an object will
> remain visible at) and reference to object.
>
> There is a problem where large scale views of an area will constantly be
> invalidated by small changes in the area, despite those changes not
> affecting objects visible at the current zoom level.
>
> For example, you may view the whole London area A-road network. From one
> view to the next, the whole lot will be invalidated from tiny changes to
> minor roads, which are not visible at your zoom level.
>
> This is where the variable bitmask and zoom level become one of the same
> thing.
>
> If a feature with a zoom value of 0 is modified, only the smallest
> invalidation tile has it's timestamp updated and the tile location
> written to the invalidation table.
>
> If a feature with zoom value 1 is modified or created, exactly the same
> happens for 0. After that update, the last 2 bits of the quad-tree tile
> are set to 0 and an entry is put into/timestamp updated for zoom level 1.
>
> If a feature with zoom value 2 is modified or created, exactly the same
> happens for 0 and for 1. After those updates, the last 4 bits of the
> quad-tree tile are set to 0 and an entry is put into/timestamp updated
> for zoom level 2.
>
> and so on.
>
> This way, a tile is only invalidated if an object which will show at
> that zoom level is changed.
>
> The table has a primary key based on invalidation tile and zoom level.
> Inserts to the table are set to update on duplicate so only the freshest
> time stamp for an area is kept.
>
> I wonder if tomorrow I will understand what I have just written?



Currently most detail is recorded to about 10m accuracy which is good enough
for roads.  It is possible (a long time in the future) that  we will be
recording detail at 1m, 10cm or even 1cm accuracy.  This will be good enough
to record the outline of residential houses, street furniture and the like.


If you use zoom level 0 as the lowest level of detail then you would need to
introduce zoom levels -1, -2 etc to cater for increased detail.  If you call
the very highest level 0 and work down then you wouldn't have this problem.

Likewise the alpha-quadtree proposal, because it is variable length, seems
to me to be infinitely extensible in the detail direction.  I'm not sure
that the 32-bit approach would be so easily extensible.

Etienne



_______________________________________________
> 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/20060916/179e3f3e/attachment.html>