4 ms·
Author of that article here. Feel free to ask me questions about all things spatial (and beyond), I will attempt to answer them.
by 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 agoloved 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 agoIf 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 agoThe 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.
- gcb0 12y agoreally? 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...
- rcpt 12y ago> spatial data at rates of petabytes per day I'm having trouble thinking up examples - can you provide some?
- jandrewrogers 12y agoThese 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.
- x0x0 12y agoHow 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.
- pas 12y agoI've a not really relevant answer, but Netflix has more than 1.2 billion time series ( http://techblog.netflix.com/2014/12/introducing-atlas-netflixs-primary.html 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).
- ChuckMcM 12y agoI 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 12y agoYou seem to be asking for this: http://postgis.net/docs/ST_DWithin.html http://postgis.net/docs/ST_DWithin.html
- ChuckMcM 12y agoI 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.
- jandrewrogers 12y agoYou 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.
- sopooneo 12y agoHere'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 12y agoWhether 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 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.
- GFK_of_xmaspast 12y agoIt looks like he's fumbling towards replacing the field with a (graded?) ring and therefore replacing vector spaces with modules.
- Potando 12y agoGreat 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. "
- fizx 12y agoA 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 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_user 12y agoDo 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 https://news.ycombinator.com/item?id=9208066
- me2i81 12y agoThe 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 12y agoYou 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 12y agoInteresting 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.