3 ms·

Try take a look at Spatial Sieve Tree (Inventor J. Andrew Rogers) https://patents.google.com/patent/US7734714B2/en https://patents.google.com/patent/US7734714B

Try take a look at Spatial Sieve Tree (Inventor J. Andrew Rogers) https://patents.google.com/patent/US7734714B2/en https://patents.google.com/patent/US7734714B2/en https://www.jandrewrogers.com/2015/03/02/geospatial-databases-are-hard/ https://www.jandrewrogers.com/2015/03/02/geospatial-database... https://www.jandrewrogers.com/2015/10/08/spacecurve/ https://www.jandrewrogers.com/2015/10/08/spacecurve/ These might give a hint at why cs101 might not be enough for the scale and kind of systems he is talking about.

jandrewrogers 6y ago
FWIW, that is completely obsolete at this point. :) It did solve one set of interesting problems very effectively but introduced some others. There has been dramatic improvements in both the theoretical and applied elegance over the years, partly just out of implementation experience. Back then, it was a bit of a “blind men and the elephant” case with some really interesting computer science constructs. Now we have a pretty pure theoretical model of the elephant, and so an elegant implementation is not the sum of what the blind men would have described. Much more capability, far fewer lines of code, albeit completely opaque to someone that doesn’t understand what they are looking at.
- electricshampo1 6y ago
  Naively it seems that ingestion for data of the form (space (longitude, latitude), time, DATA) is readily addressed by the ideas in that patent: - hierarchical partitioning of space, each node storing the data for the regions represented by a number of leaves. shard per leaf and adaptive rebalancing (merge,split, move shard) as necessary. - within each shard, partition by time With this you can gang together any number of nodes that you need to hit the aggregate ingestion rate requirement. The query "give me all the data that occurred in this region of space in this time period" is readily supported as well. Applications (shard aware or hitting some stub proxy aware of the sharding) sitting on top of this datastore can use this repeatedly to build arbitrary logic (though you would have to query all the nodes if you don't have a space region, which is fine if your query rate is low). Likely my mental model of applications consuming spatial data is too simple, but what other innovation would be required beyond this for ingestion and querying? What kind of interface does the datastore provide to the application? Would also love to hear more about the comment you made above "there are several more hard/interesting computer science problems related to topological types and conflict resolution that you'll likely need to solve before you have a useful system"
  - jandrewrogers 6y ago
    Scale and throughput have their own interesting problems. You have to think through the implications when you have billions of shards, dynamic rebalancing across servers, etc. Many common idioms stop working. Also, naive time handling doesn’t generalize well. Someone will eventually give you a data set that does violence to your assumptions about what such a data set looks like. Eventually, things you ordinarily assume you can cache in memory don’t actually fit in memory. It forces changes in the computer science strategy.

jandrewrogers 6y ago

FWIW, that is completely obsolete at this point. :) It did solve one set of interesting problems very effectively but introduced some others. There has been dramatic improvements in both the theoretical and applied elegance over the years, partly just out of implementation experience. Back then, it was a bit of a “blind men and the elephant” case with some really interesting computer science constructs. Now we have a pretty pure theoretical model of the elephant, and so an elegant implementation is not the sum of what the blind men would have described. Much more capability, far fewer lines of code, albeit completely opaque to someone that doesn’t understand what they are looking at.

electricshampo1 6y ago
Naively it seems that ingestion for data of the form (space (longitude, latitude), time, DATA) is readily addressed by the ideas in that patent: - hierarchical partitioning of space, each node storing the data for the regions represented by a number of leaves. shard per leaf and adaptive rebalancing (merge,split, move shard) as necessary. - within each shard, partition by time With this you can gang together any number of nodes that you need to hit the aggregate ingestion rate requirement. The query "give me all the data that occurred in this region of space in this time period" is readily supported as well. Applications (shard aware or hitting some stub proxy aware of the sharding) sitting on top of this datastore can use this repeatedly to build arbitrary logic (though you would have to query all the nodes if you don't have a space region, which is fine if your query rate is low). Likely my mental model of applications consuming spatial data is too simple, but what other innovation would be required beyond this for ingestion and querying? What kind of interface does the datastore provide to the application? Would also love to hear more about the comment you made above "there are several more hard/interesting computer science problems related to topological types and conflict resolution that you'll likely need to solve before you have a useful system"
- jandrewrogers 6y ago
  Scale and throughput have their own interesting problems. You have to think through the implications when you have billions of shards, dynamic rebalancing across servers, etc. Many common idioms stop working. Also, naive time handling doesn’t generalize well. Someone will eventually give you a data set that does violence to your assumptions about what such a data set looks like. Eventually, things you ordinarily assume you can cache in memory don’t actually fit in memory. It forces changes in the computer science strategy.