Ideal database for geo (map) data

Question

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:

1. should be able to locate all the nodes in a bounding box quickly (milliseconds)

2. 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

3. should be able to find nodes that connect directly: e.g. the node which connects two ways

4. could be read only

5. 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.)

Answer 1

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

Answer 2

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).

Answer 3

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.

Answer 4

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.