Well, I'm really pleased with the performance of the fixed tile size algorithms I implemented in gosmore. OSM data is remarkably "flat" : Either a tile is empty (sea / rural / unmapped) or has approximately the same number of objects as any other urban tile. So if the tiles are small enough you don't need a second index (e.g. subdividing the tiles).<br>
<br>* Arrange the tiles in a 2-D Hilbert curve to reduce disk seeks<br>* Use integers, because most of the operations are compares<br><br><div class="gmail_quote">On Tue, Oct 28, 2008 at 10:24 PM, Freek <span dir="ltr"><<a href="mailto:freek_osm@vanwal.nl">freek_osm@vanwal.nl</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">On Tuesday 28 October 2008, Iván Sánchez Ortega wrote:<br>
> - Benchmark a quadtile solution vs. a more general geodetic grid tree<br>
> solution (get the quadtile idea, apply it to triangles instead of squares,<br>
> put 'em on a geodesic sphere; basically, instead if dividing a square into<br>
> four squares, you increase the chord factor of a fractal geodesic sphere by<br>
> one). Throw in a R-tree benchmark for good measure.<br>
<br>
</div>If you want to minimize the number of disk seeks in a quadtile-like approach,<br>
using a special type of space-filling curve can also help [1]. It may be<br>
interesting to see if such an optimization criterion leads to different<br>
space-filling curves for triangle-based subdivisions.<br>
<br>
By the way, on the side of R-trees (special) space-filling curves can also be<br>
used to improve query efficiency, see the recent thread on dev [2]. A<br>
comparison with a standard type R-tree would not be "fair" in my opinion.<br>
<div class="Ih2E3d"><br>
On Tuesday 28 October 2008, Matt Amos wrote:<br>
> there were some published benchmarks of icosahedral quadtiles vs.<br>
> rectangular quadtiles vs. R(*?)-trees and rectangular quadtiles "won"<br>
> for those benchmark conditions. i can't find the paper now, though.<br>
> this was one of the reasons i never finished my icosahedral OSM server<br>
> implementation. (the other one was that i spent all my time reading<br>
> papers, not actually writing code...)<br>
<br>
</div>I have not seen those (would be interested), but I would guess rectangular<br>
queries make an equilateral-triangle subdivision inherently less favourable,<br>
even though the geometry is distorted by the projection (we don't have much<br>
data near the poles anyway ;-)<br>
<br>
[1] <a href="http://dx.doi.org/10.1016/S0304-3975%2896%2900259-9" target="_blank">http://dx.doi.org/10.1016/S0304-3975(96)00259-9</a> (<a href="http://sciencedirect.com" target="_blank">sciencedirect.com</a>, no<br>
open access. The z-curve in Fig. 2 is basically the one used in current<br>
quadtile implementations.)<br>
[2] <a href="http://lists.openstreetmap.org/pipermail/dev/2008-October/012185.html" target="_blank">http://lists.openstreetmap.org/pipermail/dev/2008-October/012185.html</a><br>
<br>
--<br>
<font color="#888888">Freek<br>
</font><div><div></div><div class="Wj3C7c"><br>
_______________________________________________<br>
talk mailing list<br>
<a href="mailto:talk@openstreetmap.org">talk@openstreetmap.org</a><br>
<a href="http://lists.openstreetmap.org/listinfo/talk" target="_blank">http://lists.openstreetmap.org/listinfo/talk</a><br>
</div></div></blockquote></div><br>