Massive matrix request, only compute small distances?

Dear ORS community,

as part of a Europe-wide (potentially including Asia in the long run) science project on reducing CO2-emissions, we need pairwise distances between each pair of 10^6 locations, so the matrix would have 10^12 entries. I have already set up a local ORS instance on my laptop (64 GB RAM, 6 cores) and am aware that this is completely infeasible. It takes more than 2 hours for 10 000 locations already. Therefore I want to work under the practical assumption, that distances between locations that are too far away from each other (bounded by straight line distance?) are irrelevant and do not change the outcome of our optimization. Does such a feature exist? Is there some trick to make this work? Otherwise, could I make this a feature request? How quickly would it be implemented?

I also considered implementing something like this in my code, but this might be a little complicated if I want to avoid doing 10^12 checks. I’d have to make assumptions about the locations (treat the distance as euclidean), maybe split them in squares to speed up computation. Then I’d have to make 10^6 bulk one-to-many requests, not sure how fast that would go?

Any ideas?

With great gratitude to everyone who contributed to ORS and alike,
Tobi & team

Hey,

no, such a feature does not exist, and I’m not sure whether we would implement something like this.

To speed up the 10^12 checks, you could use a spatial index to help with this, e.g. a quadtree.
If you’d like to collaborate with HeiGIT on your project, let us know at routing(at)heigit.org.

Best regards

1 Like