<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="">
Hi Brian Hamlin,
<div class="">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<br class="">
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.<br class="">
<br class="">
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
<div class=""><br class="">
</div>
<div class="">All of these algorithms are continuous recursive fractal curve generators so the mapping an be from <span style="color: rgb(34, 34, 34); font-family: arial, sans-serif; font-size: 16px; line-height: 19.2px; widows: 1; background-color: rgb(255, 255, 255);" class="">∞ </span><span style="color: rgb(84, 84, 84); font-family: arial, sans-serif; font-size: small; line-height: 18.2px; widows: 1; background-color: rgb(255, 255, 255);" class="">→
N, which essentially means the mapping is never ending with increasing granularity.</span></div>
<span class=""><br class="">
· For all recursive algorithms the number of hits per block remained 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 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 case O(N^(k-1/k)) for k attribute selection on a database with N records. #2<br class="">
</span><br class="">
<div class=""><br class="">
</div>
<div class="">References:<span class=""><br class="">
<ol class="">
<li class="">Mokbel, M.F., Aref, W.G. and Kamel, I., 2003. Analysis of multi-dimensional space-filling curves. GeoInformatica, 7(3), pp.179-209.</li><li class=""><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16.12px; widows: 1; background-color: rgb(255, 255, 255);" class="">Moon, B., Jagadish, H.V., Faloutsos, C. and Saltz, J.H., 2001. Analysis of the
clustering properties of the Hilbert space-filling curve. </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16.12px; widows: 1; background-color: rgb(255, 255, 255);" class="">Knowledge and Data Engineering,
IEEE Transactions on</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16.12px; widows: 1; background-color: rgb(255, 255, 255);" class="">, </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16.12px; widows: 1; background-color: rgb(255, 255, 255);" class="">13</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16.12px; widows: 1; background-color: rgb(255, 255, 255);" class="">(1),
pp.124-141.</span></li><li class="">Obe, R.O. and Hsu, L.S., 2015. PostGIS in action. Manning Publications Co..</li></ol>
Regards</span></div>
<div class=""><span class="">Ankush Chauhan</span></div>
<div class=""><span class="">Student</span></div>
<div class=""><span class="">Department of Computer Science</span></div>
<div class=""><span class="">Georgia State University</span></div>
<div class=""><span class="">Atlanta, GA</span></div>
<div class=""><span class="">USA</span></div>
</div>
</body>
</html>