Why Are Geospatial Databases So Hard to Build?

http://www.jandrewrogers.com/2015/03/02/geospatial-databases-are-hard?h

by chippy • 11 years ago

183 54 11 years ago

A great article, and very true as MemSQL (w2011) just announced its own real-time Geospatial capabilities: http://blog.memsql.com/geospatial-intelligence/

nigwil_• 11 years ago

A possible solution to the firehose problem are stream-databases, the catch phrase is "rather than data waiting for queries, it is queries waiting for data".

The people behind Truviso (http://en.wikipedia.org/wiki/Truviso subsequently bought out by Cisco) had an implementation of stream processing, an overview is here:

http://www.neilconway.org/docs/cidr2009_franklin.pdf

We looked at Truviso when we had to solve video-player-analytics and it seemed to us to solve that problem. I imagine a tree-structure of stream-queries where the leaves are the data gathering points, aggregating up the tree for summaries would address the scaling problem.

jandrewrogers8• 11 years ago

The problem with stream processing is that spatiotemporal analytics are rarely summarizations. Typically, the only aggregates that are computed at ingest are path, vector, and polygon features (e.g. an entity path reconstructed from samples). This is not the real-time analysis part of the application, just the ingest processing, and these features must be continuously indexed and online.

Most spatiotemporal analytics compare events and entity behavior in the present with the past at a pretty fine-grained level, hence why the summarizations or in-memory shortcuts do not work that well in practice. Your working set is frequently measured in days to months of data for common use cases, limited primarily by the storage budget.

In short, spatiotemporal analytics requires fully online indexing of the data in the stream, and a pretty big index at that for most apps.

joe_the_user4• 11 years ago

Hmm, Do you have to index intervals directly?

Algorithms for spatially indexing points are tractable - see k-d trees etc. R-trees seem pretty lame to be honest, like an ad-hoc data structure to partly meet a number of requirements.

Of course, some kinds of indexing and searching are inherently harder than others. But I don't see why one couldn't program any needed spatial algorithm directly from just an index of all points in the system.

For example, suppose you have an index of triangles. If want to find all triangle intersecting triangle (x,y,z), you could itterative expand a near-neighbor search from each point. Every point you find close than the given triangle-point's further point is a potential neighbor and could checked reasonably quickly. This gives the set S of intersecting triangles to a given triangle in log^n(size(S)), making the process relatively scalable.

K-d tree seem more sensible: http://en.wikipedia.org/wiki/K-d_tree

And there's more: "Storing objects in a space-partitioning data structure (kd-tree or BSP for example) makes it easy and fast to perform certain kinds of geometry queries – for example in determining whether a ray intersects an object, space partitioning can reduce the number of intersection test to just a few per primary ray, yielding a logarithmic time complexity with respect to the number of polygons."

Lends credence to my argument that a polygon-polygon intersection should be obtainable in log^n or maybe even log time.

Space partitioning in general does cool stuff: http://en.wikipedia.org/wiki/Space_partitioning

falcolas2• 11 years ago

The problem is less with the mathematics, but efficient storage and retrieval of a large number of points (i.e. index won't fit in memory) from disk. Doing a search across a tree rendered to disk is really slow.

Even with mathematically sound storage trees as indexes, locations which are close in space could easily be split between two arms of the tree, making proximity searches quite expensive - you would have to traverse the entire tree to ensure that you do not miss data separated by a poor splitting plane.

There are a number of theoretically efficient solutions to this, but they are all become remarkably inefficient when you add in a hard drive.

gobengo• 11 years ago

I think if you're going to be doing sufficiently 'biggish data' with those kind of retrieval charcteristics, you've got to just give up on disk and use flash only.

stream_fusion• 11 years ago

My experience playing around with KD trees is that they are super effective for multidimensional indexing (including spatial) and range search so long as the data is relatively static. The difficulty comes when trying to update and re-balance them dynamically, which is where other structures perform better.

joe_the_user4• 11 years ago

Oh Dear,

I was remembering my previous research wrong.

It's quad-trees and related Z-order based curves that give log(n) search and inserts.

With those, "everything" become log^n.

- Given that, my previous argument concerning log time for triangle/polygon search should stand.

http://en.wikipedia.org/wiki/Quadtree http://en.wikipedia.org/wiki/Z-order_curve

jandrewrogers8• 11 years ago

Author of that article here. Feel free to ask me questions about all things spatial (and beyond), I will attempt to answer them.

mohaps• 11 years ago

loved the article. I strongly believe that when doing geospatial indices, it is quite important to up front establish the nature and distribution of your data.

Searching for a generic/theoretically all-encompassing solution is quite akin to looking for the perfect pub-sub system for all workloads. :)

My comment was related to lat/lon indexed data clustered around cities. If you know beforehand that you're going to deal with such a dataset (static or dynamic), one can pragmatically decide on some sort of by-convention partitioning (e.g. Partitioning by continent/region which will bring it down to in-memory indices not needing continuous disk access).

I love the non-euclidean bit in the piece you wrote. Anyone who has tried to do a k-nearest neighbor query east of New Zealand will appreciate that bit. :D

jandrewrogers8• 11 years ago

If you have a priori knowledge of the data distribution, you can construct an ideal partitioning scheme. In practice, this runs into some significant problems:

- The average distribution of the data and the instantaneous distribution of the data can be very, very different. This means that some cells are overloaded while others are idle, and the whole system runs as slow as the overloaded cell. The canonical (and fairly benign) example is data following the sun.

- Many data sources have inherently unpredictable data distributions.

- Spatial joins across different data sources (say, weather and social media) require congruent partitioning or it won't scale. Unrelated data sources tend have unrelated data distributions, so this is a problem.

Making your partitions match your data distribution is good practice for static data layers. With some caveats, this can be modified for spatial joins across static data layers as well. For dynamic data sources, you run into issues with data and load skew at scale.

rcpt• 11 years ago

spatial data at rates of petabytes per day

I'm having trouble thinking up examples - can you provide some?

jandrewrogers8• 11 years ago

These tend to be the aggregate flow of pervasive sensor networks i.e. millions of machines generating this data autonomously. Collected personal location data alone is 6-10 PB/day globally, most of which is currently discarded because few people can handle it. Some are just incredibly high bandwidth platforms, which are more common in industrial and sensor settings. There are more than a couple operational environments today generating billions of records every second that must be stored (not summarized).

Some of the sexier petabyte-per-day sources include mobile phone telemetry, vehicle telemetry, and countless remote-sensing networks and platforms (of which there are far more than most people imagine). A petabyte per day is not that much data per entity, there are a lot of entities, and you can support this data rate in a single rack of commodity hardware.

A more typical generic IoT application at a large company is 1-100 TB/day, but that is quickly creeping upward as it becomes more cost effective to deploy sensors and store/analyze the data. And more often than not, they need to store weeks or months of that data so the overall data set size is still quite large.

spitfire• 11 years ago

Ship or aircraft tracking data.

Or if your the NSA, tracking mobile phones.

rch• 11 years ago

Think about the scale of agriculture in e.g. India, with network-capable farming equipment.

http://www.trimble.com/agriculture/

ChuckMcM3• 11 years ago

I enjoyed the article, and wondered what are the queries you support? Something like "SELECT * FROM world WHERE (distance_from_me < 500 meters);" ?

I ask because a lot of what you discuss seems to resonate with folks in the graphics business who are, for example, culling object geometry from a render scene by doing what is effectively the above operation. Its also what a 'whisper' or 'yik yak' type of App does trying to find people near itself although in that case the problem is greatly simplified by assuming a sphere and testing for containment in the sphere (or the circle if being planar)

saraid216• 11 years ago

You seem to be asking for this:

http://postgis.net/docs/ST_DWithin.html

jandrewrogers8• 11 years ago

You can do much more sophisticated operations than simple point-in-polygon queries.

The geospatial implementation in SpaceCurve is quite sophisticated and in some aspects the state-of-the-art. Complex geometry types and operators are obviously supported, and the implementation is fully geodetic and very high precision by default. Complex polygon constraints, aggregates, joins, intersections, etc on data models that also contain complex geometries are supported and massively parallelized. There is nothing else comparable for big data in this regard that I know of.

It is useful to understand that the entire platform, database engine on up, is fundamentally spatially organized even for plain old SQL "text and numbers" data. The SQL implementation is a thin layer that is translated into the underlying spatial algebra. You can use it for non-geospatial things, it just lends itself uniquely well to geospatial data models because it can properly represent complex spatial relationships at scale.

adamzochowski• 11 years ago

One GIS user/developer I spoke with mentioned a project they had: Find best place in town to build a mall.

This included information such as land elevation, floods areas, soil types, distances to roads and their importance (highway, major motorway, how many lanes), distance to facilities (electricity / gas / water / sewer), population demographics (wealth, buses) etc.

So beyond just measuring distances and polygon coverage, your GIS will have a lot of layers of data. Each layer either representing different data in itself, or just more detail. The query then is to find best matches knowing data, criteria, and rankings.

sopooneo• 11 years ago

Here's one I think is probably 101 level for others here, but what is the difference between a multidimensional scalar and a vector? I'll gratefully read through any reference you can link to.

nkurz• 11 years ago

Whether something is 101-level or a difficult thesis topic often depends on your point of view. Different fields seem to define scalars differently, with the physicists sometimes arguing that the mathematicians have got it all wrong: http://imechanica.org/node/15857

On a related note, I was tremendously impressed with the quality of discussion at imechanica.org. At a glance, it may be the best example of a well-functioning online community that I've ever seen.

fizx• 11 years ago

A vector belongs to a vector space, which implies certain algebraic rules relating it to other vectors in the space (http://en.wikipedia.org/wiki/Vector_space is probably enough reference). A multidimensional scalar is a more general data type, as any or all of the vector axioms can be relaxed or eliminated.

joe_the_user4• 11 years ago

Do you really think polygon intersection is inherently quadratic? It seems plausible to me that there are more efficient algorithms out there.

See my comment: https://news.ycombinator.com/item?id=9208066

me2i81• 11 years ago

The lower bound for computing the points of intersection is n log n + k for n line segments and k intersections, but obviously k can be n^2 in the worst case.

thinkt4nk• 11 years ago

You list hyperdimensional hashing as one of the early methods that you tried without success. While only good for point-to-point distance comparison in its simplest application, it seems that geohashes meet the scalar/vector problem that you describe. Do you have any experience with geohashes, and if so, what's your opinion of them?

daughart• 11 years ago

Interesting article, I'm very new to the field but I have an exciting application for GIS--I'm a biologist at Harvard and we have a new method to generate biological measurements at atomic scale inside biological specimens, and I believe the best way to store and analyze this data is using a GIS. Consider the example in your paper; "What are the optimal aircraft settings for my aircraft in this weather?” For our data, the questions are more like "What is the molecular spatial architecture of this tumor, and how can that inform treatment?" If this seems interesting to you it would be great to have a conversation about ways SpaceCurve could advance our project.

gumby• 11 years ago

This is an OK introduction to the issues of geospatial DBs (a meta meta article as it were) but two interesting (to me) points were made in passing:

Most software engineers assume today, as I did a decade ago, that the design of scalable geospatial databases is a straightforward task.

You could substitute almost any computing topic for "geospatial databases" and still (sadly) have a perfectly reasonable sentence. Partially that is because our field is so new, and partially it's by simple naïveté which is occasionally powerful but mostly dangerous.

Algorithms in computer science, with rare exception, leverage properties unique to one-dimensional scalar data models. In other words, data types you can abstractly represent as an integer.

Alas, this is painfully true, and the field of algorithms is so complex that the one-dimensional nature of our exploration is easy to overlook.

</grumble>

mbq• 11 years ago

Instead of Vincenty's, there is a very nice Meeus method for great circle distance, which has virtually identical accuracy and no loop inside; http://www.abecedarical.com/zenosamples/zs_great_circle_rout...

geophile3• 11 years ago

I'm not sure why the author is dismissing space-filling curves so quickly, just based on the age of the idea. I've worked with them extensively, in the context of spatial indexing in a database system, in both research and product settings. They address a number of problems described for interval data types. The techniques I've been working with "decompose" a spatial object into a number of regions by recursively partitioning the space, ending up with a small number of "z-values" for each. A z-value is represented by an integer, which is then used as a key in a conventional index, e.g. a sorted array, balanced binary tree, B-tree, skiplist, etc.

Getting a uniform distribution for sharding is easy in one dimension. I'm not sure what kind of scaling the author has in mind, but if you put the z-values in a B-tree, it scales exactly like a B-tree, i.e., extremely well. I agree there is no exploitable ordering of the spatial objects, but the trick is to order the z-values. If a given spatial object gives rise to 4 z-values, then they -- and the spatial object -- appear in 4 places in the ordering. That's fine. Run your search (in one dimension), get qualifying records, and then get rid of duplicates later.

jandrewrogers8• 11 years ago

The point was really that space-filling curve indexes do not solve the underlying issues with polygon indexing, their oldness was not a factor. That type of indexing is so old that the patents (yes, they were patented by the big database companies) have long since expired. And yet they are rarely used commercially. There is good reason for that. There is a resurgence in their usage by people new to spatial indexing but it is pretty obvious that few implementors are aware of the extent of the computer science, which goes back into the 1960s.

The assumption of size was "large-scale", which in this day and age usually means massively distributed. A B-tree is not a solution to that problem domain.

geophile3• 11 years ago

I'm still not sure what problems of polygon indexing are not solved by space-filling curves.

About commercial usage:

- Oracle uses R-trees now, I think. Before that, they had what I thought was a bad implementation of something sort of grid-like. Some notes I wrote from a few years ago on their "hh-encoded" index:

    Oracle 9 Spatial offered both R-tree and quadtree indexes 
    (http://download-uk.oracle.com/docs/cd/B10501_01/appdev.920/a96630/sdo_intro.htm#i877656). 
    The generation of index terms for a spatial object is called "tesselation". They have 
    two approaches to tesselation, 1) fixed-size tiles, in which the space is partitioned to 
    a fixed resolution, and covering cells give rise to index terms; 2) variable-size tiles, 
    in which spatial decomposition stops when a configurable number of tiles are generated for 
    the spatial object being indexed.

    Now here's where it gets strange. An Oracle quadtree index is either pure-fixed, or 
    it is hybrid. Hybrid is a fixed index AND a variable index. The docs recommend not 
    using hybrid. I could not find an explanation of why they even offer a hybrid option
    (as opposed to pure-variable).

    This Oracle 9 doc is from 2002. I also found a paper doing a performance comparison 
    of R-tree and fixed from around that time 
    (http://www.dpi.inpe.br/cursos/ser303/oracle_r_tree.pdf). This paper concludes 
    that R-trees are usually best, although they identify situations in which quadtrees win.

    Oracle 11 appears to have dropped quadtrees altogether
    (http://download.oracle.com/docs/cd/B28359_01/appdev.111/b28400/sdo_intro.htm#i877656).

    The pure variable-sized tile approach option was never offered in their product, 
    and not examined in the 2002 performance comparison. As that paper points out, 
    tuning fixed-size is tricky. If the tile size is too small, you get a large number 
    of index entries per spatial object. They take space, io bandwidth to read, 
    cpu time to process, etc. If the tile size is too large, you run the risk of 
    poor accuracy, retrieving more objects than necessary, again generating more io and 
    cpu. And if your data set has objects of various sizes, there is no single good size.

- Microsoft is less clear to me. From some of the tuning options on their spatial indexes, it sounds to me like a fixed-size tile approach, with tunable resolution. But I could be wrong, and I haven't looked into it in years.

- PostGIS uses R-trees. The problem with this approach is that it's a separate implementation from their main B-tree, so it always lags behind. With space-filling curves, you just use your B-tree and improvements to it then apply to your spatial indexes.

- MySQL also uses R-trees, and only in conjunction with MyISAM. So that's pretty bad.

- I know less about distributed spatial indexes, but I would think that space-filling curves are more amenable to distributed structures because they don't rely on a tree to organize the space. You can partition the 1-d space of z-values to load balance the shards.

geophile3• 11 years ago

The assumption of size was "large-scale", which in this day and age usually means massively distributed. A B-tree is not a solution to that problem domain.

Another thought on this one: Space-filling curves decomposes the problem nicely: Scale out your favorite, ordered key/value stored, and then layer spatial indexing on top. No need to develop a new data structure that both scales out and handles spatial data.

kyberias• 11 years ago

I'd love to hear some opinions (from the author?) on how well the current offering of major DBMS-vendors (eg. Microsoft, Oracle, ... ) handle geospatial data. How well do they scale and do they have some inherent limitations?

aristus2• 11 years ago

I respect the author's experience, but "Database Engines Cannot Handle Real-Time Geospatial" is probably not true. We (MemSQL) have developed geospatial on top of our existing skiplist indexes, and can deliver thousands of intersection queries per second, over billions of points, in milliseconds per query, on very modest hardware. If you want more performance, just add more hardware.

We previewed our geo code at the Esri Developer's Conference last week. The demo delivers queries in millisecond time over 170M records without any tuning. The naive version worked fine.

http://blog.memsql.com/geospatial-intelligence/

jandrewrogers8• 11 years ago

With all due respect, 170M points is a trivial data model, it fits on a thumb drive. That is seconds worth of data in IoT; you can brute-force the implementation and look great. Several well-known companies do. It just doesn't scale to anything real.

The location analytics data models I need to support, e.g. mobile telecom, have trillions of polygons. Indexing millions of records per second continuously concurrent with sub-second queries is pretty normal for IoT, and easy to support with good computer science. (Location is almost never described as a point by primary sources but as polygons; these are converted to centroid approximations for platforms incapable of doing analysis on the source.)

While I do not know the details of your implementation, I do know that indexing complex geometries using a skiplist index won't achieve the necessary volume or velocity required for IoT-like applications. If you restrict yourself to point data, people have been building extremely fast, extremely large quad-trees for years; you just can't scale high-value analytics with them, which limits their utility.

aristus2• 11 years ago

Fair enough; though I'm intrigued by the mention of trillions of polygons. How complex are they? 10 points? 100? 1000? What benefit does the raw data give that centroids can't?

vidarh2• 11 years ago

To illustrate how tiny 170M records is: I checked out the count of shapes from a side business of mine in a dataset supporting a couple of first nations in a single Canadian province. That adds up to 38 million shapes. These range from points to polygons consisting of millions of points per polygon. I don't have the patience to take out the full number of points, but it's certainly well in excess of 170M. More likely in the billions.

Consider that that's a dataset for organisations that have someone doing GIS part time a few hours a month, and that the above dataset is the type of dataset often manipulated in desktop GIS apps.

Also doing point intersections with polygons is about the lowest placement of the bar you could possibly do, and quite easy to optimise. E.g. you can scale that easily "naively" to arbitrary size by sharding the point data, and segmenting whatever polygon you want to intersect with.

A more realistic test of how well you're doing (and the type of queries typically run against the above mentioned dataset) would be full polygon to polygon intersections.

maxerickson• 11 years ago

What sorts of areas are being modeled with millions of points?

(I'm just curious and realize it may not be appropriate for you to answer, or that you might not want to take the time, or whatever, so please feel free to ignore)

tomjen3• 11 years ago

The article seems to lack even one good concrete example. All it came up with was a bunch of high level complaints.

Why Are Geospatial Databases So Hard to Build?

Related Stories