Hi Paul,
This is a good question. The two methods, i.e., VSE and AFOR, are very
similar. The two methods can be considered as an extension of FOR to
make it less sensitive to outliers by adapting the encoding to the value
distribution. To achieve this, the two methods are encoding a list of
values by
- partitioning it into "frames" (or sequence of consecutive integers) of
variable lengths,
- encoding each frame using a different "bit frame" (the minimum number
of bits required to encode any integer in the frame, and still be able
to distinguish them)
- relying on algorithms to automatically fi nd a good list partitioning.
Apart from the minor differences in the implementation design (that I
will discuss later), the main difference is that VSE is optimised for
achieving a high compression rate and a fast decompression but
disregards the efficiency of compression, while AFOR is optimised for
achieving a high compression rate, a fast decompression but also a fast
compression speed. VSE is using a Dynamic Programming method to find the
*optimal partitioning* of a list (optimal in term of compression rate).
While this approach provides a higher compression rate than the one
proposed in AFOR, the complexity of such a partitioning algorithm is O(n
* k), with the term n being the number of values and the term k the size
of the larger frame, which might greatly impact the compression
performance. In AFOR, we use instead a local optimisation algorithm that
is less effective in term of compression rate but faster to compute.
In term of implementation details, there is a few differences.
1) VSE allows frames of length 1, 2, 4, 6, 8, 12, 16 and 32. The current
implementation of AFOR restrict the length of a frame to be a multiple
of 8 to to be aligned with the start and end of a byte boundary (and
also to minimise the number of loop-unrolled highly-optimised routines).
More precisely, AFOR-2 use three frame lengths: 8, 16 and 32.
2) To allow the *optimal partitioning* of a list, the original
implementation of VSE needs to operate on the full list. On the
contrary, AFOR has been developed to operate on small subsets of the
list, so that AFOR can be applied during incremental construction of the
compressed list (it does not require the full list, but works on small
block of 32 or more integers). However, we can think of applying VSE on
small subset, as in AFOR. In this case, VSE does not compute the optimal
partition of a list, but only the optimal partition of the subset of the
list.
VSE and AFOR encodes a frame in a similar way: first, a header (1 byte)
which provides the bit frame and the frames length, then the encoded frame.
So, as you can see, in essence, the two models are very similar. For the
background, I know well Fabrizio Silvestri (co-author of VSE), and he
was my PhD thesis examiner (the AFOR compression scheme is a chapter of
my thesis). The funny thing is that we come up with these two models at
the same time, this summer, without knowing we were working on something
similar ;o). However, he was more lucky than I am to publish his
findings before me.
I hope this answers to your question.
Feel free to ask if you have any other questions,
Regards,
--
Renaud Delbru
On 24/01/11 22:02, Paul Elschot wrote:
Any idea on how this compares to the vector split encoding here:
http://puma.isti.cnr.it/publichtml/section_cnr_isti/cnr_isti_2010-TR-016.html
?
Regards,
Paul Elschot
On Monday 24 January 2011 19:32:44 Renaud Delbru (JIRA) wrote:
Adaptive Frame Of Reference
----------------------------
Key: LUCENE-2886
URL: https://issues.apache.org/jira/browse/LUCENE-2886
Project: Lucene - Java
Issue Type: New Feature
Components: Codecs
Reporter: Renaud Delbru
Fix For: 4.0
We could test the implementation of the Adaptive Frame Of Reference [1] on the
lucene-4.0 branch.
I am providing the source code of its implementation. Some work needs to be
done, as this implementation is working on the old lucene-1458 branch.
I will attach a tarball containing a running version (with tests) of the AFOR
implementation, as well as the implementations of PFOR and of Simple64 (simple
family codec working on 64bits word) that has been used in the experiments in
[1].
[1] http://www.deri.ie/fileadmin/documents/deri-tr-afor.pdf
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
