An increasing demand for geographic data imposes high query loads on data providers. Main players in the web (e.g. Facebook) use distributed memory caching systems such as Memcached to cache frequently accessed data in a key-value fashion. However, for spatial/geographic data as provided by OpenStreetMap for instance, the key-value paradigm is insufficient or at least unhandy, as many location-based services or applications require data which is located in certain ranges or regions.
How do service providers most commonly implement high scale access to spatial data with region query support?
(a) Is there any widely used distributed caching system similar to Memcached available, which supports region queries out of the box?
(b) Do application developers use standard key-value systems (such as Memcached) and manually remap query ranges to keys via space-filling curves or other spatial re-mapping techniques.
(c) Or can scalability be provided by a relational database with spatial extender which is extensively partitioned and replicated among several db instances.
I like the idea of using space-filling curves. Why not ask a developer, for example, at Esri? That is, go to Esri.com and ask a question...maybe you have already done so...but, I think that's what I would do. So, although I have no direct answer, I just suggest how I might explore trying to find an answer. I will be interested to see what you learn.
Have you looked at nonrelational options such as Mongo DB? Seems possible you could cache the results of a spatial query using a region.
Here is a blog I found kicking around some of the ideas:
http://myadventuresincoding.wordpress.com/2011/10/02/mongodb-geospatial-queries/
As Joel suggested, MongoDB could fit your problem. They recently have added a lot of useful features for geospatial queries; most of them in the last two releases (2.2 and 2.4).
Other interesting db could be OrientDB and Neo4J (graph db).
In particular Neo4J implements a set of interesting features in the neo4j-spatial package (see http://www.neo4j.org/develop/spatial and https://github.com/neo4j/spatial#readme)
Others are:
- GeoCouch, extension to Apache CouchDB that adds two-dimensional spatial indexing support.
- SimpleGeo built a Scalable Geospatial Database with Apache Cassandra.
- Geodis is a Redis based geo resolving library
Let us know what you finally choose and why ;)
Dear Sandra, Zac, Mario and Wendy,
thank you for these interesting hints. I just started to explore them and have not fully formed my mind yet. However, what makes me feel slightly against MongoDB, other NoSQL databases and relational databases is that they require disk space (at least to my knowledge) and cannot fully operate in main memory as for instance Memcached. I like the idea of keeping a respectively small portion of frequently used data in main memory while the complete data set resides in a persistent storage like MongoDB. I reckon that this saves disk space, as it enables using disk-less machines to process most of the workload. I wonder if there is a Memcached for spatial data or if anybody has ever used a spatial main memory database for this purpose.
Hi Carlos,
if your requirement is an in-memory key-store you could try redis ( using the Geodis package or others available on github). Redis is a reasonably fast key-store and could be configured to completely disable persistence (only in-memory). However AFAIK its geospatial query libraries are less mature and actively developed compared to neo4j and mongo solutions.
Space filling curves have indeed been used to access geospatial data. In fact, I have used them myself to build real products. See my article at http://www.drdobbs.com/database/space-filling-curves-in-geospatial-appli/184410998. Space-filling curves are most useful when using a existing database platform that does not support a spatial access method. The spatial keys can be indexed and queries can be converted to spatial keys, as you suggested. Which space-filling curve to use? A morton curve is simpler to implement, but hilbert curves can offer a little better performance. Peano curves might have some marginal benefit, but I don't know whether they have been used for spatial access.
I should add that many relational database support R-trees for fast spatial access. those include MySQL and Oracle (never used but heard its a pain to use).
Hi Mario and Ron,
thank you for the pointers! Especially Ron's article is helpful as it describes how a key-store like Memcached or Redis (as proposed by Mario) can be tweaked into processing range queries. Meanwhile, I also posted my question into the developer's forum at Esri ArcGIS as Sandra suggested. I'll let you know, if they come up with something interesting!
Another option is to use a relational database like PostgreSQL with the PostGIS extension, but behind the powerful Django ORM, so queries are easy to build and run with a bunch of predefined spatial lookups: https://docs.djangoproject.com/en/dev/ref/contrib/gis/geoquerysets/
In the other hand, PostgreSQL is a regular database, so you can always cache the queries using the cache you want, as well as replicate your data, make partitions or setup a cluster.
Yes, PostGIS also has spatial indexing, undoubtedly R-trees. Anyway, Carlos, you are welcome, and let me know if you'd like more help with space-filling curves.
Hi Javier and Ron,
thanks for the reference to Django, an ORM I have not been aware of until now. Interesting enough is that it also provides a key-value cache API using Memcached as back-end. And that takes me back to Ron's space-filling curves which are required to cache spatial data in key-value fashion. So thanks, Ron, for your offer. I will probably come back to it, as soon as I have started the coding part of this matter.
- Badges
- Science method