[postgis-devel] Project Proposal GSOC16 | SFCs

[Rémi Cura]

Hey,
sorry to high-jack this thread,
but I've been looking for a way to use Hilbert curve for pgpointcloud for a
while.

basically, you got a bunch of points X,Y,Z, you order by Hilbert,
and then you are able to find points in a 3DBBox (or 2D polygon, or TIN)
fast.
This would play nice with postgis rtree on patch (2 level of indexes).


It would be the perfect use case for you, as I fell PostGIS just got a new
index (BRIN)
whose functionality overlap a hilbert index (fast to build, low cost),
and Hilbert would only be useful for points, wich is a big limitation for
postgis (cf lake of sucess of SP-Gist).

So any way if you do it for postgis,
I would be _*very*_ interesting to do it in a nice lib so it can be used
for other projects.
(Somebody corrects me, but I don't know a C/Cpp implementation of 2DHilbert
with polygon query)

Cheers,
Rémi-C

2016-03-23 3:27 GMT+01:00 Paul Ramsey <pramsey at cleverelephant.ca>:

> Once the 2d/3d data linearized w/ a curve you wouldn't use
> rtree-over-gist anymore, you'd use something works on linear data,
> like btree or brin. The work isn't so much implementing the SFC, as it
> is adding the utility functions to convert an arbitrary query bounds
> into a set of ranges in the SFC space. I did this for trivial z
> curves. It's interesting stuff, not so sure how "postgis" it is,
> frankly, since it's almost better suited for use in a non-geometry
> table layout (column for X, column for Y, column for SFC value)
>
> P
>
> On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan
> <achauhan4 at student.gsu.edu> wrote:
> > Hi Brian Hamlin,
> > In continuation to our IRC chats, I want to present an approach of
> > implementing space filling curves for mapping 2D space to linear data
> which
> > can be indexed using current R-Tree-over-GiST scheme in PostGIS. #3
> > So the basic idea is to extend the current GIST scheme which may allow
> > PostGIS users to map using SFC’s namely the Hilbert, Serpenski and Moore
> > Curves, which have the potential to enhance scalability of PostGIS based
> > SDBs.
> >
> > Real world utility will include choosing the right spatial indexing
> > mechanism based upon certain application requirements, for instance
> > application requiring secondary disk accesses may try to reduce jump
> > segments, whereas for primary memory accesses a jump segment could be
> highly
> > favorable. Moreover, the directional segments may help determine the
> flow of
> > SFC growth and also using the total directional vector.  #1
> >
> > All of these algorithms are continuous recursive fractal curve
> generators so
> > the mapping an be from ∞ → N, which essentially means the mapping is
> never
> > ending with increasing granularity.
> >
> > ·       For all recursive algorithms the number of hits per block
> remained
> > constant with the increasing size of grid after grid size 16.
> >
> > ·       Number of disk blocks retrieved on a selection is a function
> only of
> > the size of the selected set and not the size of the database.
> >
> > ·       For the specific class of queries studied, better than the worst
> > case O(N^(k-1/k)) for k attribute selection on a database with N
> records. #2
> >
> >
> > References:
> >
> > Mokbel, M.F., Aref, W.G. and Kamel, I., 2003. Analysis of
> multi-dimensional
> > space-filling curves. GeoInformatica, 7(3), pp.179-209.
> > Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis
> of
> > the clustering properties of the Hilbert space-filling curve. Knowledge
> and
> > Data Engineering, IEEE Transactions on, 13(1), pp.124-141.
> > Obe, R.O. and Hsu, L.S., 2015. PostGIS in action. Manning Publications
> Co..
> >
> > Regards
> > Ankush Chauhan
> > Student
> > Department of Computer Science
> > Georgia State University
> > Atlanta, GA
> > USA
> >
> > _______________________________________________
> > postgis-devel mailing list
> > postgis-devel at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/postgis-devel
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/postgis-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20160323/5bebd8ed/attachment.html>