Is there any way I can use a Key-Value store for geospatial data?

Question

I have used many relational databases in the past, but I have also read about all NoSQL databases, and the Key-Value stores looks interesting.

When I store geometric object I mostly use five indexed columns ID, MIN_X, MAX_X, MIN_Y and MAX_Y (where X and Y are in a map projection). I don't need an index on my other data.

I need the X and Y values to lookup objects in a specified place (map rectangle), and I need the ID value if I want to update a specified object.

Is there any way that I can use a Key-Value store for this?

Answer 1

We use Google AppEngine to run spatial/attribute queries and the main issue (from day one) is how to index large sets of arbitrarily sized lines/polygons. Point data isn't too difficult (see geohash, geomodel etc) but sets of randomly clustered small/large polygons was always a problem (and in some cases, still is)

I've tried several different versions of spatial indexing on GAE but most are just variants of two below. None were as fast as SQL databases and all have pros/cons. the tradeoffs seems reasonable for most internet based mapping apps though. Also, the two below need to be coupled with in-memory geometry culling (via JTS etc) to remove any features that don't fit the final search parameters. and finally, they rely on GAE specific features but I'm sure it could be applied to other architectures (or use TyphoonAE to run on a linux cluster, ec2 etc)

Grids - Pack all the features for a certain area into a known grid index. Place a small spatial index on the grid so you quickly navigate the set of features that it contains. For most queries, you'll only need to pull a handful of grids which is fast, since you know the exact grid naming convention and how it related to K/V entities (gets, not queries)

Pros - pretty fast, easy to implement, no memory footprint.

Cons - preprocessing needed, user needs to decide grid size, large geoms are shared on several grids, clustering can cause the grids to become overloaded, serialization/deserialization costs can be an issue (even when compressed via protocol buffers)

