wgtmac commented on code in PR #55449:
URL: https://github.com/apache/arrow/pull/55449#discussion_r4546948760
##########
cpp/src/arrow/util/alp/alp_sampler_internal.h:
##########
@@ -34,7 +34,7 @@ namespace arrow::util::alp {
template <AlpFloatingType T>
class ARROW_EXPORT AlpSampler {
public:
- AlpSampler() = default;
+ explicit AlpSampler(int64_t sampling_window_size);
Review Comment:
To clarify, there are already some differences between our implementation
and the paper. The paper samples directly from encoding vectors of 1024 values.
Our implementation introduces separate sampling chunks of 4096 values and
samples only their first 1024 values. We also use up to 256 samples in both
sampling levels rather than 32, and a 122880-value window rather than the
paper’s 100 × 1024 = 102400-value row group. In addition, the paper seems to
buffer all 102400 values for both sampling and encoding, which seems
unrealistic in real production case.
------
**I used AI to help summarize the paper approach as below and have
proof-read it.**
The paper motivates two-level sampling because only a few parameter pairs
work well across the vectors in a dataset. In its evaluation, each row group
contains 100 vectors [1], each containing 1,024 values [2]. The first level
samples 32 values from each of eight equidistant vectors, finds a winning pair
for each sampled vector, and retains up to five frequently winning pairs [3].
When multiple candidates remain, the second level samples 32 values per vector
to choose among them, stopping after two consecutive non-improvements. The
selected pair encodes the entire vector [4]. The sampling counts were
experimentally tuned [5].
References to https://ir.cwi.nl/pub/33334/33334.pdf
- **[1] Page 8, “Sampling Parameters”:** The 100-vector grouping emulates
“modern OLAP engines row-group sizes”.
- **[2] Page 8, same paragraph:** The 1,024-value vector size is chosen to
“fit in the CPU cache”.
- **[3] Page 7, §3.2:** Sampling uses “equidistant values” from “equidistant
vectors”, retaining combinations that “appeared the most”. The counts are
specified on page 8.
- **[4] Page 7, §3.2:** Early exit follows “two consecutive combinations”
that fail to improve on the current best.
- **[5] Page 8, “Sampling Parameters”:** The sampling counts “were tuned
during evaluation” to balance compression ratio and speed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
