Re: [Flightgear-devel] Airport Database Model
Norman Vine writes: FGFS should be able to answer simple flightplan questions like I am leaving from KSFO flying to KLGA show me all airports that are large enough to handle a 747 within 100 miles of my flightpath. Indexing makes this trivial That's still an out-of-the-main-loop problem, though, so it doesn't matter to the to top-level code whether it's sitting on top of some moderately complex indexing code or some moderately complex linear-search code. We will need to be able to do fast searches on ATC frequencies, as we do currently with navaids, so we'll need some kind of indexing for that. There may be a reason for constant airport searches in the loop as well; I just haven't thought of it yet. All the best, David -- David Megginson, [EMAIL PROTECTED], http://www.megginson.com/ ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
David Megginson writes: Norman Vine writes: 2) is a little more complicated but we allready have a good start if we leverage the Scenery directory structure Agreed. I suggested using a quadtree for each 10x10 degree block but there are spherical indexing methods that might be better in that there is no cos(lat) shrink factor to account for when doing range lookups. Remember Knuth's (?) warnings about premature optimization, FWIW IMHO We really should move the entire scennery DB into a spherically oriented scheme. It would be quite easy using the spherical indexing method in the link that I posted and then we wouldn't need any index other then the directory tree and-you-could-fly-over-poles'ly Norman Norman ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
David Megginson wrote: Remember Knuth's (?) warnings about premature optimization, though. Amen. This blog says Knuth got it from Tony Hoare: We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. http://www.cookcomputing.com/blog/archives/84.html In that case, a simple linear search within the chunk and its neighbours is probably acceptable; for that matter, a linear search through the whole airport list wouldn't be that bad. Exactly. A typical use case might be a UI to search through all airports by name. So typing in New York would pull up Laguardia, Kennedy, etc... Users are happy to wait for 2 seconds or so for such a list. If, however, there's a reason that we'd want to redo the airport search every frame or every few frames, like we do for the navaids, then some kind of indexing will be essential. Right. But this indexing of nearby objects can be done in memory (since the set of nearby objects is already available via the tile set). There's not need for anything fancy on disk. Andy -- Andrew J. RossNextBus Information Systems Senior Software Engineer Emeryville, CA [EMAIL PROTECTED] http://www.nextbus.com Men go crazy in conflagrations. They only get better one by one. - Sting (misquoted) ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Andy Ross Right. But this indexing of nearby objects can be done in memory (since the set of nearby objects is already available via the tile set). There's not need for anything fancy on disk. FGFS should be able to answer simple flightplan questions like I am leaving from KSFO flying to KLGA show me all airports that are large enough to handle a 747 within 100 miles of my flightpath. Indexing makes this trivial Cheers Norman ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Andy Ross wrote: This is a good point, actually. Almost all the Linux filesystems use a 4k block as the minimum allocation unit*, and I presume NTFS is similar. I thought it was the other way around: that most Linux filesystems (by which I mean ext2) and NTFS had 1K or 0.5K blocks, and that Windows FAT filesystems had big (generally 4K to 16K) blocks. [* Geeky aside: reiserfs doesn't. It has a unique tail folding feature where the last sub-block of files gets folded into a single block with the tails of other files, so small files take space proportional to their actual size. Very cool, although apparently not used much.] ReiserFS is the default with SUSE 8.1 which I've just installed. Oh yes ... hey folks, I've just made the switch from Windows to Linux. Played with RedHat and Debian a couple of times in the last few years, but now I think it's a permanent switch. The windows issue is, I think, true only on very old FAT32 variants. I'm pretty sure the block size limitation went away at the same time the 2G limit did, no? Everything from Win98SE on should be fine, I believe. Any windows users want to comment? Certainly anyone running XP won't have this problem. My Windows ME (successor to 98SE) had a single 15 GB FAT-32 partition, and it uses 8 KB blocks. On that, FG scenery was eating large chunks of my disk space. I think FAT-32 is capable of using small (0.5K or 1K) blocks but is not configured to do so because the FAT itself would be big and therefore slow when following the block chain in large files. - Julian ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
On Thu, Oct 10, 2002 at 01:10:55PM -0700, Andy Ross wrote: Curtis L. Olson wrote: Just a couple thoughts to consider. We are looking at 16-20,000 airports so we couldn't stuff them all in a single directory. Even splitting them into subdirectories by first letter probably isn't enough. There are 17073 airports in the current database. Splitting on first letter only, the largest is (no surprise) 'K', with 2161 airports. On a lark, I created such a directory containing all the US airports. The creation process was relatively slow -- 20 seconds or so. But once the files are there, access to them is very fast (a few tenths of a second). This was true even after I was careful to flush the buffer cache by cat'ing a different disk to /dev/null, if the stuff is in the cache, of course, access is milliseconds at most. If you think about it, 2000 is about the same number as the number of device files in /dev, and no is complaining about performance issues there. One thing to note here is that all this cache take up RAM, and will be dropped on the floor as soon as there's any memory pressure. As it stands, on a 128MB system FlightGear will probably push most of that data out with it's own memory use, let alone leaving space for any other apps . . . So you'd likely get large performance deltas for this system depending on many subtle issues in the VM and VFS. At least using our own code would allow us to make things consistent . . . Not that I think it's a bad idea at all, though, particularly for the future: under Linux at least there are a number of new developments in filesystem-land that will make using this kind of thing much easier. ReiserFS is specifically designed for that kind of thing, and ext3 with the directory index performs as well or better on large directories. XFS probably handles such things fairly well, too. Reiser has tail packing, though at a performance cost, and there's some talk of adding tail packing to ext3. The problem is, FlightGear is portable, and most of these new features are Linux-only, and linux-2.4.$BIGNUM or 2.5+ only . . . Performing well under Linux with ReiserFS is a good advertisement for Linux and ReiserFS, but not so good for FlightGear if that's /all/ we perform well under. snippage the size of the scenery. Remember that with a file per airport, there is no need to have the whole airport database in the base package. You can download the airports along with the scenery. Airports aren't very useful without scenery, anyway. I rather like the idea of the airport files being /part/ of the scenery. It certainly seems to be where they'd belong, logically speaking. It'd also mean that the airports in the scenery matched perfectly the airports that FlightGear sees when running (unless you've explicitly hacked things up) - there've been several reports of runways and their navaids being completely out of sync with the scenery, and this seems like a good way to fix them . . . Simon -- PGP public key Id 0x144A991C, or http://himi.org/stuff/himi.asc (crappy) Homepage: http://himi.org doe #237 (see http://www.lemuria.org/DeCSS) My DeCSS mirror: ftp://himi.org/pub/mirrors/css/ msg08800/pgp0.pgp Description: PGP signature
Re: [Flightgear-devel] Airport Database Model
Julian Foad wrote: I thought it was the other way around: that most Linux filesystems (by which I mean ext2) and NTFS had 1K or 0.5K blocks, and that Windows FAT filesystems had big (generally 4K to 16K) blocks. Nope, 4k. The underlying disks have 512 byte blocks (all IDE and most SCSI, at least), but the OS doesn't cut things that fine. The 4k block size matches the processor page size on x86 and most other processors, so it makes things like swap and mmap'ed I/O simpler to implement. You can see this for yourself pretty easily (this is ext3; I'd be curious to see what the results are on other filesystems): # Make a scratch area mkdir foo cd foo # Make 100 empty files for i in 0 1 2 3 4 5 6 7 8 9; do for j in 0 1 2 3 4 5 6 7 8 9; do touch $i$j done done # Note that no space is taken up by the empty files, only 4k for the # directory itself cd .. du -s foo # Now append one byte to each of them cd foo for i in *; do echo $i done # Note that the directory now contains 404k -- 4k per file cd .. du -s foo -- Andrew J. RossNextBus Information Systems Senior Software Engineer Emeryville, CA [EMAIL PROTECTED] http://www.nextbus.com Men go crazy in conflagrations. They only get better one by one. - Sting (misquoted) ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Simon Fowler wrote: One thing to note here is that all this cache take up RAM, and will be dropped on the floor as soon as there's any memory pressure. Right, which is why I was careful to cite numbers that reflected actual disk I/O, and not cache performance. Even hitting the disk, performance is acceptable. If most machines are faster than that, it's a bug not a feature. :) Performing well under Linux with ReiserFS is a good advertisement for Linux and ReiserFS, but not so good for FlightGear if that's /all/ we perform well under. I think you have perhaps misinterpreted. My point was that a blunderingly simple file-per-airport scheme was adequate on all filesystems, not that it required fancy stuff. The reiserfs note was a fun bit of trivia about how OS authors try to accomodate stuff like this. If we work everywhere, but are blazingly fast (or take up far less space) under linux/reiserfs, I'd again consider that a feature and not a bug. I rather like the idea of the airport files being /part/ of the scenery. It certainly seems to be where they'd belong, logically speaking. [...] there've been several reports of runways and their navaids being completely out of sync with the scenery, and this seems like a good way to fix them. Right. The only complication is that there's an existing use case that requires doing fast lookup of airports by ID. My idea was to distribute files with the scenery and drop them in a single global directory. Trivially simple to implement and maintain -- users who discover airport or navaid bugs can just fix the file and post it to the mailing list; they don't need any coding experience at all. Andy -- Andrew J. RossNextBus Information Systems Senior Software Engineer Emeryville, CA [EMAIL PROTECTED] http://www.nextbus.com Men go crazy in conflagrations. They only get better one by one. - Sting (misquoted) ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
On Fri, 11 Oct 2002 13:50:21 -0700, Andy Ross [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]: # Make 100 empty files for i in 0 1 2 3 4 5 6 7 8 9; do for j in 0 1 2 3 4 5 6 7 8 9; do touch $i$j done done ..wee tweak: for i in $( seq 100 ) ; do touch $i done -- ..med vennlig hilsen = with Kind Regards from Arnt... ;-) ...with a number of polar bear hunters in his ancestry... Scenarios always come in sets of three: best case, worst case, and just in case. ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Arnt Karlsen wrote: ..wee tweak: for i in $( seq 100 ) ; do touch $i done Cute. You learn something new every day. I've never noticed that utility. I have a vague memory that there is some bash syntax that does a similar thing, too. And the $(...) syntax was new for me too -- I would have used backquotes. Honestly, I'm not much of a shell junkie. This is about as elaborate as any of my shell scripts get; anything bigger gets done in perl. Andy -- Andrew J. RossNextBus Information Systems Senior Software Engineer Emeryville, CA [EMAIL PROTECTED] http://www.nextbus.com Men go crazy in conflagrations. They only get better one by one. - Sting (misquoted) ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Simon Fowler writes: What about simply putting all the airport files in the scenery, and having a script that searched through the scenery directories for all the *-apt.xml files and built/updated a set of indexes from them? That keeps the files in the right place, and gives the indices needed to get fast lookups based on whatever criteria are needed. Sounds good to me Now we just need to figure out what we want for indices The way I see it we have two radically different needs 1) Search by name 2) Search by location 1) is easy and we could just use metakit or any other disk based indexable file I have suggested using a trie 2) is a little more complicated but we allready have a good start if we leverage the Scenery directory structure I suggested using a quadtree for each 10x10 degree block but there are spherical indexing methods that might be better in that there is no cos(lat) shrink factor to account for when doing range lookups. Here is a link to a good one http://www.sdss.jhu.edu/htm/implementation.html note this package is near optimum for a show all points within X distance when on a sphere and should be great at keeping an updated list of radio frequencies that were within range at 'altitude'. This is not a trivial task Cheers Norman ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
On Fri, 11 Oct 2002 15:04:51 -0700, Andy Ross [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]: Arnt Karlsen wrote: ..wee tweak: for i in $( seq 100 ) ; do ..should have been $( seq 0 1 99 ) to be precisely like your i/j job. touch $i done Cute. You learn something new every day. I've never noticed that utility. I have a vague memory that there is some bash syntax that does a similar thing, too. And the $(...) syntax was new for me too ..yeah, for i in ` seq 0 1 99 ` ; do etc. Cat skin. ;-) -- ..med vennlig hilsen = with Kind Regards from Arnt... ;-) ...with a number of polar bear hunters in his ancestry... Scenarios always come in sets of three: best case, worst case, and just in case. ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
[Flightgear-devel] Airport Database Model
I've been pulling information out of the DAFIF in different shapes and trying to decide how we should model our own airport database. For the external representation, we want something flexible enough that we can add new types of data easily -- fixed-length records with fixed-width fields just don't cut it. Any XML or INI files with airport data will be huge, of course, but they don't have to be part of the core base package -- we can include only precompiled binary files of some sort, and make the source XML available as a separate download. Getting on to the data model, there are some obvious relationships. For example, there is a one-to-many relationship between airports and runways, and another between airports and comm frequencies. We could model things purely relationally like this: airport id=CYOW ... /airport runway ident04/22/ident airport-refCYOW/airport-ref ... /runway runway ident07/25/ident airport-refCYOW/airport-ref ... /runway runway ident14/32/ident airport-refCYOW/airport-ref ... /runway comm typetower/type freq-mhz118.8/freq-mhz airport-refCYOW/airport-ref ... /comm But that kind of thing is a major pain to process. Personally, I prefer to model relationships by embedding when the relationship is one-to-many rather than many-to-many (i.e. no runway belongs to more than one airport): airport id=CYOW nameMacDonald-Cartier International/name short-nameOttawa/short-name lat../lat lon../lon elev../elev ... runways runway ident04/22/ident airport-refCYOW/airport-ref ... /runway runway ident07/25/ident airport-refCYOW/airport-ref ... /runway runway ident14/32/ident airport-refCYOW/airport-ref ... /runway /runways comms comm typetower/type freq-mhz118.8/freq-mhz airport-refCYOW/airport-ref ... /comm /comms /airport We can continue to add to a format like this to help with AI ATC and planes. For example, we can specify the location of the control tower, state when the lights are turned on and off (if not ARCAL) and what hours the tower is open, specify preferred runways for different types of aircraft (i.e. CYOW generally has 04 or 22 for light aircraft operating together with 07, 14, 25, or 32) and for noise-abatement, control-zone limits (when ATC hands you off), etc. etc. Comments? All the best, David -- David Megginson, [EMAIL PROTECTED], http://www.megginson.com/ ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Why can't we stick it into the scenery directories, but one directory up from the tiles, so we have one file per 10degx10deg of planet. That should ensure that FGFS doesn't need to load all that many files, and just having the one file in the base package will allow initial use. I've been pulling information out of the DAFIF in different shapes and trying to decide how we should model our own airport database. For the external representation, we want something flexible enough that we can add new types of data easily -- fixed-length records with fixed-width fields just don't cut it. Any XML or INI files with airport data will be huge, of course, but they don't have to be part of the core base package -- we can include only precompiled binary files of some sort, and make the source XML available as a separate download. Getting on to the data model, there are some obvious relationships. For example, there is a one-to-many relationship between airports and runways, and another between airports and comm frequencies. We could model things purely relationally like this: airport id=CYOW ... /airport runway ident04/22/ident airport-refCYOW/airport-ref ... /runway runway ident07/25/ident airport-refCYOW/airport-ref ... /runway runway ident14/32/ident airport-refCYOW/airport-ref ... /runway comm typetower/type freq-mhz118.8/freq-mhz airport-refCYOW/airport-ref ... /comm But that kind of thing is a major pain to process. Personally, I prefer to model relationships by embedding when the relationship is one-to-many rather than many-to-many (i.e. no runway belongs to more than one airport): airport id=CYOW nameMacDonald-Cartier International/name short-nameOttawa/short-name lat../lat lon../lon elev../elev ... runways runway ident04/22/ident airport-refCYOW/airport-ref ... /runway runway ident07/25/ident airport-refCYOW/airport-ref ... /runway runway ident14/32/ident airport-refCYOW/airport-ref ... /runway /runways comms comm typetower/type freq-mhz118.8/freq-mhz airport-refCYOW/airport-ref ... /comm /comms /airport We can continue to add to a format like this to help with AI ATC and planes. For example, we can specify the location of the control tower, state when the lights are turned on and off (if not ARCAL) and what hours the tower is open, specify preferred runways for different types of aircraft (i.e. CYOW generally has 04 or 22 for light aircraft operating together with 07, 14, 25, or 32) and for noise-abatement, control-zone limits (when ATC hands you off), etc. etc. Comments? All the best, David -- David Megginson, [EMAIL PROTECTED], http://www.megginson.com/ ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Alex Perry writes: Why can't we stick it into the scenery directories, but one directory up from the tiles, so we have one file per 10degx10deg of planet. That should ensure that FGFS doesn't need to load all that many files, and just having the one file in the base package will allow initial use. It's not a bad idea, except that FlightGear needs to be able to search all the airports at once to find the one the user wants to jump to. All the best, David -- David Megginson, [EMAIL PROTECTED], http://www.megginson.com/ ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
David Megginson wrote: Alex Perry writes: Why can't we stick it into the scenery directories, but one directory up from the tiles, so we have one file per 10degx10deg of planet. That should ensure that FGFS doesn't need to load all that many files, and just having the one file in the base package will allow initial use. It's not a bad idea, except that FlightGear needs to be able to search all the airports at once to find the one the user wants to jump to. It seems to me like the airport database is only searched on two keys: location and ID. Storing an index on location is trivial, as Alex points out -- store it with the location-specific data structure that is already indexed. So all we need is an index on name. Not to be too glib, but the OS already provides a rather nice index on named objects -- the filesystem. So in Scenery/w130n30/airports.xml you will find a simple list of airport ID's: airports idKSFO/id idKOAK/id ... /airports And look up the airport data itself under Airports/KSFO.xml: airport idKSFO/id nameSan Francisco Intl./name alt.../alt lat.../lat lon.../lon runway name11/name lat.../lat lon.../lon direction.../direction length.../length width.../width /runway runway ... /runway /airport The astute will point out that not all filesystems actually store indices on filenames (ext2 and FAT among them, sadly -- NTFS and reiserfs do have indices). With only a few thousand files, this isn't likely to be a real performance problem. Nonetheless, storing them sorted into directories is possible. Use Airports/K/KSFO.xml, for example, or even Airports/K/S/F/O.xml if you really want. :) This strikes me as easy to implement and much easier to maintain than the current metakit stuff. Andy -- Andrew J. RossNextBus Information Systems Senior Software Engineer Emeryville, CA [EMAIL PROTECTED] http://www.nextbus.com Men go crazy in conflagrations. They only get better one by one. - Sting (misquoted) ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Andy Ross Curtis L. Olson wrote: Just a couple thoughts to consider. We are looking at 16-20,000 airports so we couldn't stuff them all in a single directory. Even splitting them into subdirectories by first letter probably isn't enough. There are 17073 airports in the current database. Splitting on first letter only, the largest is (no surprise) 'K', with 2161 airports. On a lark, I created such a directory containing all the US airports. The creation process was relatively slow -- 20 seconds or so. But once the files are there, access to them is very fast (a few tenths of a second). This was true even after I was careful to flush the buffer cache by cat'ing a different disk to /dev/null, if the stuff is in the cache, of course, access is milliseconds at most. If you think about it, 2000 is about the same number as the number of device files in /dev, and no is complaining about performance issues there. And remember, we can split on the first two bytes (K/S/KSFO.xml) without any more difficulty (one extra line of code) and the whole problem goes away. Also, consider that with zillions of tiny files, much space is wasted on the file system which hits people in the windows land the hardest it seems because they often have a very large minimum file size. This is a good point, actually. Almost all the Linux filesystems use a 4k block as the minimum allocation unit*, and I presume NTFS is similar. Still, though, 4k per airport is still a tiny fraction of the size of the scenery. Remember that with a file per airport, there is no need to have the whole airport database in the base package. You can download the airports along with the scenery. The windows issue is, I think, true only on very old FAT32 variants. I'm pretty sure the block size limitation went away at the same time the 2G limit did, no? Everything from Win98SE on should be fine, I believe. Any windows users want to comment? Certainly anyone running XP won't have this problem. For the Index I reccomend making a single trie on the airport name that stores the bucket of the actual airport data file which lives in the same spot as it currently does. Then In each 10x10 degree directory I propose that we have a KD-tree spatial index of the positions of each airport in that block. This 2 tiered approach should give lighning fast lookups to both airport by name and what airports are near by. The indexes should be binary and we should distribute the tools that rebuild them when they change which won't be that often nor take very long. The indexes chould be able to dump themselves as XML files to facilitate rebuilding them and for easy inspection. With such a scheme we should be able to access any airport and determine which airports are within some sane distance in much less then a few tenths of a second order of manitude less at least Regards Norman ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
On Thu, 10 Oct 2002, Andy Ross wrote: And remember, we can split on the first two bytes (K/S/KSFO.xml) without any more difficulty (one extra line of code) and the whole problem goes away. From a processing point of view this makes sense - you don't need to store extra information about the location of the airfields, wher if as was suggested before it's broken down by state, then presumably you need to store the state for each and every airfield too, or is there some other method of telling which state each one is in that I've missed? -- Jon Stockill [EMAIL PROTECTED] ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Norman wrote: [ ... indexing scheme involving spacial partitions and trees ... ] With such a scheme we should be able to access any airport and determine which airports are within some sane distance in much less then a few tenths of a second order of manitude less at least True, but performance really isn't the goal here. The existing metakit stuff performs great. It's problem is that it's essentially unmaintainable without regenerating a megabyte of data*. Replacing one complicated binary data structure with another really doesn't address that need. My point was that a really simple one-file-per-airport scheme (you basically can't get any more maintainable than that) would work with adequate performance for typical usage. The airports in the current tile set could be kept in memory easily; arbitrary airports could be looked up quickly (under the UI definition of quick) by their ID; and the set of all airports would still be trivially searchable in a linear walk (looking for a match by name, for example) for cases where that capability was needed. Andy * Well, and that it involves a 3rd party C++ library that insists on installing itself as a shared library. My guess is that metakit version skew is the single biggest FAQable problem with new developers. It's a very real, very significant barrier to people who want to run the cool new stuff in CVS. This is my peeve, anyway. -- Andrew J. RossNextBus Information Systems Senior Software Engineer Emeryville, CA [EMAIL PROTECTED] http://www.nextbus.com Men go crazy in conflagrations. They only get better one by one. - Sting (misquoted) ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Andy Ross writes: Norman wrote: [ ... indexing scheme involving spacial partitions and trees ... ] With such a scheme we should be able to access any airport and determine which airports are within some sane distance in much less then a few tenths of a second order of manitude less at least My point was that a really simple one-file-per-airport scheme (you basically can't get any more maintainable than that) would work with adequate performance for typical usage. My scheme also uses one file per airport PLUS two fairly advanced yet relatively simple indexes for lightning quick seaches. I hope you note that I used a trie which is just a binary implementation of the individual file basd method that you proposed http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie.html And there is a performance issue here with searching radio frequencies for stations within range hence the spatial index for each 10x10 degree block. I believe that my proposal is a 'Dr Pangloss' type solution * Well, and that it involves a 3rd party C++ library that insists on installing itself as a shared library % cd $metakit % ../unix/configure --disable-shared % make core % make install best-of-both-worlds'ly yr's Norman ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Andy Ross writes: [* Geeky aside: reiserfs doesn't. It has a unique tail folding feature where the last sub-block of files gets folded into a single block with the tails of other files, so small files take space proportional to their actual size. Very cool, although apparently not used much.] Not true. It's not the default for RedHat, but I understand that it's better used in the European distros and I notice a fair number of users elsewhere. For scenery data like DEMs, ReiserFS gives me an extremely large improvement, sometimes taking only 25% of the disk space of the same data under E2FS (I didn't check E3FS, but it should be similar). I strongly recommend Reiser for anyone working with scenery data. All the best, David -- David Megginson, [EMAIL PROTECTED], http://www.megginson.com/ ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Jon Stockill writes: Is there any sort of master database from which all this can be generated? Or should we create one? No and yes. Note that I'm discussing only the external format, not the internal format someone might use in a SQL master repository (or whatever). That said, these are *small* data tables from a DBMS point of view -- they fit into memory trivially easily on most PCs, so an RDBMS isn't strictly necessary to manage and process them; it's just a convenience. Obviously, once we have the information in a managable format producing data files in any required format is a lot easier. It'd also make updates much simpler - I know one of my local strips actually consists of 1 closed surfaced runway, and a selection of grass strips - currently the database only has the surfaced runway in (EGCJ if anyone's *that* interested). My idea earlier today should allow faster updates. Instead of having one single master file, we have a separate one for each country or (in the case of the US and possible Canada and other airport-heavy countries) a separate file for each state or province. If you wanted to add to or update a UK airport, you could simply send your update to the UK file maintainer, and she or he could test it, merge it, and check it in. Right now, I'm almost a month behind on most of the patches in my Inbox, and I don't know if Curt's much better. You don't want anyone like us delaying updates. All the best, David -- David Megginson, [EMAIL PROTECTED], http://www.megginson.com/ ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel
Re: [Flightgear-devel] Airport Database Model
Jon Stockill writes: From a processing point of view this makes sense - you don't need to store extra information about the location of the airfields, wher if as was suggested before it's broken down by state, then presumably you need to store the state for each and every airfield too, or is there some other method of telling which state each one is in that I've missed? We're going to want to store that anyway, though, if only for the user pick-an-airport interface. Besides, it makes a lot more sense to pick a maintainer for all California airports than it does to pick a maintainer for all airports with an ICAO code starting with KB. All the best, David -- David Megginson, [EMAIL PROTECTED], http://www.megginson.com/ ___ Flightgear-devel mailing list [EMAIL PROTECTED] http://mail.flightgear.org/mailman/listinfo/flightgear-devel