6 ms·

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

by 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.
- maxerickson 12y 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)
  - vidarh 12y ago
    Several Canadian provinces have vast forest management areas with hugely intricate rights (e.g. Alberta have dozens of first nations, dozens of oil companies and dozens of forestry companies all with different rights to the same overlapping areas), and many of them have huge datasets that needs to be coordinated. E.g. years back when we started doing this app, I visited with one forest management company that were doing logging in an area the size of Ireland. Most of the polygons will be smaller, but there's any number of objects mapping out boundaries of massive areas to a ridiculous level of detail. More often the datasets will map out large number of moderate size (tens to thousands of points) polygons. Anything from buildings to traditional hunting trails, to oil and gas pipelines or mineral deposits. Many of the huge polygons could be simplified just fine without any noticeable loss of precision, but that's not always a choice anyone is willing to take responsibility for doing, and so the system needs to work on whatever overly detailed data is passed in - customer knows best and all that - (but often the right answer for indexing this kind of data is just that: Simplify the outlines however drastically works for your application, with the most extreme being simply the bounding box; intersect that, discard all the "misses", and do the expensive full intersect on what's left).

by aristus 12y ago

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.

maxerickson 12y 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)
- vidarh 12y ago
  Several Canadian provinces have vast forest management areas with hugely intricate rights (e.g. Alberta have dozens of first nations, dozens of oil companies and dozens of forestry companies all with different rights to the same overlapping areas), and many of them have huge datasets that needs to be coordinated. E.g. years back when we started doing this app, I visited with one forest management company that were doing logging in an area the size of Ireland. Most of the polygons will be smaller, but there's any number of objects mapping out boundaries of massive areas to a ridiculous level of detail. More often the datasets will map out large number of moderate size (tens to thousands of points) polygons. Anything from buildings to traditional hunting trails, to oil and gas pipelines or mineral deposits. Many of the huge polygons could be simplified just fine without any noticeable loss of precision, but that's not always a choice anyone is willing to take responsibility for doing, and so the system needs to work on whatever overly detailed data is passed in - customer knows best and all that - (but often the right answer for indexing this kind of data is just that: Simplify the outlines however drastically works for your application, with the most extreme being simply the bounding box; intersect that, discard all the "misses", and do the expensive full intersect on what's left).