VSEncoding - int codec faster than p4delta

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

VSEncoding - int codec faster than p4delta

Andrzej Białecki-2
Hi,

I found this paper recently published in proceedings of CIKM'10:

VSEncoding: efficient coding and fast decoding of integer lists via
dynamic programming, F. Silvestri, R. Venturini

Available here http://portal.acm.org/citation.cfm?id=1871437.1871592

My favorite quotes:

"We point out that only our methods, together with In-
terpolative, are able to beat the entropy of the lists on the
datasets. This quasi-paradoxical e ect is, indeed, present
because entropy does not consider context information. En-
tropy, or to use a notation commonly used in text compres-
sion, zeroth-order entropy, does not take into account pat-
terns (i.e. the context) that can be present in lists of blocks
of integers. By grouping together blocks of integers, in fact,
we are able to assign codewords to more than a single value
at a time. Therefore, it appears obvious that we can beat
the entropy in the case of VSE, VSE-R and Interpolative. Es-
sentially, this is possible since we exploit regularities on the
lists on these very skewed d-gaps lists (e.g., small values close
to each other or quite long runs of 1s). We remark that beat
the entropy is not possible with any pre x code (e.g., sta-
tistical compressors like Arithmetic and Hu man or integer
encoders like , , 's, Golomb, and so on). Therefore, our
methods is certainly better in compression than any of these
kind of methods without the need of any comparison. Any-
way, for the sake of completeness, we report those results as
well in Table 3."

"As expected, Interpolative is the slowest as opposed to VSE
which tops others with more than 800 millions of integers
per second. Our methods, VSE and VSE-R, are among the
fastest in decoding with a number of mis (millions of integers per
second) decoded ranging from 450 of VSE-R to 835 of
VSE both of them measured using the gov2 collection. It
is interesting to observe the better performance in terms
of decoding speed of VSE with respect to others, and in
particular with respect to OPT-P4D, Simple9 and Simple16
which are considered state-of-the-art as far as decompression
speed is concerned."

P4D compression achieved a speed of 460 mis in this test, which means
the VSE method is twice as fast.

--
Best regards,
Andrzej Bialecki     <><
 ___. ___ ___ ___ _ _   __________________________________
[__ || __|__/|__||\/|  Information Retrieval, Semantic Web
___|||__||  \|  ||  |  Embedded Unix, System Integration
http://www.sigram.com  Contact: info at sigram dot com


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: VSEncoding - int codec faster than p4delta

Paul Elschot
Op woensdag 27 oktober 2010 11:27:51 schreef Andrzej Bialecki:
> Hi,
>
> I found this paper recently published in proceedings of CIKM'10:
>
> VSEncoding: efficient coding and fast decoding of integer lists via
> dynamic programming, F. Silvestri, R. Venturini
>
> Available here http://portal.acm.org/citation.cfm?id=1871437.1871592

A search for "VSEncoding" (with quotes) showed that the paper is currently also available via:

http://puma.isti.cnr.it/publichtml/section_cnr_isti/cnr_isti_2010-TR-016.html

That page refers to this open access pdf version:
(the url should be on single line, sorry for the format here)

http://puma.isti.cnr.it/download.php?DocFile=2010-TR-016.pdf&langver=it&idcode=2010-TR-016&authority=cnr.isti&collection=cnr.isti&check=

A very interesting read indeed, thanks.

Regards,
Paul Elschot

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: VSEncoding - int codec faster than p4delta

Michael McCandless-2
This sounds fabulous!

FOR/PFOR already show great gains for me over standard codec... if we
can do even better, that's awesome.

Mike

On Wed, Oct 27, 2010 at 10:36 AM, Paul Elschot <[hidden email]> wrote:

> Op woensdag 27 oktober 2010 11:27:51 schreef Andrzej Bialecki:
>> Hi,
>>
>> I found this paper recently published in proceedings of CIKM'10:
>>
>> VSEncoding: efficient coding and fast decoding of integer lists via
>> dynamic programming, F. Silvestri, R. Venturini
>>
>> Available here http://portal.acm.org/citation.cfm?id=1871437.1871592
>
> A search for "VSEncoding" (with quotes) showed that the paper is currently also available via:
>
> http://puma.isti.cnr.it/publichtml/section_cnr_isti/cnr_isti_2010-TR-016.html
>
> That page refers to this open access pdf version:
> (the url should be on single line, sorry for the format here)
>
> http://puma.isti.cnr.it/download.php?DocFile=2010-TR-016.pdf&langver=it&idcode=2010-TR-016&authority=cnr.isti&collection=cnr.isti&check=
>
> A very interesting read indeed, thanks.
>
> Regards,
> Paul Elschot
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: VSEncoding - int codec faster than p4delta

Robert Muir
On Wed, Oct 27, 2010 at 11:12 AM, Michael McCandless
<[hidden email]> wrote:
> This sounds fabulous!
>
> FOR/PFOR already show great gains for me over standard codec... if we
> can do even better, that's awesome.
>

good thing Mike spent(present tense too!) all that work on the whole
flexible indexing thing :)

Really, seeing stuff like this shows it was the right thing to do.

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]