Re: sparse bitset compression

--===============2354681233288200124==
Content-Type: multipart/alternative; boundary=001a1135ec942c832204f027d199

--001a1135ec942c832204f027d199
Content-Type: text/plain; charset=ISO-8859-1

>
> 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.

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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><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">I would question this assumption:<div class=3D"im"><div><b=
r></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">


<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 class=3D"gmail_quote">Wel=
l, we&#39;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&#39;t r=
emember precisely now) and this made it into the top three we needed to com=
press better to reduce the client bandwidth cost (mobile carrier data limit=
s and all that).</div>

</div><div><br></div><div>=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20=
4,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.800000190734863px"=
>If I had to compress the data you talk about, I might want to look into so=
me implicit representation, like a quad tree with filled/not nodes. Somethi=
ng 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>I had thought about a quad tree, but=
 I think I chose to not go that way because my previous experience with the=
m was that they&#39;re not quite as efficient in practice as the should be.=
 I can&#39;t remember why I think this, but I remember working through some=
 code and thinking something along the lines of &quot;Oh, yeah. Of course&q=
uot; but that might have been because the data involved wasn&#39;t quite as=
 clumpy.=A0</div>

<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>that&#39;s part of the netwo=
rk layer, so no point in doing it explicitly.</div><div>=A0</div><blockquot=
e 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-lef=
t: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>

--001a1135ec942c832204f027d199--


--===============2354681233288200124==
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
--===============2354681233288200124==
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
--===============2354681233288200124==--