Hi, I just took a peek at the algorthm for the cost at https://github.com/neo4j/neo4j/blob/master/community/graph-algo/src/main/java/org/neo4j/graphalgo/impl/util/GeoEstimateEvaluator.java .
I did not double-check the maths, but this does not look like a distance function over a sphere. This looks like a 3D pythagoras, which means it does not fully take into account the curvature of the earth. But in principle, for most cases, it should work exactly like the 2D pythagoras that Angelo coded himself. The two main differences between Angelos code and the GeoEstimateEvaluator are: - GeoEstimateEvaluator does 3D instead of 2D. This will give better results if parts of the route are noticably closer to the poles than other parts (or some routes go closer to the poles than others). The 2D evaluator will underestimate the costs of routes closer to the poles. For most local routing, the difference should not matter. - GeoEstimateEvaluator converts the cost to meters. Angelo does not do anything with the units. I think this should not affect the algorithm in any way. One advantage of Angelo's version is that it does not matter what units are in the nodes. In GeoEstimateEvaluator it assumes that lat and lon are in decimal degrees. Some suggestions: - Double check the maths in GeoEstimateEvaluator. If this is giving strange results, it might be worth checking why. - Support alternative units (not everyone uses decimal degrees for location). I think we should not have code that makes assumptions about the units of properties like this. Or at least allow the user to set the units if they are not the expected defaults - Consider writing a better distance function that is not pythagoras, but rather distance of the surface of the sphere. This will allow for accurate calculations of much larger distances than the current code will. Regards, Craig On Tue, May 27, 2014 at 10:14 AM, Angelo Immediata <angelo...@gmail.com>wrote: > Hi Mattias, hi Michael > Thank you for answering me > > @Mattias: I was sure about what you wrote about relationships and > influence on algorithms, but now I'm confident that I was right :). But, on > the other side, now I'm totally confused on the reason why the AStar > algorithm has so poor performance (at least in my case); on Stackoverflow I > had a rapid chat with Stefan and he was surprised too about this poor > performance....and honestly I don't know what else to try to improve > performance (I posted a topic where you can find a sample project on github > and test what I tested) > @Michael: I know that BOTH direction is for querying and/or traverser...I > was wrong in writing :) > > > Angelo > Il giorno lunedì 19 maggio 2014 09:04:51 UTC+2, Angelo Immediata ha > scritto: > >> Hi there >> >> With my colleague, we are are buillding a route system by using neo4j >> 2.0.3; so we are suing A* and Dijkstra algorithms in order to calculate the >> shortest path, >> I was wondering if the relationships number can affect the algorithm >> perfomance. I mean, we have a graph with around 1 million (or more) of >> nodes and 50 million of relationships. We have several types of >> relationship; specifically we have: >> >> - relationships for cars: the most of relationships are of this type >> - relationships for bikes >> - relationships for pedestrian >> - relationships for public transports >> >> When we execute Dijkstra and/or A* we can specify, in our PathExpander, >> the type of the relationships we want to consider during the traverser, so, >> my sensation is that the relationships number should not affect algorithm >> performance since we will sparsely (almost never) consider all the >> relationships types. Am I right? >> >> Thak you >> Angelo >> > -- > You received this message because you are subscribed to the Google Groups > "Neo4j" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to neo4j+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Neo4j" group. To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
