Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Spatial Data Structures for Better Map Interactions

chairnerd.seatgeek.com

Post reply on HN
Print view View original

11–20 of 24 posts

Re: Spatial Data Structures for Better Map Interactions

#11

Post by jandrewrogers »

ryandrake wrote: post #3

Spatial data structures are great, and heavily used in all kinds of mapping applications. Most of the systems I've worked with used the more constrained quadtree structure, where the map is divided into uniformly-sized tiles, and a level-of-detail hierarchy is built. This is good for raster data, where each tile is a picture and the whole world is covered by tiles. The R-tree has great advantages when the complexity…

The spatial data structure literature is quite incomplete, and there is a lot of confusion about what to use when. Many of the issues with spatial indexing performance at companies I go into is that they are doing it wrong, not that they necessarily have a fundamental problem.

It should be pointed out that R-family data structures should only be used for data sets that are (1) small and (2) relatively static. They scale very poorly in a number of ways. The primary reason they are used in databases is that they can handle interval (i.e. non-point) spatial data types without the possibility of pathological space complexity (bad when talking about databases) and fit B-tree indexing models adequately, which that software understands.

Quad-tree variants can scale well for point data types but are often terrible for indexing non-point data types due to pathological space complexity.

Grid-file variants are the canonical structure for large-scale spatial data sets if the data is static. However, the number of companies implementing these correctly at scale is approximately zero in my experience.

For general, scalable, online/dynamic spatial indexing structures, there is another family of algorithms and data structures (adaptive spatial sieves) that are basically ignored in the literature even though they were first described in 1990, albeit in a not very useful form at the time. If you are doing petabyte-scale real-time indexing of polygons at extremely high rates, this is what you would use but little is published about them because most modern variants did not come out of academia.

And the most advanced algorithm family for indexing point-like data is not in the literature at all.

(Background: my day job involves extreme-scale, high-performance spatial indexing software and I invented a few spatial indexing algorithms back in the day that are still the state-of-the-art in their respective algorithm families.)

Re: Spatial Data Structures for Better Map Interactions

#13

Post by kaib »

jandrewrogers wrote: post #11
ryandrake wrote: post #3

Spatial data structures are great, and heavily used in all kinds of mapping applications. Most of the systems I've worked with used the more constrained quadtree structure, where the map is divided into uniformly-sized tiles, and a level-of-detail hierarchy is built. This is good for raster data, where each tile is a picture and the whole world is covered by tiles. The R-tree has great advantages when the complexity…

The spatial data structure literature is quite incomplete, and there is a lot of confusion about what to use when. Many of the issues with spatial indexing performance at companies I go into is that they are doing it wrong, not that they necessarily have a fundamental problem. It should be pointed out that R-family data structures should only be used for data sets that are (1) small and (2) relatively static. They sc…

> And the most advanced algorithm family for indexing point-like data is not in the literature at all.

Don't leave us comp geom geeks hanging.. Which one are you referring to? :-)

Re: Spatial Data Structures for Better Map Interactions

#14

Post by rdtsc »

jandrewrogers wrote: post #11
ryandrake wrote: post #3

Spatial data structures are great, and heavily used in all kinds of mapping applications. Most of the systems I've worked with used the more constrained quadtree structure, where the map is divided into uniformly-sized tiles, and a level-of-detail hierarchy is built. This is good for raster data, where each tile is a picture and the whole world is covered by tiles. The R-tree has great advantages when the complexity…

The spatial data structure literature is quite incomplete, and there is a lot of confusion about what to use when. Many of the issues with spatial indexing performance at companies I go into is that they are doing it wrong, not that they necessarily have a fundamental problem. It should be pointed out that R-family data structures should only be used for data sets that are (1) small and (2) relatively static. They sc…

> And the most advanced algorithm family for indexing point-like data is not in the literature at all.

So what is it? Is it patented, secret(classified)?

And how do you know it is the most advanced without a peer review?

BTW "adaptive spatial sieves" on Google search produces exactly 0 results. Is there another name for it.

Spatial indexing is interesting and complex but not exactly rocket science, there have been a good number of people thinking about. It is hard to believe there are general approaches there that haven't been thought of yet. But again, but I am not an expert, so I could be wrong.

Can you write some more about it, I am very curious.

Re: Spatial Data Structures for Better Map Interactions

#15

Post by willholley »

ryandrake wrote: post #3

Spatial data structures are great, and heavily used in all kinds of mapping applications. Most of the systems I've worked with used the more constrained quadtree structure, where the map is divided into uniformly-sized tiles, and a level-of-detail hierarchy is built. This is good for raster data, where each tile is a picture and the whole world is covered by tiles. The R-tree has great advantages when the complexity…

