<!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>Hmm that doesn't look like the right dataset. Now I have to figure out where I dug up this other towns layer. Running on this particular 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 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, 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 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 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 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 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 its just<BR>
> > > the nature of unioning in different orders. I compared all 3 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 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>
> > 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>
</FONT>
</P>
</BODY>
</HTML>
<HTML><BODY><P><hr size=1></P>
<P><STRONG>
The substance of this message, including any attachments, may be confidential, legally privileged and/or exempt from disclosure pursuant to Massachusetts law. It is intended solely for the addressee. If you received this in error, please contact the sender and delete the material from any computer.
</STRONG></P></BODY></HTML>
<P><hr size=1></P>
<P><STRONG><font size="2" color="339900"> Help make the earth a greener place. If at all possible resist printing this email and join us in saving paper. </p> <p> </font></STRONG></P>