

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 RTreeoverGiST 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^(k1/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 multidimensional spacefilling curves. GeoInformatica, 7(3), pp.179209.
 Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis of the
clustering properties of the Hilbert spacefilling curve. Knowledge and Data Engineering,
IEEE Transactions on, 13(1),
pp.124141.
 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
_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel


Once the 2d/3d data linearized w/ a curve you wouldn't use
rtreeovergist 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 nongeometry
table layout (column for X, column for Y, column for SFC value)
P
On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan
< [hidden email]> 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 RTreeoverGiST 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^(k1/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 multidimensional
> spacefilling curves. GeoInformatica, 7(3), pp.179209.
> Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis of
> the clustering properties of the Hilbert spacefilling curve. Knowledge and
> Data Engineering, IEEE Transactions on, 13(1), pp.124141.
> 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
>
> _______________________________________________
> postgisdevel mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/postgisdevel_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel


Hey,
sorry to highjack 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 SPGist).
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émiC
_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel


If done, a pure C would be much preferred :)
On Wed, Mar 23, 2016 at 3:49 AM, Rémi Cura < [hidden email]> wrote:
> Hey,
> sorry to highjack 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 SPGist).
>
> 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émiC
>
> 20160323 3:27 GMT+01:00 Paul Ramsey < [hidden email]>:
>>
>> Once the 2d/3d data linearized w/ a curve you wouldn't use
>> rtreeovergist 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 nongeometry
>> table layout (column for X, column for Y, column for SFC value)
>>
>> P
>>
>> On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan
>> < [hidden email]> 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 RTreeoverGiST 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^(k1/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
>> > multidimensional
>> > spacefilling curves. GeoInformatica, 7(3), pp.179209.
>> > Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis
>> > of
>> > the clustering properties of the Hilbert spacefilling curve. Knowledge
>> > and
>> > Data Engineering, IEEE Transactions on, 13(1), pp.124141.
>> > 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
>> >
>> > _______________________________________________
>> > postgisdevel mailing list
>> > [hidden email]
>> > http://lists.osgeo.org/mailman/listinfo/postgisdevel>> _______________________________________________
>> postgisdevel mailing list
>> [hidden email]
>> http://lists.osgeo.org/mailman/listinfo/postgisdevel>
>
>
> _______________________________________________
> postgisdevel mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/postgisdevel_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel


Hi Ankush 
I have briefly looked over the MoonJagadishFaloutsosSaltz paper.. I see
where you may be going with this inquiry.
I agree with Paul Ramsey (below) that once the data is reduced, retrieval and
such becomes a linear problem, for which linear indexing is a best fit . The
linearization is in fact, the whole point of the exercise !!
It is true the PostGIS RTree index implementation uses the Postgres GIST
mechanism. The GIST mechanism is not easy going ! It is abstract in design and
terse in implementation. I do not have an opinion on whether GIST is the right
vehicle to implement this idea. Evaluation of GIST, or no GIST, would have to
be part of the project.
If there is a fit to a GSoC project here, we have to realign to these two
realities. To get to actual, working code here is an ambitious undertaking !
Please respond.
best regards from Berkeley, California
 Brian M Hamlin
On Tue, 22 Mar 2016 19:27:47 0700, Paul Ramsey
<[hidden email]> wrote:
Once the 2d/3d data
linearized w/ a curve you wouldn't use rtreeovergist 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 nongeometry
table layout (column for X, column for Y, column for SFC value)
P
On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan
<[hidden email]> 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 RTreeoverGiST 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^(k1/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 multidimensional > spacefilling curves. GeoInformatica,
7(3), pp.179209. > Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz,
J.H., 2001. Analysis of > the clustering properties of the Hilbert
spacefilling curve. Knowledge and > Data Engineering, IEEE Transactions
on, 13(1), pp.124141. > 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 > >
_______________________________________________ > postgisdevel mailing
list > [hidden email] >
http://lists.osgeo.org/mailman/listinfo/postgisdevel
_______________________________________________ postgisdevel mailing
list [hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel
 Brian M Hamlin OSGeo California Chapter
blog.light42.com
_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel


Thanks for the valuable input.
Paul is right about the fact that linear data would utilize linear indexing like BTree.
However, including coordinates for indexing can map every point in a GeoSpatial system linearly. Example below:
Hi Ankush 
I have briefly looked over the MoonJagadishFaloutsosSaltz paper.. I see where you may be going with this inquiry.
I agree with Paul Ramsey (below) that once the data is reduced, retrieval and such becomes a linear problem, for which linear indexing is a best fit . The linearization is in fact, the whole point of the exercise !!
It is true the PostGIS RTree index implementation uses the Postgres GIST mechanism. The GIST mechanism is not easy going ! It is abstract in design and terse in implementation. I do not have an opinion on whether GIST is the right vehicle to implement this
idea. Evaluation of GIST, or no GIST, would have to be part of the project.
If there is a fit to a GSoC project here, we have to realign to these two realities. To get to actual, working code here is an ambitious undertaking ! Please respond.
best regards from Berkeley, California
 Brian M Hamlin
On Tue, 22 Mar 2016 19:27:47 0700, Paul Ramsey < [hidden email]> wrote:
Once the 2d/3d data linearized w/ a curve you wouldn't use
rtreeovergist 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 nongeometry
table layout (column for X, column for Y, column for SFC value)
P
On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan
<[hidden email]> 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 RTreeoverGiST 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^(k1/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 multidimensional
> spacefilling curves. GeoInformatica, 7(3), pp.179209.
> Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis of
> the clustering properties of the Hilbert spacefilling curve. Knowledge and
> Data Engineering, IEEE Transactions on, 13(1), pp.124141.
> 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
>
> _______________________________________________
> postgisdevel mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/postgisdevel
_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel
_______________________________________________
postgisdevel
mailing list
[hidden email]
https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.osgeo.org%2fmailman%2flistinfo%2fpostgisdevel&data=01%7c01%7cachauhan4%40student.gsu.edu%7c9f8f66cba5834e4e86d608d353301d11%7c704d822c358a47849a1649e20b75f941%7c0&sdata=VMVJAZ3Teff1fAuKO2RTuFqJRuprexsmKQ9nLUIXGTY%3d
_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel


Within this indexing schema these 2D space can be benchmarked with previous SAMs(Spatial Indexing Mechanisms) for scalability and fairness analyatics which can be helpful in overall query processing time.
As displayed in the above diagram the second table with combination of primary and secondary indexes can intersect two different SAMs and improve query processing.
And in the context of PostGIS it can speed up kNN queries.
No offense, but the current PostGIS SAMs are naïve and SFCs can surely fill up the gap for scalability of dimensions from 3D and beyond.
Why can’t the DBA have the choice of choosing indexing mechanism based upon their application, moreover these SAMs can also help convert LiDAR point data into 2D.
That being said I am open to further discussions, if the above idea is not novel enough for PostGIS, I am actively seeking ways to contribute to PostGIS. I have an expertise in the concepts Spatial Databases and scientific computing.
I am open for suggestions on similar project ideas out there, if any.
Thanks & Regards
Ankush Chauhan
Student
Department of Computer Science
Georgia State University
Atlanta, GA
USA
Thanks for the valuable input.
Paul is right about the fact that linear data would utilize linear indexing like BTree.
However, including coordinates for indexing can map every point in a GeoSpatial system linearly. Example below:
Hi Ankush 
I have briefly looked over the MoonJagadishFaloutsosSaltz paper.. I see where you may be going with this inquiry.
I agree with Paul Ramsey (below) that once the data is reduced, retrieval and such becomes a linear problem, for which linear indexing is a best fit . The linearization is in fact, the whole point of the exercise !!
It is true the PostGIS RTree index implementation uses the Postgres GIST mechanism. The GIST mechanism is not easy going ! It is abstract in design and terse in implementation. I do not have an opinion on whether GIST is the right vehicle to implement this
idea. Evaluation of GIST, or no GIST, would have to be part of the project.
If there is a fit to a GSoC project here, we have to realign to these two realities. To get to actual, working code here is an ambitious undertaking ! Please respond.
best regards from Berkeley, California
 Brian M Hamlin
On Tue, 22 Mar 2016 19:27:47 0700, Paul Ramsey < [hidden email]> wrote:
Once the 2d/3d data linearized w/ a curve you wouldn't use
rtreeovergist 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 nongeometry
table layout (column for X, column for Y, column for SFC value)
P
On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan
<[hidden email]> 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 RTreeoverGiST 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^(k1/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 multidimensional
> spacefilling curves. GeoInformatica, 7(3), pp.179209.
> Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis of
> the clustering properties of the Hilbert spacefilling curve. Knowledge and
> Data Engineering, IEEE Transactions on, 13(1), pp.124141.
> 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
>
> _______________________________________________
> postgisdevel mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/postgisdevel
_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel
_______________________________________________
postgisdevel
mailing list
[hidden email]
https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.osgeo.org%2fmailman%2flistinfo%2fpostgisdevel&data=01%7c01%7cachauhan4%40student.gsu.edu%7c9f8f66cba5834e4e86d608d353301d11%7c704d822c358a47849a1649e20b75f941%7c0&sdata=VMVJAZ3Teff1fAuKO2RTuFqJRuprexsmKQ9nLUIXGTY%3d
_______________________________________________
postgisdevel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgisdevel

