[OSM-talk] Ideas for student project on OSM

[Freek]

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 (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