<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:"Consolas","serif";}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="FR-CA" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Hi,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Thank you for sharing these ideas. Many of the ideas can make improvements. In the prototype we have developed at RNCan and that we mentioned in the paper in attachment
we have implemented some of these concepts. For example, in the prototype we are sorting points according to the Morton pattern before creating blocks.
</span><span lang="EN-CA" style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">And each block is composed only of points that are spatially close, thereby improving the level of compression. We also use the properties of the Morton curve (Z pattern)
to do spatial queries using Geohash as BBox. </span><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Usually, in Geohash based system the more the Geohash prefixes for two points resemble one another, the more they are spatially close to
each other. Unfortunately, this property is not always complied with two points located on either side of a subdivision line.
</span><span lang="EN-CA" style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">For this reason we implemented a neighbourhood based strategy to allow spatial query based on the hash string.
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-CA" style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Also to improve the compression and performance we can change the encoding of Geohash.
</span><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Currently, the hashes are encoded as base 32 strings, which causes a lot of overhead (5 bits are inflated in 8 bits of character).
</span><span lang="EN-CA" style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Unfortunately, the current libght does not include all the concepts of GeoHashTree.
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-CA" style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Oscar, I will read your paper and get you back so we could continue to exchange.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Kind regards!<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Nouri,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-CA" style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-CA"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Paul Ramsey [mailto:pramsey@cleverelephant.ca]
<br>
<b>Sent:</b> 17 avril 2015 06:56<br>
<b>To:</b> pgpointcloud@lists.osgeo.org; Peter van Oosterom; Oscar Martinez Rubi; Howard Butler; Rémi Cura<br>
<b>Cc:</b> Sabo, Nouri<br>
<b>Subject:</b> Re: [pgpointcloud] RLE and SIGBITS heuristics<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Hi Oscar, <o:p></o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">This sounds like a slightly more sophisticated version of the work done at Natural Resources Canada for what they call “geohash tree”. They did find that they got pretty
good compression (even with the simple ascii-based key!) using the scheme, and it did allow easy random access to subsets of the data.<o:p></o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><a href="http://2013.foss4g.org/conf/programme/presentations/60/">http://2013.foss4g.org/conf/programme/presentations/60/</a><o:p></o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">The downside was of course the cost of sorting things in the first place, but for a one-time cost on frequently accessed data, it’s not a bad thing. The “libght” soft dependency
in pgpointcloud is to a (not so great) implementation of the scheme that I did for them a couple years ago. As a scheme, I think it cuts against the idea of having small patches that is core to the pgpointcloud concept. It makes more and more sense the larger
your file is, in that it gets greater and greater leverage for random access.<o:p></o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">ATB,<o:p></o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">P.<o:p></o:p></span></p>
</div>
<div id="bloop_customfont">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
</div>
<div id="bloop_sign_1429267881021870080">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">-- <br>
Paul Ramsey<br>
<a href="http://cleverelephant.ca">http://cleverelephant.ca</a><o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><a href="http://postgis.net">http://postgis.net</a>
<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
<p><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif";color:black">On April 17, 2015 at 11:02:47 AM, Oscar Martinez Rubi (<a href="mailto:o.martinezrubi@tudelft.nl">o.martinezrubi@tudelft.nl</a>) wrote:<o:p></o:p></span></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">Hi,<br>
<br>
About the XYZ binding for better compression. In our research in the NL escience center and TU Delft we have been thinking (not testing yet though) about one possible approach for this.<br>
<br>
It is based on using space filling curves. So, once you have the points that go in a block you could compute the morton/hilbert code of the XYZ. Since all the points are close together such codes will be extremely similar, so one could store only the increments
which could fit in many few bits. We have not tested or compared this with any of the other compressions but we just wanted to share it with you just in case you find it useful!<br>
<br>
An additional improvement would be to sort the points within the blocks according to the morton code. Then, when doing crop/filter operations in the blocks one can use the morton codes for the queries similarly to what we presented in our papers with the flat
table (without blocks), I attach one of them (see section 5.2). In a nutshell: You convert the query region into a set of quadtree/octree nodes which can be also converted to morton code ranges (thanks to relation between morton/hilbert curve and a quadtree/octree).
You scale down the ranges to increments (like you did when storing the point of the block) and then you simply do range queries in sorted data with a binary algorithm. In this way you avoid the decompression of the morton code for most of the block. This filtering
is equivalent to a bbox filter so it still requires a point in polygon check for some of the points.<br>
<br>
Kind Regards,<br>
<br>
Oscar.<br>
<br>
<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">On 16-04-15 18:15, Rémi Cura wrote:<o:p></o:p></span></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Courier New"">epic fail ! I had avoided html just for you</span><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Courier New""><br>
Dataset |subset size | compressing | decompressing |<br>
|(Million pts)|(Million pts/s)|(Million pts/s)|<br>
Lidar | 473.3 | 4,49 | 4,67 |</span><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Courier New"">21-atributes | 105.7 | 1,11 | 2,62 |</span><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p></o:p></span></p>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:10.0pt;font-family:"Courier New"">Stereo | 70 | 2,44 | 7,38 |</span><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Courier New"">Cheers</span><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p></o:p></span></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">2015-04-16 17:42 GMT+02:00 Sandro Santilli <<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a>>:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">On Thu, Apr 16, 2015 at 05:30:12PM +0200, Rémi Cura wrote:<br>
> OUps<br>
><br>
> Dataset | subset size(Million pts) | compressing (Million pts/s) |<br>
> decompressing (Million pts/s)<br>
> Lidar | 473.3 | 4,49<br>
> | __4,67__<br>
> 21 attributes | 105.7 |<br>
> 1,11 | 2,62<br>
> Stereo | 70 | 2,44<br>
> | 7,38<br>
<br>
These tables aren't really readable here.<br>
Could you make sure to use a fixed-width font to write those tables<br>
and to keep lines within 70 columns at most ?<br>
<br>
--strk;<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><br>
<br>
<br>
<o:p></o:p></span></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>pgpointcloud mailing list<o:p></o:p></pre>
<pre><a href="mailto:pgpointcloud@lists.osgeo.org">pgpointcloud@lists.osgeo.org</a><o:p></o:p></pre>
<pre><a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/pgpointcloud">http://lists.osgeo.org/cgi-bin/mailman/listinfo/pgpointcloud</a><o:p></o:p></pre>
</blockquote>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif""><o:p> </o:p></span></p>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:10.0pt;font-family:"Helvetica","sans-serif"">
<hr size="2" width="100%" align="center">
</span></div>
</div>
</div>
</blockquote>
</div>
</body>
</html>