Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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

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 an specified object.

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

share|improve this question

9 Answers 9

up vote 18 down vote accepted

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 Polygon Quadkeys

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
+1 Good answer Scott! –  JasonBirch Jul 23 '10 at 2:18
    
I would not accept an answer like "yes, you can." because I want to know HOW. And "SHOULD I.." is not a better question, because as you said "it depends". –  Jonas Jul 24 '10 at 16:57
1  
I have to disagree with you. If you want to build a useful system, or leave behind a useful reference on the internet for other people building similar systems, then "should I" is much more important than "how". In the interest of being helpful, however I did edit my answer for you to provide some info on how. –  Scott Wisniewski Jul 24 '10 at 21:29
    
@Jonas I believe the "advice" answers you got were because of the way you asked the question: "but I have also read about all NoSQL databases, and the Key-Value stores looks interesting." This has all the hallmarks of a solution looking for a problem. –  JasonBirch Jul 25 '10 at 18:55
    
NoSQL does solve a problem, but it is a problem that practically no one has because they aren't working on a massive enough scale. Unfortunately it is always nice to think that our own systems are bigger in the grand scheme of things than they actually are. :) –  JamesRyan Aug 9 '10 at 9:18

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.

share|improve this answer

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.

share|improve this answer
    
Yes, they both do, and SimpleGeo is building a spatial extension to Cassandra. I haven't heard anything in Voldemort or MemCache –  TheSteve0 Jul 23 '10 at 4:39
    
Oh, I love what SimpleGeo is doing. I am jealous and would love to work for them! –  JoshFinnie Jul 23 '10 at 14:39

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.

share|improve this answer

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.

share|improve this answer
1  
Here's an example of a problem you might have (and a solution to it) if you need to calculate if a point is inside or outside of a geometry. code.google.com/p/giscloud/wiki/SerializedSpatialIndexes –  Jon Bringhurst Jul 22 '10 at 20:20
    
Hey @Jon, that would be better added as an Answer. That way it can stand on its own, and you'll get credit for it if people think it has merit! –  JasonBirch Jul 22 '10 at 20:21

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.