Системы гео роутинга и нахождения кратчайшего расстояния?

Question

[roadhump]

Необходима система для нахождения подробного кратчайшего пути между гео-точками.


Критерии: точность и скорость с учетом, что рассчитывать придется по всей Евразии.


Смотрю в сторону pgRouting, однако скорость пока не устраивает — 10 секунд между Москвой и Магаданом. Возможно потому как еще не особенно смотрел на возможность оптимизации базы.


В идеале хотелось бы нечто, сравнимого по скорости с роутингом от Cloudmade.


Собственно варианты видятся пока такие:

• оптимизация базы, вынос в «облако»
  
• поиск другого инструмента или сервиса (вышеупомянутый Cloudmade не устраивает в силу достаточно большой интенсивности и специфичности запросов)
  
• реализация собственного (чем черт не шутит) инструмента с использованием оптимального и быстрого алгоритма расчета (отсюда вопрос — какого)
  

Есть ли у хабрасообщества советы и опыт решения подобных задач?

Answer 1

[tzlom]

выносите в облако, делайте по схеме map-reduce и делите нагрузку между серверами
т.е. вам понадобится много уточняющих графов, и какой нибудь весовой алгоритм для выбора с какого графа следует начать поиск