Ideal database for geo (map) data
I'm looking for suggestions for an ideal database or data structure for storing a map. Essentially, the map consists of "ways" which are like roads, paths, etc. Ways contain nodes (which have a latitude and longitude coordinate, and sometimes an altitude.)
Any such database or structure:
should be able to locate all the nodes in a bounding box quickly (milliseconds)
optionally, should not considerably slow down when a large number of nodes are in a bounding box vs. a small number of nodes, or if the bounding box is large
should be able to find nodes that connect directly: e.g. the node which connects two ways
could be read only
should be compact (avoids wasting space) - I'm looking to fit a map of the UK into less than 1 GB. I have a sat nav that does this with about 800 MB of space on an SD card.
I was thinking initially of quad trees to store ways. But a fast implementation is tricky, and they don't work for individual nodes; all nodes get put in the smallest bbox possible.
(I'm deliberately using the same terminology of Open Street Map because I plan to use that data.)
I'd recommend with PostGIS 1.5 using the geography type as it's suited to what you want, however my only concern with using something like this on an embedded device would be memory usage.
I've built something vaguely related using a non GIS database (firebird) in Java and the performance was more than adequate for retrieving points within a bounding box (although fancy SQL was required which isn't the case with PostGIS).
PostGIS might be the best choice. Note: PostGIS is PostgreSQL with geo-extensions. You literally install postgres, and then run various scripts which add in geo functions and types.
See the OpenStreetMap information about PostGIS. you can load OpenStreetMap planet files/planet extracts, into PostGIS using osm2pgsql, and this is what is done on the OpenStreetMap tile server, where the Mapnik renderer runs. However...
There is also a more raw database schema for OpenStreetMap data (tables called "nodes" and "ways" etc) This is what main OpenStreetMap database server uses for storing its geo-data and allowing edits over an API. This isn't so clever when it comes to spatial indexing etc, but nice and simple. You can create a database in this format by installing the OpenStreetMap API/website ruby on rails code. This is most reliable way of setting up an up-to-date version of the database schema (defined by the rails migrations). After that you might run the osmosis tool to populate the database.
The best database I know of for Geographic data is PostgreSQL with geo-extensions, but I do not know about speed. I know that OSM uses this, but they have access to a huge computer infrastructure that is fast. I also know that they have several request for people that can write speedier programs for them.
I would say that Quadtree is a really good option for handling geospartial data, it seems that you allows the squares to get too small from what I can tell. You can make the boundaries softer (allow a node to be in two leaves of the Quadtree) and add a minimum amount of nodes per leaf. Say that any leaf are not allowed to contain less than 64 nodes, and no more than 1024.
Sorting is especially important for speed here, a suggestion would be to sort up åreas that would be more likely to be accessed fist. Say that 70% of all requests would be around London, then it would be fastest to have this data in the beginning of the file to lessen the search time.
PostGIS is not the only database that supports geospatial data, but the price point is very nice. Hard to beat "free".
But there are other free options, and some readers may already have another relational database system in place and want to leverage that expertise instead of having to learn PostGIS. Any database supporting the Open Geographical Consortium specifications (OGC or OpenGeo) will suffice for the scenario you describe.
And just like the maxim from the world of photography - "The best camera is the one you have with you" - sometimes the ideal spatial database is the one you already have and know how to use.
So here is a list of all the options I know of:
Spatial RDBMS - free option available
- Oracle (with Spatial or Locator) (Free option: Oracle XE + Locator)
- MS SQL Server (2008 or later) (Free option: SQL Server Express)
Spatial RDBMS - no free option
- DB2 (with Spatial Extender)
- Informix (with Spatial Blade)
Less Than Ideal Spatial RDBMS
- MySQL Spatial (very limited function set)
- ArcSDE (you add it on to an existing RDBMS)
I'm not sure about space, but you might want to look at use any Geo extension for common database servers (if at all possible). They usually offer fast geographical indexing, bounding box based (answer to 1 and 2) many geographic procedures to make calculations (answer to 3, intersect(way1,way2)).
Also, your question is a better match for http://gis.stackexchange.com