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 _______________________________________________ talk mailing list [email protected] http://lists.openstreetmap.org/listinfo/talk
