Thanks and btw here's a public link to my dropbox heap dump file. http://dl.dropbox.com/u/20014383/java_pid590.hprof Hope this helps.Regards
> From: tobias.ivars...@neotechnology.com > Date: Mon, 31 Jan 2011 16:44:28 +0100 > To: user@lists.neo4j.org > Subject: Re: [Neo4j] Calculating shortest paths in a large graph > > Much better, I'll have a look at this tonight. > > -tobias > > On Mon, Jan 31, 2011 at 4:35 PM, Saikat Kanjilal <sxk1...@hotmail.com>wrote: > > > > > Tobias,I apologize, I am creating the zips on the command line and they > > appear to be flaky, I am attaching the database zip file again, can you take > > a look and let me know if this is ok. I will see if I can put the heap file > > on dropbox and send it across.Thanks in advance > > > > > From: tobias.ivars...@neotechnology.com > > > Date: Mon, 31 Jan 2011 16:26:33 +0100 > > > To: user@lists.neo4j.org > > > Subject: Re: [Neo4j] Calculating shortest paths in a large graph > > > > > > Since you have not sent a heap dump file (what you have sent is a stack > > > trace, and they aren't very useful on OOME), what I would need to do is > > to > > > recreate your database from your xml-file (the database zip you sent was > > > empty), and rerun your code on that to reproduce the problem. > > > > > > I have not had time to do that yet. > > > > > > If you could send the actual *.hprof-file that is written to the working > > > directory of the java process when the OutOfMemoryError occurs (if you've > > > started the jvm with -XX:+HeapDumpOnOutOfMemoryError) then I could > > analyze > > > this quicker. If the file is too large to send as an e-mail attachment > > > perhaps you could upload it to dropbox or similar. Otherwise I'll let you > > > know when I've had time to recreate your database and analyze the > > problem. > > > > > > -tobias > > > > > > On Mon, Jan 31, 2011 at 4:13 PM, Saikat Kanjilal <sxk1...@hotmail.com > > >wrote: > > > > > > > > > > > Tobias/Michael et al,I was wondering if you guys had a chance to do > > some > > > > more analysis on this heap space issue, I have sent you the zipped up > > > > contents of part of the heap dump file problem report, the graph > > directory > > > > and parts of the code. Additionally I am also sending the spring > > > > configuration files and the web services code zipped up in this email. > > > > Yesterday I increased the heap size to be really large and the process > > ran > > > > for about 10 minutes to calculate the shortest path without arriving at > > the > > > > answer. > > > > > > > > Let me know if I am missing something obvious.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 > > > > > > > > > > > > > > > > > -- > > > 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 > > > > > > > -- > 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
