There are a handful of bottlenecks and a number of ways to decompose this problem. To get started on subproblems, one of us (Ethan) is working on a list of suggestions, which we will backlink here.
@eca, did you end up writing this list?
@eca, did you end up writing this list?