News for hackers. Stuff that matters.
Re:Why Are Geospatial Databases So Hard to Build? by jandrewrogers on Sunday March 15, 2015 @05:10PM (#9208140)
Author of that article here. Feel free to ask me questions about all things spatial (and beyond), I will attempt to answer them.
Re:Why Are Geospatial Databases So Hard to Build? by ChuckMcM on Sunday March 15, 2015 @07:11PM (#9208632)
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)

Re:Why Are Geospatial Databases So Hard to Build? by jandrewrogers on Sunday March 15, 2015 @09:03PM (#9209048)
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.

Re:Why Are Geospatial Databases So Hard to Build? by ChuckMcM on Sunday March 15, 2015 @09:10PM (#9209086)
Great, I was actually wondering if you have like an API manual online somewhere? It sounds like it is more than just a performant PostGIS (no disrespect in that, PostGIS is quite slow) but beyond the basic stuff near here, how is the spatial algebra expressed from the client to the underlying database?
Re:Why Are Geospatial Databases So Hard to Build? by mrec on Monday March 16, 2015 @10:18AM (#9211525)
Graphics will tend to want 3D spatial queries, though, and this gives the impression of being optimized for, if not restricted to, 2D or 2D-plus-curvature. The article consistently talks about "polygons" as opposed to "polytopes", for example.

Have I got the wrong impression?

Re:Why Are Geospatial Databases So Hard to Build? by jandrewrogers on Monday March 16, 2015 @12:59PM (#9212645)
The geospatial implementation is a true 3-space model. You can content-address objects and features past low-earth orbit by default. All surfaces upon which geometries are constructed are embedded in this space. Polygons relative to an embedded surface, such as a geodetic 2-ellipsoid, are actually represented as 3-space shapes under the hood; the 2-surface is a convenience for popular use cases but the data is not organized that way.

There are an unbounded number of possible shapes and surfaces in 3-space. Storing and content-addressing them is easy enough. The challenge is that to be useful you need, at a minimum, generally correct intersection algorithms for all of the representable shapes. It is an open-ended computational geometry problem and we continuously extend geometry capabilities as needed. Currently, the most complex shapes can be constructed relative to a number of well-behaved mathematical surfaces embedded in 3-space. Shapes directly constructible in 3-space are significantly more limited but I expect that to expand over time as well, particularly if there are specific requirements and use cases.

The underlying representation was intended to mirror the spatiotemporal organization of the physical world at a data level. We can generate projections but the data lives in 3-space.

Re:Why Are Geospatial Databases So Hard to Build? by adamzochowski on Monday March 16, 2015 @12:11PM (#9212274)
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.

Re:Why Are Geospatial Databases So Hard to Build? by saraid216 on Sunday March 15, 2015 @08:46PM (#9208963)
You seem to be asking for this:

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

Re:Why Are Geospatial Databases So Hard to Build? by ChuckMcM on Sunday March 15, 2015 @09:08PM (#9209075)
I am aware of PostGIS, the author specifically said PostGIS was unable to keep up. I was wondering about the types of operations that SpaceCurve could do, and keep up, that PostGIS cannot.
Re:Why Are Geospatial Databases So Hard to Build? by sopooneo on Sunday March 15, 2015 @08:44PM (#9208955)
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.
Re:Why Are Geospatial Databases So Hard to Build? by nkurz on Sunday March 15, 2015 @09:14PM (#9209104)
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.

Re:Why Are Geospatial Databases So Hard to Build? by Potando on Monday March 16, 2015 @12:42AM (#9209909)
Great part: "They should not call the elements in the number field F scalars. These elements already have names: they are called numbers. And we physicists and engineers need the word scalar to name some other objects. Mathematicians, like physicians, should at least learn to do no harm. "
Re:Why Are Geospatial Databases So Hard to Build? by GFK_of_xmaspast on Sunday March 15, 2015 @10:17PM (#9209374)
It looks like he's fumbling towards replacing the field with a (graded?) ring and therefore replacing vector spaces with modules.
Re:Why Are Geospatial Databases So Hard to Build? by fizx on Sunday March 15, 2015 @09:49PM (#9209254)
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.
Re:Why Are Geospatial Databases So Hard to Build? by rcpt on Sunday March 15, 2015 @05:34PM (#9208253)
> spatial data at rates of petabytes per day

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

Re:Why Are Geospatial Databases So Hard to Build? by jandrewrogers on Sunday March 15, 2015 @06:03PM (#9208376)
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.

Re:Why Are Geospatial Databases So Hard to Build? by x0x0 on Sunday March 15, 2015 @08:27PM (#9208899)
How many companies have million sized sensor networks? I guess few. And even at eg 400k records per second with an average record size of 1k, you'll generate ~ 30 TB per day. I just can't imagine there are many situations with more data incoming.

Can you share company names or more concrete examples?

Even ups only delivers 17M packages / day.

edit: also, which industries customarily have thousand vertex polygons? Thanks for the interesting blog post.

Re:Why Are Geospatial Databases So Hard to Build? by pas on Sunday March 15, 2015 @11:47PM (#9209718)
I've a not really relevant answer, but Netflix has more than 1.2 billion time series ( http://techblog.netflix.com/2014/12/introducing-atlas-netfli... ), which they update about every 5 sec. Though I don't know how much they store for how long.

The interesting time series are heavy machinery telemetry feeds (for example a Rolls Royce jet engine has its own communications subsystem to phone home to a RR engineering station via satellite, which however, likely makes it low-bandwidth).

Re:Why Are Geospatial Databases So Hard to Build? by pjc50 on Monday March 16, 2015 @11:50AM (#9212123)
Collected personal location data alone is 6-10 PB/day globally, most of which is currently discarded because few people can handle it

Knowing where everyone is at all times; the ultimate enabler for weaponised harrasment.

Re:Why Are Geospatial Databases So Hard to Build? by rch on Sunday March 15, 2015 @11:41PM (#9209696)
Think about the scale of agriculture in e.g. India, with network-capable farming equipment.

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

Re:Why Are Geospatial Databases So Hard to Build? by spitfire on Sunday March 15, 2015 @08:43PM (#9208951)
Ship or aircraft tracking data.

Or if your the NSA, tracking mobile phones.

Re:Why Are Geospatial Databases So Hard to Build? by thinkt4nk on Monday March 16, 2015 @09:42AM (#9211335)
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?
Re:Why Are Geospatial Databases So Hard to Build? by mohaps on Sunday March 15, 2015 @05:25PM (#9208213)
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

Re:Why Are Geospatial Databases So Hard to Build? by jandrewrogers on Sunday March 15, 2015 @06:34PM (#9208495)
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.

Re:Why Are Geospatial Databases So Hard to Build? by gcb0 on Monday March 16, 2015 @04:57AM (#9210465)
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.

Re:Why Are Geospatial Databases So Hard to Build? by gcb0 on Tuesday March 17, 2015 @03:55PM (#9220883)
really? i got downvoted because i find it hard to imagine that people don't know that their systems will get more requests for the area that is day-time?

or i guess the sun is not predictable? sigh...

Re:Why Are Geospatial Databases So Hard to Build? by daughart on Monday March 16, 2015 @02:56PM (#9213484)
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.
Re:Why Are Geospatial Databases So Hard to Build? by joe_the_user on Sunday March 15, 2015 @09:25PM (#9209160)
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

Re:Why Are Geospatial Databases So Hard to Build? by me2i81 on Monday March 16, 2015 @12:05AM (#9209783)
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.