9 ms·

Why Are Geospatial Databases So Hard to Build?

183 points by chippy 12y ago

ericfrenkiel 12y ago
A great article, and very true as MemSQL (w2011) just announced its own real-time Geospatial capabilities: http://blog.memsql.com/geospatial-intelligence/ http://blog.memsql.com/geospatial-intelligence/
nigwil_ 12y 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 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 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.
- jandrewrogers 12y 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_user 12y 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 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 http://en.wikipedia.org/wiki/Space_partitioning
- falcolas 12y 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 12y ago
jandrewrogers 12y 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 12y 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
  - jandrewrogers 12y 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.
    - gcb0 12y ago
      The sun is pretty predictable... everyone who built any online service know the access pattern is a wave with time of day. do you mean to say you've seen people trying to shard a geodb by latitude instead of longitude? ... that would be a very sloppy initial research.
gumby 12y 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 12y 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_route.html http://www.abecedarical.com/zenosamples/zs_great_circle_rout...
geophile 12y 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.
- jandrewrogers 12y 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.
  - geophile 12y 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.
kyberias 12y 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?
- deleted 12y ago
  [deleted]
ddd1600 12y ago
They're not.
aristus 12y 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/ http://blog.memsql.com/geospatial-intelligence/
- jandrewrogers 12y 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.
  - aristus 12y 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?
- vidarh 12y 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.
tomjen3 12y ago
The article seems to lack even one good concrete example. All it came up with was a bunch of high level complaints.

183 points by chippy 12y ago

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

nigwil_ 12y 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 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 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.

jandrewrogers 12y 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_user 12y 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 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 http://en.wikipedia.org/wiki/Space_partitioning

falcolas 12y 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 12y ago

jandrewrogers 12y 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 12y 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
- jandrewrogers 12y 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.
  - gcb0 12y ago
    The sun is pretty predictable... everyone who built any online service know the access pattern is a wave with time of day. do you mean to say you've seen people trying to shard a geodb by latitude instead of longitude? ... that would be a very sloppy initial research.

gumby 12y 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 12y 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_route.html http://www.abecedarical.com/zenosamples/zs_great_circle_rout...

geophile 12y 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.

jandrewrogers 12y 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.
- geophile 12y 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.

kyberias 12y 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?

deleted 12y ago
[deleted]

ddd1600 12y ago

They're not.

aristus 12y 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/ http://blog.memsql.com/geospatial-intelligence/

jandrewrogers 12y 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.
- aristus 12y 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?
vidarh 12y 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.

tomjen3 12y ago

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