Neo4J path traversal: A* optimization

NEO4J PATH TRAVERSAL: A* OPTIMIZATION

06 MARCH 2018

-
-

Work. Vessel tracking with Neo4J hit a limit. Need to analyze 13,000 route -points; Dijkstra’s shortest path search slows after 4,000.

- -

Replaced Dijkstra’s algorithm with A* search using haversine function as -heuristic:

- -

private double computeHeuristic(
-    final double lat1, final double lon1,
-    final double lat2, final double lon2) {
-    final int earthRadius = 6371;
-    final double kmToNM = 0.539957;
-
-    final double latDistance = Math.toRadians(lat2 - lat1);
-    final double lonDistance = Math.toRadians(lon2 - lon1);
-
-    final double a = Math.sin(latDistance / 2) 
-        * Math.sin(latDistance / 2)
-        + Math.cos(Math.toRadians(lat1)) 
-        * Math.cos(Math.toRadians(lat2))
-        * Math.sin(lonDistance / 2) 
-        * Math.sin(lonDistance / 2);
-
-    final double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
-
-    return earthRadius * c * kmToNM;
-}
-

- -

Core search loop updates costs when better path found:

- -

private void updateCosts(
-    final int source, final int target,
-    final double newCost, final double heuristic) {
-    final double oldCost = gCosts.getOrDefault(target, Double.MAX_VALUE);
-    if (newCost < oldCost) {
-        gCosts.put(target, newCost);
-        fCosts.put(target, newCost + heuristic);
-        path.put(target, source);
-    }
-}
-

- -

300x speedup. Scaled to 13,000 route points.

- -

Upstreamed changes: Neo4J v3.4.0 | -Full -source

by W. D. Sadeep Madurange