QuadKeys - This is the current implementation. basically its the same as Grids except there is no set grid level. as features are added, they are indexed by the quadkey grid that completely contains their bounds (or in some cases, split into two when a single quadkey can't be used, think dateline). After the qk is found, its then split into a max number of smaller qk that provide finer grain representations of the feature. a pointer/bbox to that feature is then packed into a lightweight gridindex (group of features) that can be queried (an original design queried the features directly but this proved too slow/CPU intensive in cases where the resultset was large)

Polyline Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_1.png Polygon Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_2.png

The quadkey naming convention used above is well known and more importantly, tends to preserve locality (described more here )

The polygon above looks something like this: 0320101013123 03201010131212 03201010131213 0320101013132 0320101013133 03201010131302 03201010131303 032010101313002 032010101313003 032010101313012 032010101313013 03201010131312 03201010131313 032010101313102 ...

if the query bounds is small enough, you can directly fetch via the qk. this is optimal since its only a single, batch rpc call to the GAE datatore. if the bounds is large enough that it included too many possible qks (>1000) then you can alternatively query using a filter (ex: qk >= 0320101013 and qk <= 0320101013 + \ufffd ). The quadkey naming convention plus the way GAE indexes strings allows the query above to fetch only the existing grids that fall below that qk value.

there are other caveats and perf issues but in general, its the ability to query on the quadkeys that makes it feasible

examples - query on US counties: geojson

Pros - pretty fast, no grid size config, no memory footprint, no overcrowded grids

Cons - preprocessing needed, possible overfetch in some scenarios, no polar data

Space Filling Curves - Take a look at Alfred's NextGen Queries talk at Google I/O this year. The inclusion of generic space/time filling curves along with the new MultiQuery operators (run in parallel) will allow for some really cool spatial queries. Will it beat traditional SQL performance? Hard to say but it should scale really well. And we're rapidly approaching a future where always-on mobile devices of all shapes/sizes will dramatically ramp up the traffic to your site/service.

finally, I would also agree that you should look very closely at your problem domain before choosing NoSQL over SQL. In our case, I really liked the pricing model of GAE so there really wasn't a choice but if you do not need to scale, save yourself some time and just use a standard sql db

Answer 2

I have heard of GeoCouch, which is an implementation of CouchDB for locational based data. And I also think that MongoDB has geospatial indexing capabilities.

Answer 3

This is mainly an question about algorithms. Stack Overflow may also be a good place to ask it.

In any case, the answer to your direct question is "yes, you can use a kvp store to represent spatial data." A better question, however might be "SHOULD I use a kvp store to represent spatial data?"

The answer to that question (like many others) is, "it depends". It depends on your scale, your (transactional) work load, the nature of the data, and the computational infrastructure you have at your disposal.

A kvp store will have low overhead, which can help increase throughput for high volumes of insert and update parallelism. It won't however be very fast a performing spatial searches (find all objects within a rectangle). For that you would want a spatial index, like an R-Tree.

However, if you have a really large data volume, and a huge cluster of computers, then using a kvp index could provide some perormance benefits. The only way to really know for sure is to take perf measurements using the actual data and access pattens you expect to encounter.

Update:

Here is a little bit more info. You can use a KVP store to do spatial lookups. The problem is that it is slow. To see why, consider something like this:

  ***********
  ***********
  ***********
  ***********
  ****###****
  ****###****
  ****###****
  ***********
  ***********
  ***********
  ***********

Where * and # represent objects, laid out in an 11x11 grid, with the origin in the top left corner. Imagine a search for objects within the rectangle (4,4)-(7,7). That should find all the "#"'s. Assuming that you are using a b+-tree to represent your indexes in the KVP store, you could find the results using either the "X" index or the "Y" index. In this case, it doesn't matter which. For the sake of discussion, I'll use the x index. You would do a log(n) lookup in the X index to find the first node with an X value of "4" and then iterate through the b+-tree leaf nodes until you found a node with a value greater than 7. As you iterate through the x index you would then reject anything that was outside the desired y range.

This is slow. Imagine it on a large grid, with the same density, say 100 K * 100 K. There you would end up having to scan "300, 000" index entries to find only 9 records. If you use a properly balanced R-Tree, however, then the index lookup would probably only need to scan about 90 records or so. That's a huge difference.

The problem, however, is that keeping an R-Tree balanced is expensive. This is why the answer is "it depends", and why the question "should I do this" is much more important than "how do I do it".

If you insert and remove records a lot, and mostly do "object ID" lookup, and don't frequently do the "spatial" lookup, then using your KVP index will give you better performance for what you actually want to use the system for. However, if you insert or delete infrequently, but do spatial lookups a lot, then you want to use an R-Tree.

Answer 4

If you're using lat/long values, you might be able to use geohashes as the value part of your store.

Here's one for NYC. dr5regy6rc6ye

With the geohash, you can start knocking off characters at the end of the geohash to get a grid of varying precision: http://geohash.org/dr5re

Example js implementation: http://github.com/davetroy/geohash-js

Answer 5

In the majority of cases, you will get more utility from relational data storage than you will from key/value or key/value/type storage. There are considerable complexities around efficiently querying and reporting on this kind of data scheme.

My advice would be to closely evaluate whether your scale actually requires NoSQL before considering how to use it.

Answer 6

Take a look at this GAE app that serializes JTS geometry to BigTable. You might be able to adopt it for other NoSQL storage engines.

Answer 7

MongoDB has the facility to create and consume geospatial indexes based on strict 2d [x,y] tuple properties of Documents, and allows both 'near' and 'bounds' type queries. However it doesn't handle any corrections for projections and uses an idealized model of a flat earth

Answer 8

I'd use key/value stores only as a caching layer, see http://www.membase.org/ or http://wiki.basho.com/display/RIAK/How+Things+Work (riak_kv_cache_backend)

Depending on your app needs, you might still want to have SQL access to the data.

Answer 9

This is certainly an emerging area of interest, a few upcoming talks from the FOSS4G conference:

• GeoCouch: A Spatial Index for CouchDB
• Geospatial Indexing with MongoDB
• Beyond PostGIS
• Distributed Spatial Indexing in the Cloud