[inline]<br><br><div><span class="gmail_quote">On 16/09/06, <b class="gmail_sendername">Nick Hill</b> <<a href="mailto:nick@nickhill.co.uk">nick@nickhill.co.uk</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Hello Nigel<br><br>I remember reading your quadtree post.<br><br>You could, for example, use the two most significant bits to represent<br>each quadrant, then the two next most significant bits to select  the<br>next level quadrant and so on. With a 32 bit int, you can do this 16

<br>times, dividing the planet into 4Bn portions, much like the tiles I<br>suggested.</blockquote><div><br>Yes; whether you use a pair of bits or a letter doesn't make any difference to the algorithm. </div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

I think using an int and bits scheme would be wildly more efficient than using characters.</blockquote><div> It is in space, but not neccesarily in time. When I tested on a couple of databases a while back, char(16) indices significantly outperformed integer range checking. (Where a text index you do something like 'select * from nodes where qt like 'D%' vs 'select * from nodes where qt >= 12 and qt <= 15).

The important thing is having a tile address. However it's done underneath, I think it's easier for users to be able to look at tile addresses not range (so we ought to be able to do something like /api/map?tile=dcb rather than /api/map?tile=a,b). I believe google use something similar for some of their tile data.

<br><br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Extending the idea I proposed, If each object was associated with a<br>tile, each object would only need an additional single 32 bit int to

<br>locate to within 1cm. The algorithm to derive lat/lon would be extremely<br>computationally simple and fast- a few steps of a shift register. In<br>fact, faster than the transport of data that they will derive.</blockquote>

<div><br>No - objects potentially need many additional points. A segment going from tile(a) to tile(b) may traverse tile(c), so this information needs to be stored. (In this instance, a and b are stored by nature of the node, it's only the additional tiles traversal (or enclosure for areas) information you need to store). 

</div> <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">I haven't yet considered your quadtree proposal in enough depth to fully compare the two approaches, but there are many similarities.

My proposal could potentially be mimicked by MySQL by selecting partial indexing. For example, indexing only the first 16 bits of each lat and lon.</blockquote><div> I don't know MySQL that well (and its somewhat inconsistent performance characteristics); if it's similar to index file partitioning in Oracle, there may be some gains to be had.

Of course, once (if) we get tile addresses in, there's nothing to stop the map server caching API queries and not going back to the database at all, since it will be able to determine whether anything stored in it's local store has changed. A straight hashmap of tile address->query result xml would do this...

<br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Nigel Magnay wrote:<br>> yes - use tiles, but I'd rather use quadtiles, as they have nicer

<br>> properties (particularly you can fetch the super-tile of 4 child tiles<br>> incredibly easily. Calculating which tile a point is in is not very<br>> hard; I've got a bit of java lying around, but it's easy enough to

<br>> understand.<br>><br>> Incidentally, though I didn't mention it at the time, this scheme is<br>> particularly good for databases that support data file partitioning.<br>><br>> Here's the post I sent a while ago:

<br>><br>>  > [sniiip]<br>>  > I'd be interested to hear from computer scientists about fancy<br>> algorithms for<br>>  > spacially-sorting the data, doing indexes, etc. First person to mention<br>

>  > Hilbert space gets a nerd of the month award.<br>>  ><br>><br>> Quadtrees. We need to be doing this in OSM in general, and it would<br>> make things much simpler.<br>><br>> To illustrate - divide the world into 4 quadrants. Call the top-left

<br>> A, top-right B, bottom-left C, bottom-right D. Then for each quadrant,<br>> do the same. thus the grid is now<br>><br>> AA AB BA BB<br>> AC AD BC BD<br>> CA CB DA DB<br>> CC CD DC DD<br>><br>

> each time you repeat this process (and you can do this as much as you<br>> like), you halve the area in each addressable tile. For around 13<br>> characters, you get (IIRC) 100m of resolution if you started with the

> entire globe (may be wrong, memory is hazy). > > So, just thinking about nodes, we store along with each (long, lat) > coordinate the quadtree address. Instead of querying, say, > > select * from nodes where lat>? and lat<? and lon>? and lon<?

<br>><br>> we just do (say)<br>> select * from nodes where quadtree='AAABDBA'<br>><br>> rather neatly, if you wanted to zoom out to the next level of detail,<br>> you can do<br>><br>> select  * from nodes where quadtree like 'AAABDB%'

<br>><br>> Which will get any node in AAABDBA, AAABDBB, AAABDBC and AAABDBD. This<br>> is a single index lookup, and is very fast.<br>><br>> This also solves another sticky problem. Consider segments (ways are

<br>> just the same on a larger scale). You have a segment going from AB to<br>> BC. Using the current 'get nodes in area, get missing nodes in<br>> segments' method, if you fetch the area AD, you'll miss the fact that

> there is this segment going through it. By storing for each > way/segment the list of tiles it intersects, the segments query is > also simplified to 'select * from segments where quadtree like 'xyz%'.

<br>><br>> This is particularly important for areas - for example, you could be<br>> viewing a tile in the middle of a forest whose edge does not actually<br>> intersect with your tile at all.<br>><br>> This makes the map query somewhat easy, just a sequence of

<br>> select * from nodes where quadtile like ?<br>> select * from segments join segment_quadtile on<br>> segment.id=segment_quadtile<br>> .quadtile where segment_quadtile like ?<br>> etc., etc.<br>><br>

> Using quadtree addresses is also useful for external applications. Say<br>> OSM had an RSS feed of changes that listed which quadtiles have been<br>> changed. Map renderers can thus use this information to invalidate

<br>> their cache for just that tile, and re-render, without having to check<br>> for changes each time. I could 'register' for information if anything<br>> changed in a list of quadtile addresess (say, those covring oxford),

> and it would be very easy to calculate when something I would be > interested in had happened. > > This isn't very complicated and could be done relatively quickly. I > have most of a java implementation buried on my harddrive somewhere...

<br>><br>><br></blockquote></div><br>