<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7652.24">
<TITLE>RE: [postgis-devel] More Cascade Union Adventures</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<P><FONT SIZE=2>Martin,<BR>
<BR>
Ok just tried in OJ and its 3 seconds for me too and 10 seconds with PostGIS ST_CascadeUnion (although postgis is on a separate server so I'll have to do another test later),<BR>
ST_Union is 99,703 ms. I'm not sure why the 30,000 is performing so poorly for me in OJ then. Maybe its my memory settings.<BR>
<BR>
Wish I could find that other set I was trying, but don't have connection to that server at the moment. <BR>
<BR>
Anyrate I did recall trying the US State bounds and for some reason I ran out of heap space in OJ, but it did complete within a minute with the ST_CascadeUnion. I'll have to find where I have that. I think that would be a good test.<BR>
<BR>
So I guess it looks like we are back to the 3 to 1 mark. Drats. I bow to the Doctor.<BR>
<BR>
Thanks,<BR>
Regina<BR>
<BR>
<BR>
<BR>
-----Original Message-----<BR>
From: postgis-devel-bounces@postgis.refractions.net on behalf of Martin Davis<BR>
Sent: Wed 8/13/2008 7:10 PM<BR>
To: PostGIS Development Discussion<BR>
Subject: Re: [postgis-devel] More Cascade Union Adventures<BR>
<BR>
Ok...<BR>
<BR>
I just tried the dataset you sent in OJ and JTS. They were both<BR>
basically the same - 3 secs.<BR>
<BR>
Obe, Regina wrote:<BR>
><BR>
> Hmm that doesn't look like the right dataset. Now I have to figure<BR>
> out where I dug up this other towns layer. Running on this particular<BR>
> layer ST_CascadeUnion runs in<BR>
> 10 secs. Regular ST_Union takes 99,703 ms.<BR>
><BR>
> I'll let you know when I find it. I have too many places where I have<BR>
> servers and all have slightly different datasets with the same name.<BR>
><BR>
><BR>
><BR>
> -----Original Message-----<BR>
> From: postgis-devel-bounces@postgis.refractions.net on behalf of Obe,<BR>
> Regina<BR>
> Sent: Wed 8/13/2008 6:40 PM<BR>
> To: PostGIS Development Discussion<BR>
> Subject: RE: [postgis-devel] More Cascade Union Adventures<BR>
><BR>
> Sure - its just the one on the MassGIS site<BR>
><BR>
> <A HREF="ftp://data.massgis.state.ma.us/pub/shape/state/towns.exe">ftp://data.massgis.state.ma.us/pub/shape/state/towns.exe</A><BR>
><BR>
> Shucks - I guess that means I don't win a prize huh :(<BR>
><BR>
> Thanks,<BR>
> Regina<BR>
><BR>
> -----Original Message-----<BR>
> From: postgis-devel-bounces@postgis.refractions.net on behalf of<BR>
> Martin Davis<BR>
> Sent: Wed 8/13/2008 6:40 PM<BR>
> To: PostGIS Development Discussion<BR>
> Subject: Re: [postgis-devel] More Cascade Union Adventures<BR>
><BR>
> I'm pretty sure that OJ is *not* calling CascadeUnion, but is using a<BR>
> special-purpose, similar algorithm developed by Michael Michaud. I<BR>
> just looked at the OJ src code to confirm, and this looks to be the<BR>
> situation. I think he tested his code against the JTS CascadedUnion and<BR>
> decided that the JTS algorithm is still faster.<BR>
><BR>
> I just tried the OJ Union as well as the JTS CascadedUnion on the<BR>
> 32278-feature dataset. Results were:<BR>
><BR>
> OJ Union: 27 sec<BR>
> JTS CascUnion: 17.7 sec<BR>
><BR>
> So JTS still wins, but they're not too far apart.<BR>
><BR>
> Just for grins, can you send me your Mass towns dataset to try?<BR>
><BR>
> Obe, Regina wrote:<BR>
> ><BR>
> > Martin,<BR>
> ><BR>
> > Just loaded that plugin - unless I put it in the wrong folder. - it<BR>
> > just seemed to create an option called aggregation-options under<BR>
> > plugins which seems to require two layers and does union, count<BR>
> > between the 2 layers. So nope doesn't sound like Cascaded union and<BR>
> > didn't seem to change anything with the union function.<BR>
> ><BR>
> > If OpenJump union function isn't doing cascaded union, then what is<BR>
> > that count down thing for. Doing the 30,000 it displays something<BR>
> > like this<BR>
> ><BR>
> > Computing Union<BR>
> > 1/8 (32,278)<BR>
> > 2/8 (8070)<BR>
> > 3/8 ... /2018<BR>
> > 86/505<BR>
> > 1/127<BR>
> > 6/8 (2/32)<BR>
> > 8/8 (2/3)<BR>
> > 3/3 (8/8)<BR>
> ><BR>
> > I also thought its speed of unioning of Mass towns was pretty<BR>
> impressive.<BR>
> ><BR>
> > Thanks,<BR>
> > Regina<BR>
> > -----Original Message-----<BR>
> > From: postgis-devel-bounces@postgis.refractions.net on behalf of Obe,<BR>
> > Regina<BR>
> > Sent: Wed 8/13/2008 5:40 PM<BR>
> > To: PostGIS Development Discussion<BR>
> > Subject: RE: [postgis-devel] More Cascade Union Adventures<BR>
> ><BR>
> > I assumed it was since it was counting down like in some sort of<BR>
> > upside down pyramid<BR>
> ><BR>
> > 500<BR>
> > 255<BR>
> > 10<BR>
> > :<BR>
> > :<BR>
> ><BR>
> > So it seemed like it was doing some sort of division of the<BR>
> > geometries. I'll give the below<BR>
> > a try. Maybe I misunderstood what that counting was for.<BR>
> ><BR>
> ><BR>
> ><BR>
> > -----Original Message-----<BR>
> > From: postgis-devel-bounces@postgis.refractions.net on behalf of<BR>
> > Martin Davis<BR>
> > Sent: Wed 8/13/2008 4:49 PM<BR>
> > To: PostGIS Development Discussion<BR>
> > Subject: Re: [postgis-devel] More Cascade Union Adventures<BR>
> ><BR>
> > Yep, I don't Hausdorff distance is available in very many places. Pity,<BR>
> > because it is a very useful metric for comparing geometry. The full<BR>
> > Hausdorff distance is quite challenging to implement, but I have made a<BR>
> > VertexHausdorffDistance approximation which is just as useful in most<BR>
> > situations, and is a lot simpler to implement (and faster to run).<BR>
> ><BR>
> > By the way, are you sure that OpenJUMP is using CascadedUnion? AFAIK it<BR>
> > didn't in the past... Michael Michaud has just released (today!) an<BR>
> > extension which I think does use CascadedUnion - so you might want to<BR>
> > try that.<BR>
> ><BR>
> > <A HREF="http://geo.michaelm.free.fr/OpenJUMP/resources/aggregation-0.1.jar">http://geo.michaelm.free.fr/OpenJUMP/resources/aggregation-0.1.jar</A><BR>
> ><BR>
> > When I did the original testing with the 30K polygon dataset that you're<BR>
> > using, I was getting times of around 20 sec using CascadedUnion...<BR>
> ><BR>
> ><BR>
> ><BR>
> > Obe, Regina wrote:<BR>
> > ><BR>
> > > Martin,<BR>
> > > Pardon my ignorance.<BR>
> > ><BR>
> > > I don't see a Hausdorff distance in OpenJump or maybe it goes by a<BR>
> > > more verbose name and the descriptions I read about Hausdorff<BR>
> > > distances are greek to me.<BR>
> > ><BR>
> > > Well the Mass town test seems to pass my trivial test exercises. It<BR>
> > > looks like massachusetts with no visually apparent gaps, has the same<BR>
> > > number points in all cases, similar area<BR>
> > ><BR>
> > > both num points - 476026<BR>
> > > both num geometries - 694<BR>
> > > area (ST_CascadeUnion - 2.094208570266725E10)<BR>
> > > area (JTS - 2.0942085702666965E10)<BR>
> > ><BR>
> > ><BR>
> > > -----Original Message-----<BR>
> > > From: postgis-devel-bounces@postgis.refractions.net on behalf of<BR>
> > > Martin Davis<BR>
> > > Sent: Wed 8/13/2008 11:51 AM<BR>
> > > To: PostGIS Development Discussion<BR>
> > > Subject: Re: [postgis-devel] More Cascade Union Adventures<BR>
> > ><BR>
> > > I wouldn't expect to have the results be exactly equal - the union<BR>
> code<BR>
> > > is likely to be input-order dependent.<BR>
> > ><BR>
> > > And the difference in areas doesn't seem surprising either - it's way<BR>
> > > down in the small decimal places, which would occur even with slight<BR>
> > > differences in the geometry.<BR>
> > ><BR>
> > > A more revealing test would be to compute the Hausdorff distance<BR>
> between<BR>
> > > the union boundaries - that would show if they differed by very much,<BR>
> > > and where. PostGIS doesn't have this - I can't remember whether<BR>
> > > OpenJUMP does or not. JEQL has this operation, too.<BR>
> > ><BR>
> > > Obe, Regina wrote:<BR>
> > > > Now testing all including JTS 1.9.0 (OpenJump) on a Win XP runing<BR>
> > > > PostgreSQL 8.3.1, PostGIS 1.3.3, Geos 3.0.0. It appears using array<BR>
> > > > trumps all, Cascade aggregate union is a vast improvement over<BR>
> > ST_Union<BR>
> > > > (ST_Union I didn't bother testing of course because it owuld never<BR>
> > > > finish on this test), but evidentally the array accum calls give a<BR>
> > major<BR>
> > > > penalty.<BR>
> > > ><BR>
> > > > I found some things I found a bit possibly disturbing. Maybe<BR>
> its just<BR>
> > > > the nature of unioning in different orders. I compared all 3<BR>
> outputs<BR>
> > > > and none of them are binary equal or even ST_Equals for that matter.<BR>
> > > ><BR>
> > > > However all 3 give same basic stats using OpenJump - e.g<BR>
> > > > All result in = 32972 pts <BR>
> > > > components = 10<BR>
> > > > lengths and areas are off by a bit<BR>
> > > > length = agg cascade union = 17.262684721407624, k nested union =<BR>
> > > > 17.262684721407688,<BR>
> > > > jts = 17.262684721406348<BR>
> > > ><BR>
> > > > Should I be bothered by any of these or are they just rounding<BR>
> errors?<BR>
> > > ><BR>
> > > > --Other odd thing is that the array approach is not as good as it<BR>
> > was on<BR>
> > > > my other machine bu the aggregate union performs better. I'll just<BR>
> > > > chuck this off to different postgresql version, and memory settings.<BR>
> > > ><BR>
> > > > Thanks,<BR>
> > > > Regina<BR>
> > > ><BR>
> > > ><BR>
> > > > -- 209,563 | 198,391 ms - SELECT 198391/1000.00/60 = 3.31 minutes<BR>
> > > ><BR>
> > > > SELECT ST_CascadeUnion(the_geom)<BR>
> > > > FROM (SELECT the_geom FROM sample_poly) As foo;<BR>
> > > ><BR>
> > > > -- 48,594 ms | 47,688 ms = 48 secs<BR>
> > > > SELECT st_unitecascade_garray_sort(ARRAY(SELECT the_geom FROM<BR>
> > > > sample_poly));<BR>
> > > ><BR>
> > > > -- 74,515 ms | 74,922 ms = SELECT 74515/1000.00/60 = 1.24 minutes<BR>
> > > > SELECT ST_Union(the_geom) AS the_geom, 'nested union'<BR>
> > > > FROM (<BR>
> > > > SELECT min(id) AS id, ST_Union(the_geom) AS the_geom<BR>
> > > > FROM (<BR>
> > > > SELECT min(id) AS id, ST_Union(the_geom) AS the_geom<BR>
> > > > FROM (<BR>
> > > > SELECT min(id) AS id, ST_Union(the_geom) AS the_geom<BR>
> > > > FROM (<BR>
> > > > SELECT min(id) AS id, ST_Union(the_geom) AS the_geom<BR>
> > > > FROM (SELECT the_geom, id FROM sample_poly) As foo<BR>
> > > > GROUP BY round(id/10)<BR>
> > > > ORDER BY id) AS tmp1<BR>
> > > > GROUP BY round(id/100)<BR>
> > > > ORDER BY id) AS tmp2<BR>
> > > > GROUP BY round(id/1000)<BR>
> > > > ORDER BY id) AS tmp3<BR>
> > > > GROUP BY round(id/10000)<BR>
> > > > ORDER BY id) AS tmp4<BR>
> > > > GROUP BY round(id/100000);<BR>
> > > ><BR>
> > > ><BR>
> > > > -- Open Jump JTS 1.9.0 Win XP<BR>
> > > > --After loading running union across the whole set<BR>
> > > > --1.14 minutes<BR>
> > > > --Loading database query<BR>
> > > > SELECT ST_AsBinary(the_geom)<BR>
> > > > FROM sample_poly;<BR>
> > > ><BR>
> > > > -----------------------------------------<BR>
> > > > The substance of this message, including any attachments, may be<BR>
> > > > confidential, legally privileged and/or exempt from disclosure<BR>
> > > > pursuant to Massachusetts law. It is intended<BR>
> > > > solely for the addressee. If you received this in error, please<BR>
> > > > contact the sender and delete the material from any computer.<BR>
> > > ><BR>
> > > > _______________________________________________<BR>
> > > > postgis-devel mailing list<BR>
> > > > postgis-devel@postgis.refractions.net<BR>
> > > > <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
> > > ><BR>
> > > ><BR>
> > ><BR>
> > > --<BR>
> > > Martin Davis<BR>
> > > Senior Technical Architect<BR>
> > > Refractions Research, Inc.<BR>
> > > (250) 383-3022<BR>
> > ><BR>
> > > _______________________________________________<BR>
> > > postgis-devel mailing list<BR>
> > > postgis-devel@postgis.refractions.net<BR>
> > > <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
> > ><BR>
> > ><BR>
> > ><BR>
> > ><BR>
> ------------------------------------------------------------------------<BR>
> > ><BR>
> > > _______________________________________________<BR>
> > > postgis-devel mailing list<BR>
> > > postgis-devel@postgis.refractions.net<BR>
> > > <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
> > ><BR>
> ><BR>
> > --<BR>
> > Martin Davis<BR>
> > Senior Technical Architect<BR>
> > Refractions Research, Inc.<BR>
> > (250) 383-3022<BR>
> ><BR>
> > _______________________________________________<BR>
> > postgis-devel mailing list<BR>
> > postgis-devel@postgis.refractions.net<BR>
> > <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
> ><BR>
> ><BR>
> > ------------------------------------------------------------------------<BR>
> ><BR>
> > _______________________________________________<BR>
> > postgis-devel mailing list<BR>
> > postgis-devel@postgis.refractions.net<BR>
> > <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
> > <BR>
><BR>
> --<BR>
> Martin Davis<BR>
> Senior Technical Architect<BR>
> Refractions Research, Inc.<BR>
> (250) 383-3022<BR>
><BR>
> _______________________________________________<BR>
> postgis-devel mailing list<BR>
> postgis-devel@postgis.refractions.net<BR>
> <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
><BR>
><BR>
> ------------------------------------------------------------------------<BR>
><BR>
> *The substance of this message, including any attachments, may be<BR>
> confidential, legally privileged and/or exempt from disclosure<BR>
> pursuant to Massachusetts law. It is intended solely for the<BR>
> addressee. If you received this in error, please contact the sender<BR>
> and delete the material from any computer. *<BR>
><BR>
> ------------------------------------------------------------------------<BR>
><BR>
> * Help make the earth a greener place. If at all possible resist<BR>
> printing this email and join us in saving paper. *<BR>
><BR>
> * *<BR>
><BR>
> * *<BR>
><BR>
> ------------------------------------------------------------------------<BR>
><BR>
> _______________________________________________<BR>
> postgis-devel mailing list<BR>
> postgis-devel@postgis.refractions.net<BR>
> <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
> <BR>
<BR>
--<BR>
Martin Davis<BR>
Senior Technical Architect<BR>
Refractions Research, Inc.<BR>
(250) 383-3022<BR>
<BR>
_______________________________________________<BR>
postgis-devel mailing list<BR>
postgis-devel@postgis.refractions.net<BR>
<A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
<BR>
</FONT>
</P>
</BODY>
</HTML>