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