shameless plug: Cloudant Geo (https://cloudant.com/product/cloudant-features/geospatial/) uses a sharded R*-Tree for big geospatial data.

Re: Spatial Data Structures for Better Map Interactions

#16

Post by ehsanu1 »

rdtsc wrote: post #14
jandrewrogers wrote: post #11

Earlier quoted context omitted.

The spatial data structure literature is quite incomplete, and there is a lot of confusion about what to use when. Many of the issues with spatial indexing performance at companies I go into is that they are doing it wrong, not that they necessarily have a fundamental problem. It should be pointed out that R-family data structures should only be used for data sets that are (1) small and (2) relatively static. They sc…

> And the most advanced algorithm family for indexing point-like data is not in the literature at all. So what is it? Is it patented, secret(classified)? And how do you know it is the most advanced without a peer review? BTW "adaptive spatial sieves" on Google search produces exactly 0 results. Is there another name for it. Spatial indexing is interesting and complex but not exactly rocket science, there have been a…

Googling for it without forcing a phrase match returns some limited results. Here's a patent for a "Spatial Sieve Tree", which is apparently invented by the parent, jandrewrogers: http://www.google.st/patents/US7734714

Re: Spatial Data Structures for Better Map Interactions

#17

Post by aw3c2 »

ehsanu1 wrote: post #16
rdtsc wrote: post #14

Earlier quoted context omitted.

> And the most advanced algorithm family for indexing point-like data is not in the literature at all. So what is it? Is it patented, secret(classified)? And how do you know it is the most advanced without a peer review? BTW "adaptive spatial sieves" on Google search produces exactly 0 results. Is there another name for it. Spatial indexing is interesting and complex but not exactly rocket science, there have been a…

Googling for it without forcing a phrase match returns some limited results. Here's a patent for a "Spatial Sieve Tree", which is apparently invented by the parent, jandrewrogers: http://www.google.st/patents/US7734714

In that case I am glad it is not covered in literature. Patenting algorithms is bad.

Re: Spatial Data Structures for Better Map Interactions

#18

Post by jandrewrogers »

rdtsc wrote: post #14
jandrewrogers wrote: post #11

Earlier quoted context omitted.

The spatial data structure literature is quite incomplete, and there is a lot of confusion about what to use when. Many of the issues with spatial indexing performance at companies I go into is that they are doing it wrong, not that they necessarily have a fundamental problem. It should be pointed out that R-family data structures should only be used for data sets that are (1) small and (2) relatively static. They sc…

> And the most advanced algorithm family for indexing point-like data is not in the literature at all. So what is it? Is it patented, secret(classified)? And how do you know it is the most advanced without a peer review? BTW "adaptive spatial sieves" on Google search produces exactly 0 results. Is there another name for it. Spatial indexing is interesting and complex but not exactly rocket science, there have been a…

What makes spatial indexing different than other areas of computer science is that its fundamental operands are interval types (like hypercubes). Almost all other areas of computer science focus on solutions that only work on point-like data and so many idioms and intuitions computer scientists use are not actually valid when dealing with spatial representations. Data types that require no less than two integers to describe break the assumptions of computer science developed for data types that require one integer to describe.

Oddly, there are almost no people working on the computer science of spatial representations and indexing. That was how I became involved in the first place; I needed solutions to specific problems for which no active research was being done in academia (and I was talking to people like Samet at the time). And to this day, academics still aren't doing any interesting work on spatial structures.

The algorithms are not classified, just not published. There are a couple patents out there on spatial sieves -- I am the inventor on the first practical one -- but more sophisticated and advanced variants exist that will probably never be patented. Widmayer (respected CS academic) was the first to propose this approach to the problem of generalized interval indexing but a useful algorithm was not discovered until my work in 2007.

The point indexing algorithm family I mentioned has never been patented or published anywhere but was based on the development of a novel theoretical CS construct that allows the expression of polymorphic space-filling curves. These are essentially adaptive to the information theoretic properties of the high-dimensionality data set but still embarrassingly parallel and distributable. I don't think these are being used in production anywhere (yet) but they've been around for several years. Very cool but the number of people that grok them can be counted on one hand.

All modern research on computing with spatial representations is being done at one of a few companies, which is why nothing is published. People like me, and I haven't done the pure research in years, don't have time to generate hundreds of pages of fairly deep content. Consequently, learning advanced spatial indexing is fairly prohibitive; you have to figure it out yourself, which is far from easy, or be at one of the handful of places where they are using it.

Re: Spatial Data Structures for Better Map Interactions

#19

Post by jandrewrogers »

ehsanu1 wrote: post #16
rdtsc wrote: post #14

Earlier quoted context omitted.

> And the most advanced algorithm family for indexing point-like data is not in the literature at all. So what is it? Is it patented, secret(classified)? And how do you know it is the most advanced without a peer review? BTW "adaptive spatial sieves" on Google search produces exactly 0 results. Is there another name for it. Spatial indexing is interesting and complex but not exactly rocket science, there have been a…

Googling for it without forcing a phrase match returns some limited results. Here's a patent for a "Spatial Sieve Tree", which is apparently invented by the parent, jandrewrogers: http://www.google.st/patents/US7734714

Yep, that was the first practical spatial sieve (previous variants had pathological spatial skew sensitivity). Most people that use them use more sophisticated variants. Even with that version, which is simple, many implementors do not understand the technical subtleties well enough to produce a non-broken implementation.

Re: Spatial Data Structures for Better Map Interactions

#20

Post by kastnerkyle »

jandrewrogers wrote: post #18
rdtsc wrote: post #14

Earlier quoted context omitted.

> And the most advanced algorithm family for indexing point-like data is not in the literature at all. So what is it? Is it patented, secret(classified)? And how do you know it is the most advanced without a peer review? BTW "adaptive spatial sieves" on Google search produces exactly 0 results. Is there another name for it. Spatial indexing is interesting and complex but not exactly rocket science, there have been a…

What makes spatial indexing different than other areas of computer science is that its fundamental operands are interval types (like hypercubes). Almost all other areas of computer science focus on solutions that only work on point-like data and so many idioms and intuitions computer scientists use are not actually valid when dealing with spatial representations. Data types that require no less than two integers to d…

I found some related papers for others who are interested:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56....

http://bmi.osu.edu/resources/techreports/ahmedBokhariV21.pdf

Also a book:

Space-Filling Curves: An Introduction with Applications in Scientific Computing

by

Michael Bader

Post reply on HN