<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
Thanks for the valuable input.<br class="">
Paul is right about the fact that linear data would utilize linear indexing like B-Tree.<br class="">
However, including coordinates for indexing can map every point in a GeoSpatial system linearly. Example below:<br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Mar 23, 2016, at 11:30 AM, Brian M Hamlin <<a href="mailto:maplabs@light42.com" class="">maplabs@light42.com</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
Hi Ankush -</div>
<p style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</p>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
I have briefly looked over the Moon-Jagadish-Faloutsos-Saltz paper.. I see where you may be going with this inquiry.</div>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
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 !!</div>
<p style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</p>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
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.</div>
<p style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</p>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
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.</div>
<p style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</p>
<p style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</p>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
best regards from Berkeley, California</div>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
-- Brian M Hamlin</div>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br class="">
<br class="">
On Tue, 22 Mar 2016 19:27:47 -0700, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca" class="">pramsey@cleverelephant.ca</a>> wrote:</div>
<blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; border-left-width: 2px; border-left-style: solid; border-left-color: rgb(0, 0, 0); padding-right: 0px; padding-left: 5px; margin-left: 5px; margin-right: 0px;" class="">
Once the 2d/3d data linearized w/ a curve you wouldn't use<br class="">
rtree-over-gist anymore, you'd use something works on linear data,<br class="">
like btree or brin. The work isn't so much implementing the SFC, as it<br class="">
is adding the utility functions to convert an arbitrary query bounds<br class="">
into a set of ranges in the SFC space. I did this for trivial z<br class="">
curves. It's interesting stuff, not so sure how "postgis" it is,<br class="">
frankly, since it's almost better suited for use in a non-geometry<br class="">
table layout (column for X, column for Y, column for SFC value)<br class="">
<br class="">
P<br class="">
<br class="">
On Tue, Mar 22, 2016 at 5:52 PM, Ankush Chauhan<br class="">
<<a href="mailto:achauhan4@student.gsu.edu" class="">achauhan4@student.gsu.edu</a>> wrote:<br class="">
> Hi Brian Hamlin,<br class="">
> In continuation to our IRC chats, I want to present an approach of<br class="">
> implementing space filling curves for mapping 2D space to linear data which<br class="">
> can be indexed using current R-Tree-over-GiST scheme in PostGIS. #3<br class="">
> So the basic idea is to extend the current GIST scheme which may allow<br class="">
> PostGIS users to map using SFC’s namely the Hilbert, Serpenski and Moore<br class="">
> Curves, which have the potential to enhance scalability of PostGIS based<br class="">
> SDBs.<br class="">
><br class="">
> Real world utility will include choosing the right spatial indexing<br class="">
> mechanism based upon certain application requirements, for instance<br class="">
> application requiring secondary disk accesses may try to reduce jump<br class="">
> segments, whereas for primary memory accesses a jump segment could be highly<br class="">
> favorable. Moreover, the directional segments may help determine the flow of<br class="">
> SFC growth and also using the total directional vector. #1<br class="">
><br class="">
> All of these algorithms are continuous recursive fractal curve generators so<br class="">
> the mapping an be from ∞ → N, which essentially means the mapping is never<br class="">
> ending with increasing granularity.<br class="">
><br class="">
> · For all recursive algorithms the number of hits per block remained<br class="">
> constant with the increasing size of grid after grid size 16.<br class="">
><br class="">
> · Number of disk blocks retrieved on a selection is a function only of<br class="">
> the size of the selected set and not the size of the database.<br class="">
><br class="">
> · For the specific class of queries studied, better than the worst<br class="">
> case O(N^(k-1/k)) for k attribute selection on a database with N records. #2<br class="">
><br class="">
><br class="">
> References:<br class="">
><br class="">
> Mokbel, M.F., Aref, W.G. and Kamel, I., 2003. Analysis of multi-dimensional<br class="">
> space-filling curves. GeoInformatica, 7(3), pp.179-209.<br class="">
> Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis of<br class="">
> the clustering properties of the Hilbert space-filling curve. Knowledge and<br class="">
> Data Engineering, IEEE Transactions on, 13(1), pp.124-141.<br class="">
> Obe, R.O. and Hsu, L.S., 2015. PostGIS in action. Manning Publications Co..<br class="">
><br class="">
> Regards<br class="">
> Ankush Chauhan<br class="">
> Student<br class="">
> Department of Computer Science<br class="">
> Georgia State University<br class="">
> Atlanta, GA<br class="">
> USA<br class="">
><br class="">
> _______________________________________________<br class="">
> postgis-devel mailing list<br class="">
><span class="Apple-converted-space"> </span><a href="mailto:postgis-devel@lists.osgeo.org" class="">postgis-devel@lists.osgeo.org</a><br class="">
><span class="Apple-converted-space"> </span><a href="http://lists.osgeo.org/mailman/listinfo/postgis-devel" class="">http://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br class="">
_______________________________________________<br class="">
postgis-devel mailing list<br class="">
<a href="mailto:postgis-devel@lists.osgeo.org" class="">postgis-devel@lists.osgeo.org</a><br class="">
<a href="http://lists.osgeo.org/mailman/listinfo/postgis-devel" class="">http://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br class="">
</blockquote>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br class="">
<br class="">
</div>
<div style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br class="">
--<br class="">
Brian M Hamlin<br class="">
OSGeo California Chapter<br class="">
<a href="http://blog.light42.com/" class="">blog.light42.com</a><br class="">
</div>
<p style="margin: 0px; padding: 0px; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</p>
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">postgis-devel
mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<a href="mailto:postgis-devel@lists.osgeo.org" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">postgis-devel@lists.osgeo.org</a><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<a href="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" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">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</a></div>
</blockquote>
</div>
<br class="">
</body>
</html>