I am attaching a tar file containing the db directory as well as the xml file used to load the initial data. Also since this runs as a webservice the data is loading first when the app starts up and then the algorithm runs each time a webservice call is made to calculate the shortest path.
Also I am using 64 bit jdk 1.6 on the mac with heap setting of -Xmx4096. I appreciate your help in troubleshooting this further.Regards > From: michael.hun...@neotechnology.com > Date: Sun, 30 Jan 2011 17:19:46 +0100 > To: user@lists.neo4j.org > Subject: Re: [Neo4j] Calculating shortest paths in a large graph > > You can also zip the graph database directory and send it to me or tobias. > > Do you run the algorithm just after the insertion of the data or in a > separate run? > > Thanks > > Michael > > Am 30.01.2011 um 16:44 schrieb Saikat Kanjilal: > > > > > Looks like the heap dump file didn't come across in my post, so here's the > > heap dump: > > > > > > > > > > > > > > > > > > java.lang.OutOfMemoryError: Java heap space > > at org.neo4j.kernel.impl.util.ArrayMap.put(ArrayMap.java:75) > > at > > org.neo4j.kernel.impl.nioneo.xa.ReadTransaction.relGetProperties(ReadTransaction.java:157) > > at > > org.neo4j.kernel.impl.nioneo.xa.NioNeoDbPersistenceSource$ReadOnlyResourceConnection.relLoadProperties(NioNeoDbPersistenceSource.java:255) > > at > > org.neo4j.kernel.impl.persistence.PersistenceManager.loadRelProperties(PersistenceManager.java:113) > > at > > org.neo4j.kernel.impl.core.NodeManager.loadProperties(NodeManager.java:638) > > at > > org.neo4j.kernel.impl.core.RelationshipImpl.loadProperties(RelationshipImpl.java:88) > > at > > org.neo4j.kernel.impl.core.Primitive.ensureFullProperties(Primitive.java:574) > > at org.neo4j.kernel.impl.core.Primitive.getProperty(Primitive.java:141) > > at > > org.neo4j.kernel.impl.core.RelationshipProxy.getProperty(RelationshipProxy.java:91) > > at > > org.neo4j.graphalgo.impl.util.DoubleEvaluator.getCost(DoubleEvaluator.java:39) > > at > > org.neo4j.graphalgo.impl.util.DoubleEvaluator.getCost(DoubleEvaluator.java:27) > > at > > org.neo4j.graphalgo.impl.path.Dijkstra$SelectorFactory.calculateValue(Dijkstra.java:101) > > at > > org.neo4j.graphalgo.impl.path.Dijkstra$SelectorFactory.calculateValue(Dijkstra.java:89) > > at > > org.neo4j.graphalgo.impl.util.BestFirstSelectorFactory$BestFirstSelector.next(BestFirstSelectorFactory.java:67) > > at > > org.neo4j.kernel.impl.traversal.TraverserImpl$TraverserIterator.fetchNextOrNull(TraverserImpl.java:128) > > at > > org.neo4j.kernel.impl.traversal.TraverserImpl$TraverserIterator.fetchNextOrNull(TraverserImpl.java:95) > > at > > org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:56) > > at > > org.neo4j.graphalgo.impl.util.StopAfterWeightIterator.fetchNextOrNull(StopAfterWeightIterator.java:46) > > at > > org.neo4j.graphalgo.impl.util.StopAfterWeightIterator.fetchNextOrNull(StopAfterWeightIterator.java:30) > > at > > org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:56) > > at > > org.neo4j.graphalgo.impl.path.Dijkstra.findSinglePath(Dijkstra.java:86) > > at > > org.neo4j.graphalgo.impl.path.Dijkstra.findSinglePath(Dijkstra.java:46) > > at > > com.hbc.locationservices.graph.GraphManager.findCheapestPathWithDijkstra(GraphManager.java:339) > > at > > com.hbc.locationservices.graph.GraphManager.getNodesInCheapestPath(GraphManager.java:413) > > at > > com.hbc.locationservices.graph.GraphManager$$FastClassByCGLIB$$167175c8.invoke(<generated>) > > at net.sf.cglib.proxy.MethodProxy.invoke(MethodProxy.java:149) > > at > > org.springframework.aop.framework.Cglib2AopProxy$CglibMethodInvocation.invokeJoinpoint(Cglib2AopProxy.java:688) > > at > > org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:150) > > at > > org.springframework.transaction.interceptor.TransactionInterceptor.invoke(TransactionInterceptor.java:110) > > at > > org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:172) > > at > > org.springframework.aop.framework.Cglib2AopProxy$DynamicAdvisedInterceptor.intercept(Cglib2AopProxy.java:621) > > at > > com.hbc.locationservices.graph.GraphManager$$EnhancerByCGLIB$$64354524.getNodesInCheapestPath(<generated>) > > > > > > > > Regards > > From: sxk1...@hotmail.com > > To: user@lists.neo4j.org > > Date: Sun, 30 Jan 2011 07:41:00 -0800 > > Subject: Re: [Neo4j] Calculating shortest paths in a large graph > > > > > > Hello Tobias,Thanks very much for your help, to be clear I want to find the > > path that has the least cost, in this case length is the determinator for > > doing this. The total number of nodes are roughly around a 100 but not > > much more. I am attaching my heap dump,my code for parsing the google > > earth data as well as the actual xml file I use to parse and load the data, > > managing the Graph and the relationships. > > My project does the following:1) Create a physical graph based on google > > earth with a set of nodes and paths2) Load the contents of the google earth > > file into neo4j using regular expressions to parse the xml3) Run the > > dijkstra algorithm on this graph > > > > > > Your help is much appreciated, let me know if there's anything else I can > > provide.Regards > > > >> From: tobias.ivars...@neotechnology.com > >> Date: Sun, 30 Jan 2011 16:22:42 +0100 > >> To: user@lists.neo4j.org > >> Subject: Re: [Neo4j] Calculating shortest paths in a large graph > >> > >> Hi Saikat, > >> > >> This was a strange one. > >> > >> Are you sure you only have 100 nodes? That is really tiny, and your title > >> said "large graph". How many relationships? > >> > >> I really cant see a way this could run into heap space issues, what does > >> your heap configuration look like? > >> > >> 1) Batch insertion will not help you, since you aren't inserting, you are > >> reading from the graph. > >> 2) Granted, Dijkstra isn't the best algorithm for finding the cheapest path > >> (that's what it finds, not shortest path), but with a small graph it should > >> still terminate quickly. > >> 3) Unless you are running this on a machine with only 8MB of RAM (or > >> something equally silly), hardware should not be your problem. > >> > >> If the specifications you've specified are in fact correct, and your graph > >> only contains 100 nodes, then could you please provide me with a heap dump > >> so that I can analyze where heap is being wasted, because OOM on such a > >> small graph would be a bug. > >> > >> To get a heap dump when the program throws OOME, provide the following > >> startup parameter to the JVM: > >> -XX:+HeapDumpOnOutOfMemoryError > >> You can send the resulting .hprof-file to me directly, the mailing list is > >> a > >> bit restrictive about attachments. > >> If the graph is larger, and the "100 nodes" part was a typo, then switching > >> algorithm might be a good solution, Dijkstra is not optimal for large > >> graphs. > >> > >> I'd love to help, but I need some more details, because this seems strange > >> to me. > >> Cheers, > >> Tobias > >> > >> On Sun, Jan 30, 2011 at 3:19 PM, Saikat Kanjilal > >> <sxk1...@hotmail.com>wrote: > >> > >>> > >>> Hi Folks,I'm working on a little route planning spring based neo4j service > >>> where I initially load up all my data into neo4j and have about a 100 > >>> nodes, however it seems that I am running into heap space issues when > >>> running the Dijkstra Algorithm for any traversals that are relatively far > >>> apart (i.e. opposite ends of the graph). I have tried to increase the > >>> heap > >>> space but that didn't seem to make a difference. Note that I am not > >>> currently using batch insertion and am using neo4j's transaction manager > >>> with spring with the @Transactional annotation to perform all > >>> transactions. > >>> I was wondering what the areas are that I can look at to get past this. > >>> The things that are coming to mind include: > >>> 1) Adding batch insertion2) Trying the other algorithms like AStar3) > >>> Running this on more powerful hardware > >>> > >>> Number 3 seems unlikely based on all I've read on neo4j and its > >>> performance > >>> characteristics. I can attach my code if needed but being a newbie to > >>> neo4j > >>> I wanted to understand what I'm missing conceptually that could be causing > >>> these issues. > >>> Best Regards > >>> > >>> > >>> > >>> _______________________________________________ > >>> Neo4j mailing list > >>> User@lists.neo4j.org > >>> https://lists.neo4j.org/mailman/listinfo/user > >>> > >> > >> > >> > >> -- > >> Tobias Ivarsson <tobias.ivars...@neotechnology.com> > >> Hacker, Neo Technology > >> www.neotechnology.com > >> Cellphone: +46 706 534857 > >> _______________________________________________ > >> Neo4j mailing list > >> User@lists.neo4j.org > >> https://lists.neo4j.org/mailman/listinfo/user > > > > > > _______________________________________________ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > > > _______________________________________________ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > _______________________________________________ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user
_______________________________________________ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
