From eb6497e805627137e15bf30d3ec46fb510103f56 Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Sun, 2 Nov 2025 14:31:47 +0800 Subject: neo4J post. --- _archive/neo4j-a-star-search.md | 48 +++++++++++++++------------- _site/archive/neo4j-a-star-search/index.html | 46 +++++++++++++------------- _site/feed.xml | 2 +- _site/posts.xml | 2 +- 4 files changed, 51 insertions(+), 47 deletions(-) diff --git a/_archive/neo4j-a-star-search.md b/_archive/neo4j-a-star-search.md index ac2f35d..aae34b9 100644 --- a/_archive/neo4j-a-star-search.md +++ b/_archive/neo4j-a-star-search.md @@ -9,10 +9,26 @@ Back in 2018, we used the Neo4J graph database to track the movement of marine vessels. We were interested in the shortest path a ship could take through a network of about 13,000 route points. -Performance issues with Neo4J’s then-available shortest-path algorithms limited -our search to about 4,000 route points. +Performance issues with Neo4J’s shortest-path algorithms limited our search to +about 4,000 route points. -The fix led to my first contribution to an open-source project: +A graph is a finite set of vertices, and a subset of vertex pairs known as +edges. Edges can have weights. + +In the case of vessel tracking, the route points can be modeled as a graph +with the distances between them as weights. For different reasons, people are +interested in minimizing (or maximizing) the weight of a path through a set of +vertices. For instance, we may want to find the shortest path between two +ports. + +Dijkstra's algorithm is one such algorithm that finds the shortest path between +two vertices. The one drawback of this algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex. + +The following enhancement, also known as the A* search, employs spherical +distance between route points (which are on the earth's surface) as a heuristic +to steer the search in the direction of the destination far more quickly: ``` package org.neo4j.graphalgo.impl; @@ -291,26 +307,12 @@ public class ShortestPathAStar extends Algorithm { } } ``` +The heuristic function is domain-specific. If chosen wisely, it can +significantly speed up the search. In our case, we achieved a 300x speedup, +enabling us to expand our search from 4,000 to 13,000 route points. -If you are new to them, a graph is a finite set of vertices (such as ports -ships are known to travel through), and a subset of vertex pairs (such as -origin and destination ports) known as edges. - -Edges can have weights. In the case of ships and ports, the weights could be -the distances between ports. For various reasons, people are interested in -minimizing or maximizing the weight of a path through a set of vertices. For -instance, we may want to find the shortest path between two ports. - -There's nothing spectacular about the code. It is, for the most part, a patch -over Dijkstra's algorithm that employs spherical distance between vertices as a -heuristic to steer the search in the right direction. Dijkstra's algorithm, on -the other hand, explores all possible paths from the source, which is what -makes it slower. - -The heuristic function is domain-specific. I planned to make it configurable, -but didn't get around to it. With the help of my A* algorithm, we scaled our -search to include all the route points of interest. Here's a link to -the now-archived official release. +class="external" target="_blank" rel="noopener noreferrer">v3.4 shipped +with my implementation of the A* search algorithm. diff --git a/_site/archive/neo4j-a-star-search/index.html b/_site/archive/neo4j-a-star-search/index.html index f37d00b..92d350d 100644 --- a/_site/archive/neo4j-a-star-search/index.html +++ b/_site/archive/neo4j-a-star-search/index.html @@ -46,10 +46,26 @@

Back in 2018, we used the Neo4J graph database to track the movement of marine vessels. We were interested in the shortest path a ship could take through a network of about 13,000 route points. -Performance issues with Neo4J’s then-available shortest-path algorithms limited -our search to about 4,000 route points.

+Performance issues with Neo4J’s shortest-path algorithms limited our search to +about 4,000 route points.

-

The fix led to my first contribution to an open-source project:

+

A graph is a finite set of vertices, and a subset of vertex pairs known as +edges. Edges can have weights.

+ +

In the case of vessel tracking, the route points can be modeled as a graph +with the distances between them as weights. For different reasons, people are +interested in minimizing (or maximizing) the weight of a path through a set of +vertices. For instance, we may want to find the shortest path between two +ports.

+ +

Dijkstra’s algorithm is one such algorithm that finds the shortest path between +two vertices. The one drawback of this algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex.

+ +

The following enhancement, also known as the A* search, employs spherical +distance between route points (which are on the earth’s surface) as a heuristic +to steer the search in the direction of the destination far more quickly:

package org.neo4j.graphalgo.impl;
 
