Re: sparse bitset compression

--===============0340997904334749734==
Content-Type: multipart/alternative; boundary=047d7ba97e649a65d704f02e6031

--047d7ba97e649a65d704f02e6031
Content-Type: text/plain; charset=ISO-8859-1

Its on the fringe of being useful, but one thing you could look at to
reduce your data size is Exponential Golomb coding (
http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in H.264
entropy encoding among other things.

Instead of writing a full n-bit values for every number you store, it
produces a bit stream of codes, using far less bits for small numbers -
take a look at the wiki page, its pretty simple to see whats going on when
you look at the example. It can reduce the amount of data you have to move,
and from what I remember from when I worked with video, it produces much
more predictable (and compressible) stream of bits for the next compression
scheme along (variable length encoding, or arithmetic encoding in the case
of H.264) - I've not looked into the details but could probably improve the
compression of the stream you get through gzip.

Regards,

Alex


On Fri, Jan 17, 2014 at 10:14 AM, Richard Fabian <[email protected]> wrote:

> I would question this assumption:
>>
>> This is too much for sending over the network regularly as part of a save.
>>
>>
>>
>
> Well, we've got our play-through logs showing how much data was being sent
> per day per user, and this part of the save was the bit being updated the
> most. Over a day of play it was adding up to about 5mb I think (can't
> remember precisely now) and this made it into the top three we needed to
> compress better to reduce the client bandwidth cost (mobile carrier data
> limits and all that).
>
>
>
>> If I had to compress the data you talk about, I might want to look into
>> some implicit representation, like a quad tree with filled/not nodes.
>> Something like:
>> "Does the current sub-area have entities? If not, store 0, and terminate.
>> Else store 1. If the size of the sub-area is greater than one, subdivide,
>> and recurse for each sub-quadrant."
>> Depending on how clustered the entities are, this may compress well or
>> poorly (but with a max 7% fill rate, it ought to at least compress
>> somewhat.)
>>
>
> I had thought about a quad tree, but I think I chose to not go that way
> because my previous experience with them was that they're not quite as
> efficient in practice as the should be. I can't remember why I think this,
> but I remember working through some code and thinking something along the
> lines of "Oh, yeah. Of course" but that might have been because the data
> involved wasn't quite as clumpy.
>
>
>> Apply gzip on top of any encoding you come up with for possible bonus
>> gains.
>>
>> that's part of the network layer, so no point in doing it explicitly.
>
>
>> Sincerely,
>>
>> jw
>>
>>
>> Thanks, I might try the quad tree idea again.
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

--047d7ba97e649a65d704f02e6031
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Its on the fringe of being useful, but one thing you could=
 look at to reduce your data size is Exponential Golomb coding (<a href=3D"=
http://en.wikipedia.org/wiki/Exponential-Golomb_coding">http://en.wikipedia=
.org/wiki/Exponential-Golomb_coding</a>), its used in H.264 entropy encodin=
g among other things.<div>
<br></div><div>Instead of writing a full n-bit values for every number you =
store, it produces a bit stream of codes, using far less bits for small num=
bers - take a look at the wiki page, its pretty simple to see whats going o=
n when you look at the example. It can reduce the amount of data you have t=
o move, and from what I remember from when I worked with video, it produces=
 much more predictable (and compressible) stream of bits for the next compr=
ession scheme along (variable length encoding, or arithmetic encoding in th=
e case of H.264) - I&#39;ve not looked into the details but could probably =
improve the compression of the stream you get through gzip.<div>
<br></div><div>Regards,</div><div><br></div><div>Alex</div></div></div><div=
 class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Fri, Jan 17, 2=
014 at 10:14 AM, Richard Fabian <span dir=3D"ltr">&lt;<a href=3D"mailto:ras=
[email protected]" target=3D"_blank">[email protected]</a>&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extra">=
<div class=3D"gmail_quote"><div class=3D"im"><blockquote class=3D"gmail_quo=
te" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-col=
or:rgb(204,204,204);border-left-style:solid;padding-left:1ex">


<div dir=3D"ltr">I would question this assumption:<div><div><br></div><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-=
width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;paddin=
g-left:1ex">



<span style=3D"font-family:arial,sans-serif;font-size:12.800000190734863px"=
>This is too much for sending over the network regularly as part of a save.=
</span></blockquote><div><span style=3D"color:rgb(34,34,34)">=A0</span></di=
v>


</div></div></blockquote><div><br></div></div><div><div class=3D"gmail_quot=
e">Well, we&#39;ve got our play-through logs showing how much data was bein=
g sent per day per user, and this part of the save was the bit being update=
d the most. Over a day of play it was adding up to about 5mb I think (can&#=
39;t remember precisely now) and this made it into the top three we needed =
to compress better to reduce the client bandwidth cost (mobile carrier data=
 limits and all that).</div>


</div><div class=3D"im"><div><br></div><div>=A0</div><blockquote class=3D"g=
mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-=
left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div =
dir=3D"ltr">
<div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348=
63px">If I had to compress the data you talk about, I might want to look in=
to some implicit representation, like a quad tree with filled/not nodes. So=
mething like:</span></div>



<div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348=
63px">&quot;Does the current sub-area have entities? If not, store 0, and t=
erminate. Else store 1. If the size of the sub-area is greater than one, su=
bdivide, and recurse for each sub-quadrant.&quot;</span></div>



<div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348=
63px">Depending on how clustered the entities are, this may compress well o=
r poorly (but with a max 7% fill rate, it ought to at least compress somewh=
at.)</span></div>


</div></blockquote><div><br></div></div><div>I had thought about a quad tre=
e, but I think I chose to not go that way because my previous experience wi=
th them was that they&#39;re not quite as efficient in practice as the shou=
ld be. I can&#39;t remember why I think this, but I remember working throug=
h some code and thinking something along the lines of &quot;Oh, yeah. Of co=
urse&quot; but that might have been because the data involved wasn&#39;t qu=
ite as clumpy.=A0</div>
<div class=3D"im">

<div>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px=
 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left=
-style:solid;padding-left:1ex"><div dir=3D"ltr"><div><span style=3D"font-fa=
mily:arial,sans-serif;font-size:12.800000190734863px"></span></div>


<div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348=
63px">Apply gzip on top of any encoding you come up with for possible bonus=
 gains.</span></div>
<div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348=
63px"><br></span></div></div></blockquote></div><div>that&#39;s part of the=
 network layer, so no point in doing it explicitly.</div><div>=A0</div><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left=
-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;paddi=
ng-left:1ex">


<div dir=3D"ltr"><div><span style=3D"font-family:arial,sans-serif;font-size=
:12.800000190734863px"></span></div><div><span style=3D"font-family:arial,s=
ans-serif;font-size:12.800000190734863px">Sincerely,</span></div><div><span=
 style=3D"font-family:arial,sans-serif;font-size:12.800000190734863px"><br>



</span></div><div><span style=3D"font-family:arial,sans-serif;font-size:12.=
800000190734863px">jw</span></div><div><span style=3D"font-family:arial,san=
s-serif;font-size:12.800000190734863px"><br></span></div><div><br></div></d=
iv>


</blockquote><div>Thanks, I might try the quad tree idea again.=A0</div></d=
iv>
</div></div>
<br>-----------------------------------------------------------------------=
-------<br>
CenturyLink Cloud: The Leader in Enterprise Cloud Services.<br>
Learn Why More Businesses Are Choosing CenturyLink Cloud For<br>
Critical Workloads, Development Environments &amp; Everything In Between.<b=
r>
Get a Quote or Start a Free Trial Today.<br>
<a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D119420431&amp;iu=
=3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam=
pad/clk?id=3D119420431&amp;iu=3D/4140/ostg.clktrk</a><br>__________________=
_____________________________<br>

GDAlgorithms-list mailing list<br>
<a href=3D"mailto:[email protected]">GDAlgorithms-lis=
[email protected]</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" =
target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms=
-list</a><br>
Archives:<br>
<a href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgo=
rithms-list" target=3D"_blank">http://sourceforge.net/mailarchive/forum.php=
?forum_name=3Dgdalgorithms-list</a><br></blockquote></div><br></div>

--047d7ba97e649a65d704f02e6031--


--===============0340997904334749734==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

------------------------------------------------------------------------------
CenturyLink Cloud: The Leader in Enterprise Cloud Services.
Learn Why More Businesses Are Choosing CenturyLink Cloud For
Critical Workloads, Development Environments & Everything In Between.
Get a Quote or Start a Free Trial Today. 
http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
--===============0340997904334749734==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
--===============0340997904334749734==--