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