<br><div class="gmail_quote">On Mon, Aug 17, 2009 at 11:00 PM, Mikel Maron <span dir="ltr"><<a href="mailto:mikel_maron@yahoo.com">mikel_maron@yahoo.com</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><div style="font-family: times new roman,new york,times,serif; font-size: 12pt; color: rgb(0, 0, 0);"><div><br>Look forward to some good
 ideas.<br></div></div></div></blockquote><div><br>Here is my plan :<br>* Create a separate server that starts with a very old planet file and then processes the diffs.<br>* Use Mercator projection, divide the map into tiles of fixed size of approximately 2km x 2km. Enumerate the tiles according to the Hilbert curve. This scheme works well for rendering cities areas at high zoom most queries (which are the vast majority of queries). The lack of performance on other queries will be more than compensated for (as gosmore proves).<br>
* To prevent wasting disk space on ocean, desert and tiles, choose a function that "maps" the many tiles unto few buckets (hash function).<br>* For each bucket allocate a few kilobytes of disk space. We need to mark it as empty, but there is a nice Linux trick of marking parts of a file as zero and delaying the actual writing until that part of the file is actually modified.<br>
* Now add all the data to the file i.e. write the info into the buckets. If a bucket K gets full, use K+1. The structure(s) used for nodes have space to point to the ways that use them. The ways are store in the buckets, preferably next to one of the nodes used in it. Ways point to the nodes that they depend on. Use a similar scheme for relations.<br>
* Every node, way and relation must have a start time, end time (initially infinite) and a pointer to its successor.<br>* Now process the diff files. Old nodes, ways & relations aren't removed. Instead their end times and successors are updated.<br>
* To find old nodes, ways and relations we need an index that maps their id numbers to where they currently are in the file. These indices are not stored in the file (RAM?). Note that I'm only interested in serving bounding box queries for any given time T. I'm not interested in serving queries like "Where was node N at time T ?" So old versions of this index is not necessary.<br>
* To serve a query, iterate over all the tiles and look in the buckets. If a bucket K is full, look in K+1, until you found one with unused space.<br>* Over time many buckets will get full and this will mean that the server will need to linearly search larger and larger parts of the file. When this performance degradation happens (say after several months), we just create a new file. The server then looks at the T values of the queries to choose the correct file.<br>
<br>Then the T parameter will appear in the permalink, it will get passed to mod_tile etc. and you will get a map of burning man 2008.<br><br>And the possibility of differential rendering also exist.<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div><div style="font-family: times new roman,new york,times,serif; font-size: 12pt; color: rgb(0, 0, 0);"><div><br>Thanks<br><font color="#888888">Mikel<br></font></div></div></div><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>
<br></blockquote></div><br>