From 48b2bc137d274b386b8d12fc6e7bf303c8ce8a14 Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Thu, 19 Feb 2026 22:15:04 +0800 Subject: Minor improvements to neo4j post. --- _log/neo4j-a-star-search.md | 23 ++++++++++++++--------- 1 file 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: Neo4J v3.4.0 | 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. +NOTE: Despite impressive gain, performance horizon visible. Unlikely to scale past +16,000 vertices without caching. + -- cgit v1.2.3