On Sun, Oct 19, 2008 at 01:42:39PM +0200, Freek wrote:
Indices (or data) with one entry per id (potentially a starting point inside another index).Much simpler, as more complex index structures also use more memory (thus risking disk access penalty). Sorted lists, scanned with binary search (=> O(log n)).Ok, but what about the O(1)?
Regarding index structures, I think you can reduce disk access penalty by using slightly more complex index structures (in this case B-trees for example). The O(log_2 n) is the number of disk operations you have to perform. Using a B-tree you can get this down to O(log_B n), where B is the number of elements per node. If you use your "implicit pointer" idea, you don't even have the extra storage penalty :-)Depending on the application (RAM size, access patterns, etc.), it might be worth it. Configurable index methods would be great. :)
So you transparently rewrite internal IDs to external ones and vice versa on in- and output?Not transparently within an application, but for in- and output (e.g. start, goal and path for a router) the application probably will convert them, so it's transparently for the user.
OSM ids are sparse (at most one object per id). Internal ids always point to exactly one object (at least one, at most one).What is the advantage of having separate internal IDs?
Ah, nice. By the way, is all this still in (early) development, or is there already a description/website/demo online?There's no website or demo, but it works quite fine in router prototype (routing works fine but CLI and postprocessing are not implemented yet). It's available (license is GPL) in my 2008 GNU arch repository [1] as osmbindb--devel--0.1 (the router is osmroute--devel--2.0 in my 2007 repository [2]). To check it out:
1. install tla (apt-get install tla, emerge tla, ...)2. tla register-archive http:///sascha.silbe.org/arch/[EMAIL PROTECTED]
3. tla get osmbindb--devel--0.1 osmbindb--devel--0.1This will check it out into a directory called osmbindb--devel--0.1 (the second parameter of the tla get invocation)
Ok. Do you plan to make your current format into a kind of standard for binary, indexed OSM data or do you want to go with, say, Marcus' plans (for which I don't clearly see if he wants it to be lossy or lossless)?Well, obviously I like my format better, but if any other proposal (including Markus' one) turns out to be better, that's fine with me. :)
[Geocoding with Gosmore]
Judging from Nic Roets' mails on [EMAIL PROTECTED], there is no spatial index involved.I remembered that it did. The feature list on the wiki says:"Incremental search of all tags. Results are ordered from nearest to farthest."
[1] http:///sascha.silbe.org/arch/[EMAIL PROTECTED] [2] http:///sascha.silbe.org/arch/[EMAIL PROTECTED] CU Sascha -- http://sascha.silbe.org/ http://www.infra-silbe.de/
signature.asc
Description: Digital signature
_______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
