diff options
Diffstat (limited to '_log/neo4j-a-star-search.md')
| -rw-r--r-- | _log/neo4j-a-star-search.md | 19 |
1 files changed, 10 insertions, 9 deletions
diff --git a/_log/neo4j-a-star-search.md b/_log/neo4j-a-star-search.md index 3233428..fe6f33f 100644 --- a/_log/neo4j-a-star-search.md +++ b/_log/neo4j-a-star-search.md @@ -4,13 +4,11 @@ date: 2018-03-06 layout: post --- -Replaced Dijkstra's search for vessel route tracking in Neo4J. +Work project. Marine vessel tracking with Neo4J hit a limit. Need to store +13,000 route points; Dijkstra's shortest path search slows after 4,000. -Tracking 13,000 marine vessel route points. Needed shortest paths between ports -for arrival prediction. Neo4j's Dijkstra's algorithm slows after 4,000 route -points. - -Implemented A* search using haversine function as heuristic: +Replaced Dijkstra's algorithm with A* search using haversine function as +heuristic: ``` private double computeHeuristic( @@ -50,7 +48,10 @@ private void updateCosts( } ``` -Outcome: 300x speedup. Scaled to 13,000 route points. Upstreamed changes. <a +Outcome: 300x speedup. Scaled to 13,000 route points. + +Upstreamed changes: <a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" -class="external" target="_blank" rel="noopener noreferrer">Neo4J v3.4.0</a>. -[Full source](https://github.com/neo4j-contrib/neo4j-graph-algorithms/blob/bd9732d9a690319552e134708692acb5a0d6b37c/algo/src/main/java/org/neo4j/graphalgo/impl/ShortestPathAStar.java) +class="external" target="_blank" rel="noopener noreferrer">Neo4J v3.4.0</a> | +[Full +source](https://github.com/neo4j-contrib/neo4j-graph-algorithms/blob/bd9732d9a690319552e134708692acb5a0d6b37c/algo/src/main/java/org/neo4j/graphalgo/impl/ShortestPathAStar.java) |