diff options
| -rw-r--r-- | _log/neo4j-a-star-search.md | 23 |
1 files changed, 14 insertions, 9 deletions
diff --git a/_log/neo4j-a-star-search.md b/_log/neo4j-a-star-search.md index 017a33e..ad927e5 100644 --- a/_log/neo4j-a-star-search.md +++ b/_log/neo4j-a-star-search.md @@ -1,14 +1,19 @@ --- -title: 'Neo4J path traversal: A* optimization' +title: 'Neo4J search: A* optimization' date: 2018-03-06 layout: post --- -Work. Vessel tracking with Neo4J hit a limit. Need to analyze 13,000 route -points; Dijkstra's shortest path search slows after 4,000. +Written in 2026, backdated to 2018. -Replaced Dijkstra's algorithm with A* search using haversine function as -heuristic: +First real performance problem. Vessel tracking with Neo4J hit a wall. Need to +find shortest paths in a 13,000-vertex graph. Dijkstra's search, which Neo4J +ships with, slowed to a crawl after 4,000. + +Spent better part of the week replacing Dijkstra's algorithm with A* +search—Python shop, junior developer, took more than a day to set up toolchain +and build the project. Haversine function as heuristic uses distance between +ports as the crow flies to steer search: ``` private double computeHeuristic( @@ -47,10 +52,7 @@ private void updateCosts( } ``` -300x speedup. Scaled to 13,000 route points. - -Despite impressive speedup, performance horizon visible. Unlikely to scale past -16,000 points. +Verdict: 300x speedup—scaled to 13,000 vertices. Upstreamed changes: <a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" @@ -59,3 +61,6 @@ class="external" target="_blank" rel="noopener noreferrer">Neo4J v3.4.0</a> | href="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">Full source</a>. +NOTE: Despite impressive gain, performance horizon visible. Unlikely to scale past +16,000 vertices without caching. + |