[postgis-devel] Project Proposal GSOC16 | SFCs

[Ankush Chauhan]

Thanks for the valuable input.
Paul is right about the fact that linear data would utilize linear indexing like B-Tree.
However, including coordinates for indexing can map every point in a GeoSpatial system linearly. Example below:
On Mar 23, 2016, at 11:30 AM, Brian M Hamlin <maplabs at light42.com<mailto:maplabs at light42.com>> wrote:

Hi Ankush -



  I have briefly looked over the Moon-Jagadish-Faloutsos-Saltz 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 R-Tree 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 <pramsey at cleverelephant.ca<mailto:pramsey at cleverelephant.ca>> wrote:
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<mailto: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<mailto:postgis-devel at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/postgis-devel
_______________________________________________
postgis-devel mailing list
postgis-devel at lists.osgeo.org<mailto:postgis-devel at lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/postgis-devel



--
Brian M Hamlin
OSGeo California Chapter
blog.light42.com<http://blog.light42.com/>



_______________________________________________
postgis-devel mailing list
postgis-devel at lists.osgeo.org<mailto:postgis-devel at lists.osgeo.org>
https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.osgeo.org%2fmailman%2flistinfo%2fpostgis-devel&data=01%7c01%7cachauhan4%40student.gsu.edu%7c9f8f66cba5834e4e86d608d353301d11%7c704d822c358a47849a1649e20b75f941%7c0&sdata=VMVJAZ3Teff1fAuKO2RTuFqJRuprexsmKQ9nLUIXGTY%3d

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20160323/ff457996/attachment.html>