3 ms·

Would you be willing to expand a bit more on the hard problems and their relation to spatial computing?

jandrewrogers 6y ago
The elementary operations for spatial computing are a mixture of complex constraint/event processing and ad hoc graph search, frequently on data models with types that are not representable as an integer and therefore lack the characteristic properties of integers like order and trivial partitioning. Three of the above are notoriously difficult to scale individually. For spatial computing we need to scale all three simultaneously in a single computational construct. And if that wasn't enough, these are real-time systems that need to support extremely high write throughput while all of those operations are happening -- offline batch reorganization isn't an option. These are petabyte scale systems in the trivial case (tens of TB in the most minimalist data models), so you aren't going to be building a bunch of indexes or similar. It is a vexing computer science and architecture problem. And even if you solved that elementary computing infrastructure problem, 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. It is headaches all the way down.
- prox 6y ago
  Is this is a solution looking for a problem? As you mention something as such in your first comment? Personally I don’t see a need to this “maximizing efficiency” paradigm for spatial computing, which seems to be mostly driven by industry (the potential for making billions of dollars) not as an inborn desire to better this world. It’s not that I decline it, but the need seems somewhat artificial in a way.
  - birdyrooster 6y ago
    Needing new data structures? What would that even look like to create a generic data structure which was specifically useful to spatial computing? Why not use existing data structures and algorithms as has been done already?
    - electricshampo1 6y ago
      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
    Ignore the applications for spatial computing in the article, industry already has a very long list of concrete applications that they are trying to operationalize today. The real use cases aren't as sexy as the articles but they are incredibly valuable and utilitarian. The problem already exists at scale today in many, many companies that everyone has heard of. Mitigating and working around this has been a large part of what I do for many years. If such a platform came into existence today, dozens of companies would each happily spend tens of millions per year to use it tomorrow; they are all ready lighting similar amounts of money on fire in this area on infrastructure that doesn't work. The business challenge is that the engineering effort required to build such a platform is simply too large to easily fund, even inside large tech companies. There is no appetite for that scale of investment in infrastructure software anymore, everyone kind of waits around for something to show up in open source that they can re-purpose. Less risk and less cost. In this particular case, that is unlikely to happen for the foreseeable future, someone will need to make a real investment.
    - rsp1984 6y ago
      You might be missing the forest for the trees. Digital twins are already used today. 3D Scanning adoption is growing quickly across a whole range of industries. Billions of dollars change hands for AR/VR products and experiences. Also, on the technology side, there's tons that can be done on the edge these days. Those petabytes of data you mention can be crunched down to mere gigabytes before reaching the cloud. Adoption of spatial computing will not be binary "once someone pulls it off". It's going to be gradually, step after step.
      - mlyle 6y ago
        > Digital twins are already used today. 3D Scanning adoption is growing quickly across a whole range of industries. You might be considering a lot broader things to be spatial computing that are short of the sense being considered here. Yes, representing objects and annotating trivial scenes is interesting and is starting to happen today. But free-form automated representation of the environment in ways that the spatial shortcuts we rely upon ("inside", "on top of", etc) can be used, (non-graph) paths of different types can be solved, and actuator kinematics can find and interact with things, etc: it's really hard. AR and VR and being able to interact with object meshes and geometry is a start. But computational geometry and encoding world constraints in a useful way is really hard. We'll snatch some incremental parts from AR and vision research, but we'll need some breakthroughs in the space, too, to do the really cool stuff.
ml_thoughts 6y ago
A problem that I was surprised to not be solved well is the study of paths (not represented as graphs). It seems that for example trying to cluster trajectories over time through real coordinates has a bit of prior work (there’s a bit of an unintuitive and costly metric called the Frechet distance that can be used) but is not the solved problem I would have expected for this type of fundamental problem (that would seem to come up a lot for human movement applications). Like answering the question of “what are the most commonly used paths to get to work” without resorting to discretizing steps into nodes on a graph seems tricky as far as I can tell.

The elementary operations for spatial computing are a mixture of complex constraint/event processing and ad hoc graph search, frequently on data models with types that are not representable as an integer and therefore lack the characteristic properties of integers like order and trivial partitioning. Three of the above are notoriously difficult to scale individually. For spatial computing we need to scale all three simultaneously in a single computational construct. And if that wasn't enough, these are real-time systems that need to support extremely high write throughput while all of those operations are happening -- offline batch reorganization isn't an option. These are petabyte scale systems in the trivial case (tens of TB in the most minimalist data models), so you aren't going to be building a bunch of indexes or similar. It is a vexing computer science and architecture problem. And even if you solved that elementary computing infrastructure problem, 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. It is headaches all the way down.

prox 6y ago
Is this is a solution looking for a problem? As you mention something as such in your first comment? Personally I don’t see a need to this “maximizing efficiency” paradigm for spatial computing, which seems to be mostly driven by industry (the potential for making billions of dollars) not as an inborn desire to better this world. It’s not that I decline it, but the need seems somewhat artificial in a way.
- birdyrooster 6y ago
  Needing new data structures? What would that even look like to create a generic data structure which was specifically useful to spatial computing? Why not use existing data structures and algorithms as has been done already?
  - electricshampo1 6y ago
    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
  Ignore the applications for spatial computing in the article, industry already has a very long list of concrete applications that they are trying to operationalize today. The real use cases aren't as sexy as the articles but they are incredibly valuable and utilitarian. The problem already exists at scale today in many, many companies that everyone has heard of. Mitigating and working around this has been a large part of what I do for many years. If such a platform came into existence today, dozens of companies would each happily spend tens of millions per year to use it tomorrow; they are all ready lighting similar amounts of money on fire in this area on infrastructure that doesn't work. The business challenge is that the engineering effort required to build such a platform is simply too large to easily fund, even inside large tech companies. There is no appetite for that scale of investment in infrastructure software anymore, everyone kind of waits around for something to show up in open source that they can re-purpose. Less risk and less cost. In this particular case, that is unlikely to happen for the foreseeable future, someone will need to make a real investment.
  - rsp1984 6y ago
    You might be missing the forest for the trees. Digital twins are already used today. 3D Scanning adoption is growing quickly across a whole range of industries. Billions of dollars change hands for AR/VR products and experiences. Also, on the technology side, there's tons that can be done on the edge these days. Those petabytes of data you mention can be crunched down to mere gigabytes before reaching the cloud. Adoption of spatial computing will not be binary "once someone pulls it off". It's going to be gradually, step after step.
    - mlyle 6y ago
      > Digital twins are already used today. 3D Scanning adoption is growing quickly across a whole range of industries. You might be considering a lot broader things to be spatial computing that are short of the sense being considered here. Yes, representing objects and annotating trivial scenes is interesting and is starting to happen today. But free-form automated representation of the environment in ways that the spatial shortcuts we rely upon ("inside", "on top of", etc) can be used, (non-graph) paths of different types can be solved, and actuator kinematics can find and interact with things, etc: it's really hard. AR and VR and being able to interact with object meshes and geometry is a start. But computational geometry and encoding world constraints in a useful way is really hard. We'll snatch some incremental parts from AR and vision research, but we'll need some breakthroughs in the space, too, to do the really cool stuff.

ml_thoughts 6y ago

A problem that I was surprised to not be solved well is the study of paths (not represented as graphs). It seems that for example trying to cluster trajectories over time through real coordinates has a bit of prior work (there’s a bit of an unintuitive and costly metric called the Frechet distance that can be used) but is not the solved problem I would have expected for this type of fundamental problem (that would seem to come up a lot for human movement applications). Like answering the question of “what are the most commonly used paths to get to work” without resorting to discretizing steps into nodes on a graph seems tricky as far as I can tell.