<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Hi Sébastien,<br><br>Sounds like an interesting situation :-)<br><br>You might look at the newish (v8.4+ ?) RECURSIVE/WITH capabilities of Postgres.<br><br>Given Postgis allows you to create arbitrary buffer zones around your points, the RECURSIVE query capability allows you to write an SQL that will recursively track points which can interact with each other, so you should be able to <br><br>select points which interact with points which interact with points which.... <br>(ie: creates an "interaction cluster")<br><br>by using a Postgis buffer or a distance expression to represent "interact with". Or a similar effect to a predetermined level with subqueries in an SQL & cut-and-paste.<br><br>However I'm not sure this will give the performance you need, and an in-memory tool like R may be more appropriate than a disk based RDBMS solution.<br><br>A bit left

 field, but, depending on your use case, you could generate polygons for an "immediate neighbour" interaction as the distinct geomunion of all the point buffers which intersect with each other, then for each, select the count() of points contained in each to "rank" the clusters, or the count/area to estimate density within clusters, or assign points to clusters or vice versa.<br><br>There are lots of things you can do with Postgis in this arena, you need to really clarify the actual use case to see if it can be done in SQL, how it could be done and if it should be done in SQL :-)<br><br><br><br>Cheers,<br><br>  Brent Wood<br><br>--- On <b>Wed, 12/8/10, Sébastien Lorion <i><sl@thestrangefactory.com></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Sébastien Lorion <sl@thestrangefactory.com><br>Subject: Re: [postgis-users] Determining clusters of points<br>To:

 pcreso@pcreso.com<br>Cc: "PostGIS Users Discussion" <postgis-users@postgis.refractions.net><br>Date: Wednesday, December 8, 2010, 10:53 AM<br><br><div id="yiv1725727761"><div>Hello Brent,</div><div><br></div><div>Thanks for your help also. I saw this method, but I cannot use it in my scenario as it is too imprecise.</div><div><br></div><div>Consider all points as agents that interact with each other, each up to a certain range. I need to find interaction clusters and cannot afford to have those split in many parts, though it is ok to miss including some points.</div>

<div><br></div><div>Sébastien</div><br><div class="yiv1725727761gmail_quote">On Tue, Dec 7, 2010 at 15:06,  <span dir="ltr"><<a rel="nofollow" ymailto="mailto:pcreso@pcreso.com" target="_blank" href="/mc/compose?to=pcreso@pcreso.com">pcreso@pcreso.com</a>></span> wrote:<br><blockquote class="yiv1725727761gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<table border="0" cellpadding="0" cellspacing="0"><tbody><tr><td style="font-family: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; font-size: inherit; line-height: inherit; font-size-adjust: inherit; font-stretch: inherit;" valign="top">Hi Sébastien ,<br><br>One way I "clustered" points in the (distant) past for a zoom-layer mapping solution was to create multiple geometries, by reducing the number of decimal points in the X & Y coords and grouping by these locations. Simplistic & not especially statistical, but given a random point distribution you get an order of magnitude reduction in the number of positions of points at each step. With a non-random distribution, the reduction in number of these clusters is often greater. <br>

<br>I have also done a similar thing by creating grids of square cells of appropriate sizes, then assigning points to the cells using Postgis queries,  which allows a regular clustered sampling of the points by grid cell.<br>

<br>If you are after a more statistical approach, I'd look at using R, and once you have your R clustering capability coded, perhaps

 look at PL/R to embed the clustering capability within your database.<br><br>What isn't clear from your question is whether the clustering is something done often, perhaps at various resolutions, or is done once, to assign points to clusters, then used as these groups from then on. This would have an impact on performance & the approach you might take.<br>

<br>Also note that with both Postgis & R, any use of multiple cores or hardware clusters will require some work, as these are not applications that parallel process particularly well, but you could perhaps develop code that assigns individual analyses of data clusters to a load balanced hardware cluster. <br>

<br>If you have a clusterin algorithm, it may also be feaqsibl to implement it as a native user defined Postgis/Postgres function, but I think PL/R is an easier approach for embedded SQL clustering capability.<br><br><br>

HTH,   Brent Wood --- On Wed, 12/8/10,

 Sébastien Lorion <i><<a rel="nofollow" ymailto="mailto:sl@thestrangefactory.com" target="_blank" href="/mc/compose?to=sl@thestrangefactory.com">sl@thestrangefactory.com</a>></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;">

