[postgis-devel] Project Proposal GSOC16 | SFCs

[Paul Ramsey]

If done, a pure C would be much preferred :)

On Wed, Mar 23, 2016 at 3:49 AM, Rémi Cura <remi.cura at gmail.com> wrote:
> 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
>
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/postgis-devel