<div dir="ltr">Hey,<div>I'm not sure I understand perfectly your problem, </div><div>for instance why exactly do you need an unioned footprint? </div><div>Could you not stick to function where f(footprint) = sum(f(cells)) (this work for area, cover analysis etc.).</div>
<div>Meaning you could aggregate your result cell by cells.</div><div><br>Another think is what about your input data precision? I'm guessing it is low precision, so you may cut corners during processing (for instance, using buffer with quad_segs=2 to lower number of vertices in generated buffer, so generated footprint).</div>
<div><br></div><div><br></div><div>If not, and for <b>very</b> big data you may need to change your way of working.</div><div>The ideal candidat (lots of memory, less cpu) is image processing!</div><div>Fortunately you can switch to image world, where operations are <b>way way</b> faster, and easily made in parallel.<br>
</div><div>In image world you don't have to care about topology and exact computation, you can just compute by pixels.<br>(I won't even talk about GPU processing, but it may be used depending on your operations)</div>
<div><br></div><div>(If you don't require too much precision and can cope with aliasing effect)</div><div><br></div><div>Your data process would look like this :</div><div>using <a href="http://www.gdal.org/">gdal</a> directly (or several connection to postgis) you rasterize your polygons cells by cells. You do it the parallel way. You should have one image file per cell as output.</div>
<div><br></div><div>This images can be assembled into one big image depending on memory limitation.</div><div>If it doesn't fit in memory, you can use very fast , very efficient out of memory parallel processing software like Orfeo ToolBox, included in QGis sextante, depending on what you want to do.<br>
</div><div><br></div><div>What is cool with images is that you can do things you can't with pure geometry : </div><div>I'm guessing you are working on data that are observations of animals. Instead of using a plain surface like "area where it is likely animals live", you could use <a href="http://gitta.info/Suitabilityi/en/html/fuzzy_learningObject2.html">fuzzy models</a> (in the area, probability of animal living would be decreasing as the distance with the observation of animal),</div>
<div>then generate more "precise" and interesting results.<br><br></div><div><br></div><div>I made a lot's of guess so my answer may be completely useless .</div><div>I can precise things unclear.</div><div>
<br></div><div>Cheers,</div><div>Rémi-C</div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/10/17 Brent Wood <span dir="ltr"><<a href="mailto:pcreso@pcreso.com" target="_blank">pcreso@pcreso.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-size:12pt;font-family:times new roman,new york,times,serif"><div><span>These tend to assume each operation is constrained to a single cell, hence parallelizable, hence undertaking an operation on multiple cells concurrently.</span></div>
<div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif"><br><span></span></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
<span>While I'm dealing with many cells - they are all being merged into a single multipolygon feature. I can't load two cells into the same multipolygon at the same time - two writes to the same record - so can't run concurrently.<br>
</span></div><div><br></div><div>What may be possible is to perhaps run multiple processes on
subsets to create intermediate (larger) merged polygons which can then be merged themselves to create the final single feature.</div><div><br></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
This would probably allow better use of resources on a multi core system... at present I'm using 1.7% of memory on a 100% cpu process, so I'll look into this approach - 8 cores running concurrently giving giving close to 8x faster is useful.</div>
<div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif"><br></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
Brent<br></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif"><br></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
<br></div> <div style="font-family:times new roman,new york,times,serif;font-size:12pt"> <div style="font-family:times new roman,new york,times,serif;font-size:12pt"> <div dir="ltr"> <hr size="1"> <font face="Arial"> <b><span style="font-weight:bold">From:</span></b> "<a href="mailto:maplabs@light42.com" target="_blank">maplabs@light42.com</a>" <<a href="mailto:maplabs@light42.com" target="_blank">maplabs@light42.com</a>><br>
<b><span style="font-weight:bold">To:</span></b> Brent Wood <<a href="mailto:pcreso@pcreso.com" target="_blank">pcreso@pcreso.com</a>>; PostGIS Development Discussion <<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a>>; Bborie Park <<a href="mailto:dustymugs@gmail.com" target="_blank">dustymugs@gmail.com</a>> <br>
<b><span style="font-weight:bold">Cc:</span></b> PostGIS Users Discussion <<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a>> <br> <b><span style="font-weight:bold">Sent:</span></b> Thursday,
October 17, 2013 3:16 PM<br> <b><span style="font-weight:bold">Subject:</span></b> Re: [postgis-devel] ST_Union() performance problem (with possiblefunding)<br> </font> </div><div><div class="h5"> <div><br><div><div><div>
yes,
true.. but with a thorough read you might notice that the gdal_retile.py
experiment was largely ineffective, </div><div>but if you click on the link at the
top to the *next post* </div><h2> Variable Buffers in
PostGIS</h2><div>you will find the one that really worked well.. in fact, we used
that 2nd post in production for months, to great effect.</div><div>The trick on one
machine was to split to work by some constant, and then make psycopg2
connections for each "bucket."</div><div><br clear="none"></div><div>This worked very well..
</div><div><br clear="none"></div><div>Since then I have experimented only a tiny bit with SPARK from
the Berkeley Amp Lab for a distributed work load on a Hadoop file system, but
that world has no GEOS (yet) </div><div><br clear="none"></div><div>--</div><div>Brian M
Hamlin</div><div>OSGeo California
Chapter</div><div><a href="http://blog.light42.com" target="_blank">blog.light42.com</a></div><div><br clear="none"></div><div><div><br clear="none"><br clear="none">On Wed, 16 Oct 2013
17:28:27 -0700, Bborie Park <<a href="mailto:dustymugs@gmail.com" target="_blank">dustymugs@gmail.com</a>>
wrote:<br clear="none"></div><blockquote dir="ltr" style="border-left:2px solid rgb(0,0,0);padding-right:0px;padding-left:5px;margin-left:5px;margin-right:0px"><div><div dir="ltr">Your best bet is to consider splitting the workload among several
postgresql connections.<div><br clear="none"></div><div>darkblueb had a blog post about
this...</div><div><br clear="none"></div><div><a rel="nofollow" shape="rect" href="http://blog.light42.com/wordpress/?p=23" target="_blank">http://blog.light42.com/wordpress/?p=23</a><br clear="none"></div></div><div><br clear="none">
</div><div><br clear="none"></div><div><br clear="none"><div>On Wed, Oct 16, 2013 at 5:21
PM, Brent Wood <span dir="ltr"><<a rel="nofollow" shape="rect" href="mailto:pcreso@pcreso.com" target="_blank">pcreso@pcreso.com</a>></span> wrote:<br clear="none"><blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div style="font-size:12pt;font-family:times new roman,new york,times,serif"><div>Hi, <br clear="none"></div><div><br clear="none"></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
Any advice appreciated!!</div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif"><br clear="none"></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
I'm undertaking a spatial analysis using Postgis (what else would I use!!!). The
first part works well.<br clear="none"></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
<br clear="none"></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">I take a large number (potentially millions) of lines defined
by start & end points & buffer them to create polygons. (I'm working in
lat/long EPSG:4326 but transforming to a custom equal area projection for the
buffering operation).</div>
<div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif"><br clear="none"></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
I generate a grid of 5x5km cells (polygons) covering the region of
interest.</div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif"><br clear="none"></div><div style="font-style:normal;font-size:16px;background-color:transparent;font-family:times new roman,new york,times,serif">
I clip the line based polygons to the grid, so I can generate statistics for
each cell describing the lines that intersect with it, various quantitative
measures such as ST_Union() the clipped line polygons to generate a footprint in
each cell to work out how much is/is not covered, or sum the ST_Area() of the
clipped polygons grouped by cell to calculate an aggregate cover, which can be
several times the actual cell area.<br clear="none"></div><div style="font-family:times new roman,new york,times,serif;font-size:12pt"><div style="font-family:times new roman,new york,times,serif;font-size:12pt"><br clear="none">
<br clear="none">So far so good, it works
well, the code is clear & transparent & provides a good result. At least
as good as any commercial software can do. My test
data subset is processed from scratch in about 30 minutes.<br clear="none"></div> </div>
<span><br clear="none">Now I want to ST_Union() all the cell based polygons into an overall
single multipolygon representing the footprint. The code is simple. The
performance, even with my subset, is a problem.<br clear="none"><br clear="none">I have thousands of
cell based footprint multipolygons, each potentially with thousands of vertices
to be ST_Union()ed. Runtime is weeks for an iteration. If I need separate total
footprints for 20 different species annually for 5 years, that is 100
iterations. Memory & I/O use is minimal - it is totally cpu bound.<br clear="none"><br clear="none">I
am looking at trying to simplify the polygons to be unioned to reduce the number
of vertices (& hence processing) involved, but to achieve any significant
benefit I'm having to change the shape of the polygons to ST_Union() too much.
<br clear="none"><br clear="none"><br clear="none"><br clear="none">Does anyone have any suggestions as to how this could be made
significantly faster? <br clear="none">If I
had $$ to throw at developers to work on the codebase (presumably GEOS?) could
performance be significantly improved?<br clear="none"><br clear="none"><br clear="none">Thanks,<br clear="none"><br clear="none"> Brent
Wood</span><div></div></div></div><br clear="none">_______________________________________________<br clear="none">
postgis-devel mailing list<br clear="none"><a rel="nofollow" shape="rect" href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br clear="none"><a rel="nofollow" shape="rect" href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel</a><br clear="none">
</blockquote></div><br clear="none"></div>
</div>
<br clear="none"><hr><br clear="none">
_______________________________________________<br clear="none">
postgis-devel mailing list<br clear="none">
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br clear="none"><a rel="nofollow" shape="rect" href="http://webmail.light42.com/hwebmail/services/go.php?url=http%3A%2F%2Flists.osgeo.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fpostgis-devel" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel</a></blockquote>
</div><div><br clear="none"><br clear="none"></div><div><br clear="none"></div><div><br clear="none"></div></div></div><br><br></div> </div></div></div> </div> </div></div><br>_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel</a><br></blockquote></div><br></div>