<br>From: Sébastien Lorion <<a rel="nofollow" ymailto="mailto:sl@thestrangefactory.com" target="_blank" href="/mc/compose?to=sl@thestrangefactory.com">sl@thestrangefactory.com</a>><br>Subject: Re: [postgis-users] Determining clusters of points<br>To: "PostGIS Users Discussion" <<a rel="nofollow" ymailto="mailto:postgis-users@postgis.refractions.net" target="_blank" href="/mc/compose?to=postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a>><br>

Date: Wednesday, December 8, 2010, 8:03 AM<div><div></div><div class="yiv1725727761h5"><br><br><div>I like your idea very much, especially since something I did not say is that the points have a range attribute which determines how far they can interact with other points. So the circle buffer you talk about would have a diameter equals to the range of each point.<div>

<br></div><div>What would be fastest as the last step : bounding box, minimum bounding circle or minimum convex hull ? I am guessing the BB, but is the difference significant enough that one should be chosen over another ?</div>

<div><br></div><div>Sébastien<br><br><div>On Tue, Dec 7, 2010 at 13:42, Emilie Laffray <span dir="ltr"><<a rel="nofollow" target="_blank" href="http://mc/compose?to=emilie.laffray@gmail.com">emilie.laffray@gmail.com</a>></span> wrote:<br>

<blockquote style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<div><div></div><div><br><br><div>On 7 December 2010 17:01, Sébastien Lorion <span dir="ltr"><<a rel="nofollow" target="_blank" href="http://mc/compose?to=sl@thestrangefactory.com">sl@thestrangefactory.com</a>></span> wrote:<br>

<blockquote style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Hello,<div><br></div><div>I am trying to find an efficient way to find clusters of points as shown in the attached image. The only clustering criteria is the distance between the points. The dataset can be very large (millions of points) and point distribution is mostly clustered with some sparse points in the gaps.</div>

<div><br></div><div>I searched the net and this mailing list and found two promising solution paths: </div><div><br></div><div>- use a statistical tools such as R with a density function (<a rel="nofollow" target="_blank" href="http://www.r-project.org/">http://www.r-project.org</a>)</div>

<div>- use a clustering algorithm like those explained here <a rel="nofollow" target="_blank" href="http://www.med.nyu.edu/biostatistics/people/Ilana%20Belitskaya-Levy/Courses/MAS/Handouts/clustering.pdf">http://www.med.nyu.edu/biostatistics/people/Ilana%20Belitskaya-Levy/Courses/MAS/Handouts/clustering.pdf</a> (agnes seems the most promising for my purposes)</div>

<div><br></div><div><a rel="nofollow" target="_blank" href="http://www.med.nyu.edu/biostatistics/people/Ilana%20Belitskaya-Levy/Courses/MAS/Handouts/clustering.pdf"></a>I would like your advice to help me find which approach would be best suited with PostGIS (maybe there is even something already made that I can use?). Whatever solution I pick, it must be efficient and the workload must be able to be distributed on a cluster of commodity hardware.</div>

<div><br></div><div>I am new to GIS and this mailing list, so please excuse me if I am not using the right vocabulary.</div><div><br></div><div>Thank you very much!</div><br></blockquote></div><br></div></div>Hello,<br><br>

Some time ago I have worked on something similar, except that I was using circles instead of boxes which should not be a problem. I am just giving the logic as I don't have access to the code right now.<br>

You can start by creating a buffer around each of your points of the distance you want. <br>The next step is to create an UNION of all the buffers that intersect.<br>You get the list of points included in each of the resulting polygons and then you create either a bounding box around them or use a minimum bounding circle (Postgis 1.5 and above).<br>

<br>Emily Laffray<br>

<br>_______________________________________________<br>

postgis-users mailing list<br>

<a rel="nofollow" target="_blank" href="http://mc/compose?to=postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>

<a rel="nofollow" target="_blank" href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</a><br>

<br></blockquote></div><br></div>

</div><br></div></div>-----Inline Attachment Follows-----<div class="yiv1725727761im"><br><br><div>_______________________________________________<br>postgis-users mailing list<br><a rel="nofollow" target="_blank" href="http://mc/compose?to=postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>

<a rel="nofollow" target="_blank" href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</a><br></div></div></blockquote></td></tr></tbody></table></blockquote>

</div><br>

</div></blockquote></td></tr></table>