@@ -327,26 +343,12 @@ public class ShortestPathAStar extends Algorithm<ShortestPathAStar> {
     }
 }
+

The heuristic function is domain-specific. If chosen wisely, it can +significantly speed up the search. In our case, we achieved a 300x speedup, +enabling us to expand our search from 4,000 to 13,000 route points.

-

If you are new to them, a graph is a finite set of vertices (such as ports -ships are known to travel through), and a subset of vertex pairs (such as -origin and destination ports) known as edges.

- -

Edges can have weights. In the case of ships and ports, the weights could be -the distances between ports. For various reasons, people are interested in -minimizing or maximizing the weight of a path through a set of vertices. For -instance, we may want to find the shortest path between two ports.

- -

There’s nothing spectacular about the code. It is, for the most part, a patch -over Dijkstra’s algorithm that employs spherical distance between vertices as a -heuristic to steer the search in the right direction. Dijkstra’s algorithm, on -the other hand, explores all possible paths from the source, which is what -makes it slower.

- -

The heuristic function is domain-specific. I planned to make it configurable, -but didn’t get around to it. With the help of my A* algorithm, we scaled our -search to include all the route points of interest. Here’s a link to -the now-archived official release.

+

The Neo4J graph algorithms open-source project v3.4 shipped +with my implementation of the A* search algorithm.

by Wickramage Don Sadeep Madurange

diff --git a/_site/feed.xml b/_site/feed.xml index 3548f7c..9abcade 100644 --- a/_site/feed.xml +++ b/_site/feed.xml @@ -1 +1 @@ -Jekyll2025-11-02T11:45:12+08:00/feed.xmlASCIIMX | ArchiveWickramage Don Sadeep MadurangeNeo4J A* search2025-09-14T00:00:00+08:002025-09-14T00:00:00+08:00/archive/neo4j-a-star-searchWickramage Don Sadeep MadurangeMy first PCB2025-07-14T00:00:00+08:002025-07-14T00:00:00+08:00/archive/my-first-pcbWickramage Don Sadeep MadurangeMOSFETs2025-06-22T00:00:00+08:002025-06-22T00:00:00+08:00/archive/mosfet-switchesWickramage Don Sadeep MadurangeAwesome books2025-04-20T00:00:00+08:002025-04-20T00:00:00+08:00/archive/awesome-booksWickramage Don Sadeep MadurangeProgramming ATmega328P chips2025-04-10T00:00:00+08:002025-04-10T00:00:00+08:00/archive/arduino-unoWickramage Don Sadeep MadurangeBare-metal ARM Cortex M3 chips2024-10-05T00:00:00+08:002024-10-05T00:00:00+08:00/archive/arduino-dueWickramage Don Sadeep Madurange \ No newline at end of file +Jekyll2025-11-02T14:31:35+08:00/feed.xmlASCIIMX | ArchiveWickramage Don Sadeep MadurangeNeo4J A* search2025-09-14T00:00:00+08:002025-09-14T00:00:00+08:00/archive/neo4j-a-star-searchWickramage Don Sadeep MadurangeMy first PCB2025-07-14T00:00:00+08:002025-07-14T00:00:00+08:00/archive/my-first-pcbWickramage Don Sadeep MadurangeMOSFETs2025-06-22T00:00:00+08:002025-06-22T00:00:00+08:00/archive/mosfet-switchesWickramage Don Sadeep MadurangeAwesome books2025-04-20T00:00:00+08:002025-04-20T00:00:00+08:00/archive/awesome-booksWickramage Don Sadeep MadurangeProgramming ATmega328P chips2025-04-10T00:00:00+08:002025-04-10T00:00:00+08:00/archive/arduino-unoWickramage Don Sadeep MadurangeBare-metal ARM Cortex M3 chips2024-10-05T00:00:00+08:002024-10-05T00:00:00+08:00/archive/arduino-dueWickramage Don Sadeep Madurange \ No newline at end of file diff --git a/_site/posts.xml b/_site/posts.xml index 1ecb22e..cef4242 100644 --- a/_site/posts.xml +++ b/_site/posts.xml @@ -1 +1 @@ -Jekyll2025-11-02T11:45:12+08:00/posts.xmlASCIIMXWickramage Don Sadeep Madurange \ No newline at end of file +Jekyll2025-11-02T14:31:35+08:00/posts.xmlASCIIMXWickramage Don Sadeep Madurange \ No newline at end of file -- cgit v1.2.3