<div dir="ltr"><div class="gmail_default" style="font-family:monospace,monospace">Hey,<br></div><div class="gmail_default" style="font-family:monospace,monospace">sorry to high-jack this thread,<br></div><div class="gmail_default" style="font-family:monospace,monospace">but I've been looking for a way to use Hilbert curve for pgpointcloud for a while.<br><br></div><div class="gmail_default" style="font-family:monospace,monospace">basically, you got a bunch of points X,Y,Z, you order by Hilbert,<br>and then you are able to find points in a 3DBBox (or 2D polygon, or TIN) fast.<br></div><div class="gmail_default" style="font-family:monospace,monospace">This would play nice with postgis rtree on patch (2 level of indexes).<br></div><div class="gmail_default" style="font-family:monospace,monospace"><br><br></div><div class="gmail_default" style="font-family:monospace,monospace">It would be the perfect use case for you, as I fell PostGIS just got a new index (BRIN)<br></div><div class="gmail_default" style="font-family:monospace,monospace">whose functionality overlap a hilbert index (fast to build, low cost),<br></div><div class="gmail_default" style="font-family:monospace,monospace">and Hilbert would only be useful for points, wich is a big limitation for postgis (cf lake of sucess of SP-Gist).<br></div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">So any way if you do it for postgis, <br></div><div class="gmail_default" style="font-family:monospace,monospace">I would be _*very*_ interesting to do it in a nice lib so it can be used for other projects.<br></div><div class="gmail_default" style="font-family:monospace,monospace">(Somebody corrects me, but I don't know a C/Cpp implementation of 2DHilbert with polygon query)<br> <br></div><div class="gmail_default" style="font-family:monospace,monospace">Cheers,<br></div><div class="gmail_default" style="font-family:monospace,monospace">Rémi-C<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2016-03-23 3:27 GMT+01:00 Paul Ramsey <span dir="ltr"><<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Once the 2d/3d data linearized w/ a curve you wouldn't use<br>
rtree-over-gist anymore, you'd use something works on linear data,<br>
like btree or brin. The work isn't so much implementing the SFC, as it<br>
is adding the utility functions to convert an arbitrary query bounds<br>
into a set of ranges in the SFC space. I did this for trivial z<br>
curves. It's interesting stuff, not so sure how "postgis" it is,<br>
frankly, since it's almost better suited for use in a non-geometry<br>
table layout (column for X, column for Y, column for SFC value)<br>
<br>
P<br>
<div><div class="h5"><br>
On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan<br>
<<a href="mailto:achauhan4@student.gsu.edu">achauhan4@student.gsu.edu</a>> wrote:<br>
> Hi Brian Hamlin,<br>
> In continuation to our IRC chats, I want to present an approach of<br>
> implementing space filling curves for mapping 2D space to linear data which<br>
> can be indexed using current R-Tree-over-GiST scheme in PostGIS. #3<br>
> So the basic idea is to extend the current GIST scheme which may allow<br>
> PostGIS users to map using SFC’s namely the Hilbert, Serpenski and Moore<br>
> Curves, which have the potential to enhance scalability of PostGIS based<br>
> SDBs.<br>
><br>
> Real world utility will include choosing the right spatial indexing<br>
> mechanism based upon certain application requirements, for instance<br>
> application requiring secondary disk accesses may try to reduce jump<br>
> segments, whereas for primary memory accesses a jump segment could be highly<br>
> favorable. Moreover, the directional segments may help determine the flow of<br>
> SFC growth and also using the total directional vector.  #1<br>
><br>
> All of these algorithms are continuous recursive fractal curve generators so<br>
> the mapping an be from ∞ → N, which essentially means the mapping is never<br>
> ending with increasing granularity.<br>
><br>
> ·       For all recursive algorithms the number of hits per block remained<br>
> constant with the increasing size of grid after grid size 16.<br>
><br>
> ·       Number of disk blocks retrieved on a selection is a function only of<br>
> the size of the selected set and not the size of the database.<br>
><br>
> ·       For the specific class of queries studied, better than the worst<br>
> case O(N^(k-1/k)) for k attribute selection on a database with N records. #2<br>
><br>
><br>
> References:<br>
><br>
> Mokbel, M.F., Aref, W.G. and Kamel, I., 2003. Analysis of multi-dimensional<br>
> space-filling curves. GeoInformatica, 7(3), pp.179-209.<br>
> Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis of<br>
> the clustering properties of the Hilbert space-filling curve. Knowledge and<br>
> Data Engineering, IEEE Transactions on, 13(1), pp.124-141.<br>
> Obe, R.O. and Hsu, L.S., 2015. PostGIS in action. Manning Publications Co..<br>
><br>
> Regards<br>
> Ankush Chauhan<br>
> Student<br>
> Department of Computer Science<br>
> Georgia State University<br>
> Atlanta, GA<br>
> USA<br>
><br>
</div></div>> _______________________________________________<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/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">http://lists.osgeo.org/mailman/listinfo/postgis-devel</a><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/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">http://lists.osgeo.org/mailman/listinfo/postgis-devel</a></blockquote></div><br></div>