[OSM-talk] Ideas for student project on OSM

[Nic Roets]

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).

* Arrange the tiles in a 2-D Hilbert curve to reduce disk seeks
* Use integers, because most of the operations are compares

On Tue, Oct 28, 2008 at 10:24 PM, Freek <freek_osm at vanwal.nl> wrote:

> On Tuesday 28 October 2008, Iván Sánchez Ortega wrote:
> > - Benchmark a quadtile solution vs. a more general geodetic grid tree
> > solution (get the quadtile idea, apply it to triangles instead of
> squares,
> > put 'em on a geodesic sphere; basically, instead if dividing a square
> into
> > four squares, you increase the chord factor of a fractal geodesic sphere
> by
> > one). Throw in a R-tree benchmark for good measure.
>
> If you want to minimize the number of disk seeks in a quadtile-like
> approach,
> using a special type of space-filling curve can also help [1]. It may be
> interesting to see if such an optimization criterion leads to different
> space-filling curves for triangle-based subdivisions.
>
> By the way, on the side of R-trees (special) space-filling curves can also
> be
> used to improve query efficiency, see the recent thread on dev [2]. A
> comparison with a standard type R-tree would not be "fair" in my opinion.
>
> On Tuesday 28 October 2008, Matt Amos wrote:
> > there were some published benchmarks of icosahedral quadtiles vs.
> > rectangular quadtiles vs. R(*?)-trees and rectangular quadtiles "won"
> > for those benchmark conditions. i can't find the paper now, though.
> > this was one of the reasons i never finished my icosahedral OSM server
> > implementation. (the other one was that i spent all my time reading
> > papers, not actually writing code...)
>
> I have not seen those (would be interested), but I would guess rectangular
> queries make an equilateral-triangle subdivision inherently less
> favourable,
> even though the geometry is distorted by the projection (we don't have much
> data near the poles anyway ;-)
>
> [1] http://dx.doi.org/10.1016/S0304-3975(96)00259-9<http://dx.doi.org/10.1016/S0304-3975%2896%2900259-9>(
> sciencedirect.com, no
> open access. The z-curve in Fig. 2 is basically the one used in current
> quadtile implementations.)
> [2] http://lists.openstreetmap.org/pipermail/dev/2008-October/012185.html
>
> --
> Freek
>
> _______________________________________________
> talk mailing list
> talk at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/talk/attachments/20081028/b8751bdc/attachment.html>