diff options
Diffstat (limited to '_site/log/neo4j-a-star-search')
| -rw-r--r-- | _site/log/neo4j-a-star-search/index.html | 106 |
1 files changed, 0 insertions, 106 deletions
diff --git a/_site/log/neo4j-a-star-search/index.html b/_site/log/neo4j-a-star-search/index.html deleted file mode 100644 index 2063d68..0000000 --- a/_site/log/neo4j-a-star-search/index.html +++ /dev/null @@ -1,106 +0,0 @@ -<!DOCTYPE html> -<html> - <head> - <meta charset="utf-8"> - <meta name="viewport" content="width=device-width, initial-scale=1"> - <title>Neo4J path traversal: A* optimization</title> - <link rel="stylesheet" href="/assets/css/main.css"> - <link rel="stylesheet" href="/assets/css/skeleton.css"> -</head> - - - <body> - - <div id="nav-container" class="container"> - <ul id="navlist" class="left"> - - <li > - <a href="/" class="link-decor-none">hme</a> - </li> - <li > - <a href="/projects/" class="link-decor-none">poc</a> - </li> - <li > - <a href="/about/" class="link-decor-none">abt</a> - </li> - <li> - <a href="/cgi-bin/find.cgi" class="link-decor-none">lup</a> - </li> - <li> - <a href="/feed.xml" class="link-decor-none">rss</a> - </li> - </ul> -</div> - - - - <main> - <div class="container"> - <div class="container-2"> - <h2 class="center" id="title">NEO4J PATH TRAVERSAL: A* OPTIMIZATION</h2> - <h5 class="center">06 MARCH 2018</h5> - <br> - <div class="twocol justify"><p>Work. Vessel tracking with Neo4J hit a limit. Need to analyze 13,000 route -points; Dijkstra’s shortest path search slows after 4,000.</p> - -<p>Replaced Dijkstra’s algorithm with A* search using haversine function as -heuristic:</p> - -<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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; -} -</code></pre></div></div> - -<p>Core search loop updates costs when better path found:</p> - -<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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); - } -} -</code></pre></div></div> - -<p>300x speedup. Scaled to 13,000 route points.</p> - -<p>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> | -<a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/blob/bd9732d9a690319552e134708692acb5a0d6b37c/algo/src/main/java/org/neo4j/graphalgo/impl/ShortestPathAStar.java">Full -source</a></p> -</div> - <p class="post-author right">by W. D. Sadeep Madurange</p> - </div> - </div> - </main> - - <div class="footer"> - <div class="container"> - <div class="twelve columns right container-2"> - <p id="footer-text">© ASCIIMX - 2026</p> - </div> - </div> -</div> - - - </body> -</html> |