Pith. sign in

REVIEW 5 major objections 6 minor 1 cited by

Learned Data Compression: Challenges and Opportunities for the Future

T0 review · 5 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A learned compressor with SIMD decodes integers at 6.5 GiB/s, beating classic codecs.

desk verdict A useful vision paper built on a headline benchmark that is currently unverifiable; the underlying ideas are solid but the key speedup claim needs missing implementation details before it can be trusted. read the letter →

arxiv 2412.10770 v1 pith:FTRSBKR7 submitted 2024-12-14 cs.DB cs.IR

Qiyu Liu , Siyuan Han , Jianwei Liao , Jin Li , Jingshu Peng , Jun Du , Lei Chen This is my paper · ORCID
classification cs.DBcs.IR
keywords learnedcompressionintegerpiecewiselinearapproximationSIMDinvertedindexdatadatabasesystems
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Learned data compression replaces hand-tuned integer codecs with a small machine-learned model that predicts each key's position, storing only tiny residuals. The paper argues that this approach, once dismissed as slower than classic methods, can actually beat them: its SIMD-optimized implementation decodes 53 GiB of web corpus document IDs at 6.535 GiB/s, faster than QMX, Variable-Byte, OptP4Delta, and BIC while matching their compression ratio. This makes learned compression a plausible foundation for database and search workloads, not just a research curiosity. The paper is a vision statement: it sketches how learned compressors already enable faster inverted-index pruning, quantile queries, KV-store compression, and vector-codebook compression, and lays out the main obstacles to production use.

What carries the argument

The central object is the error-bounded piecewise linear approximation ($\epsilon$-PLA) learned compressor. It fits $L$ line segments $f(i)$ to the sorted key list $K$ such that $|K[i] - \lfloor f(i)\rfloor| \le \epsilon$ for every $i$, then stores $K_c = (f, \Delta)$, where each residual $\Delta[i] = K[i] - \lfloor f(i)\rfloor$ needs only $\lceil \log_2(2\epsilon+1)\rceil$ bits. Decoding is $K[i] = \lfloor f(i)\rfloor + \Delta[i]$, so decompression is a sequence of fused-multiply-add evaluations plus residual additions. lc-simd is the same scheme but with SIMD-aware optimizations—task decomposition, operator fusion, and memory alignment—that make those evaluations vectorize across keys. The paper also uses the dual relation with learned indexes: compression learns the inverse CDF (index-to-key), whereas learned indexes learn the CDF (key-to-index).

What would settle it

Run the same lc-simd implementation and the listed baselines on several datasets with per-codec parameter tuning and report wall-clock decompression with error bars; if the speedup over QMX or OptP4Delta drops below 1x on any representative workload, the headline claim fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that a learned compressor, built from an error-bounded piecewise linear model plus a residual array, can serve as a new foundation for high-performance integer compression. As evidence, it reports that lc-simd—la-vector with SIMD-aware optimization—achieves 6.535 GiB/s decompression throughput on the CCNews corpus at 8.841 bits per integer, which is 18.254x, 2.316x, 2.333x, and 1.298x faster than BIC, OptP4Delta, Variable-Byte, and QMX, at a compression ratio comparable to those baselines. The authors generalize from this benchmark to assert that learned compression is no longer dominated by conventional CPU codecs and that system builders should consider replacing them. The paper then derives concrete application benefits: natural segment-level pruning in inverted index intersection, quantile and median queries in $O(\log(N/\epsilon^2))$ time, a 12.26x throughput advantage over LevelDB's Snappy, and a path toward compressing vector-quantization codebooks.

Load-bearing premise

The benchmark is fair and representative: the classic codecs were optimally configured and tuned, the CCNews corpus reflects real inverted-index workloads, and lc-simd was not overfit to that dataset.

Editorial extensions

If this is right

  • In inverted indexes, each PLA segment carries its key range, so list intersection and union get pruning for free; skip pointers become unnecessary for learned-compressed posting lists.
  • In KV stores, replacing byte-stream codecs like Snappy with a learned compressor cuts decompression cost: the reported 6.535 GiB/s is 12.26x LevelDB's Snappy throughput, with better compression of integer key blocks.
  • Quantile and median queries become cheap: exact evaluation costs $O(\log(N/\epsilon^2))$ time after $O(N/\epsilon^2 + N \log \epsilon)$ space, and dropping residuals gives an approximate quantile sketch bounded by $\epsilon$.
  • Learned compressors can play the role of a Bloom filter in distributed joins: a compact learned summary of the join attribute can filter tuples before shipping, though distribution-dependent behavior may call for a hybrid with Bloom filters.
  • Studying learned compression and learned indexes as dual problems means advances on either side (better model families, tighter error bounds, update strategies) can transfer directly to the other.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the single-dataset benchmark generalizes, I would expect learned compression to become a default for sorted integer lists in analytical engines, with codec APIs exposing segment metadata for pruning and quantile queries.
  • The BitTuner closed form assumes i.i.d. key gaps; a likely refinement is per-segment adaptive epsilon selection, which the graph-partitioning sketch in the paper makes concrete.
  • The reported speedup is CPU-only; extending lc-simd to GPU SIMT and Tensor Cores could widen the gap further, but mixed-precision numerical errors will need handling first.
  • A direct transfer test: take any learned-index model (e.g., a hierarchical RMI) and invert it; the paper's duality suggests that would give a new compression codec, but that remains unverified here.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 6 minor

Summary. This vision paper argues that learned integer compressors, specifically error-bounded piecewise-linear-approximation (PLA) models, can become a new foundation for high-performance integer compression in database and information-retrieval systems. The central supporting evidence is a preliminary benchmark in Section II-C on the CCNews inverted-index dataset, where a SIMD-optimized learned compressor (lc-simd) reaches 6.535 GiB/s decompression throughput, which the authors report as 18.254x, 2.316x, 2.333x, and 1.298x faster than BIC, OptP4Delta, Variable-Byte, and QMX respectively, with 8.841 bits/int average compressed size. The paper then sketches possible applications in inverted-index compression, LSM-based key-value stores, quantile queries, vector-database codebooks, and storage mapping tables, and it closes with technical challenges such as epsilon tuning, dynamic updates, model selection, floating-point extension, and hardware acceleration.

Significance. If the benchmark results are robust and reproducible, the paper identifies a genuinely important direction: SIMD-friendly learned compression has the potential to compete with decades-old inverted-index codecs on both speed and space. The paper's strengths include a clear formalization of the learned-compression setup, an explicit complexity comparison for quantile queries (Table I), and a thoughtful enumeration of open problems such as adaptive epsilon selection and update handling. However, the central empirical claim is currently under-specified and internally inconsistent in places, and several application claims rest on comparisons that are not apples-to-apples. Because the paper's thesis is explicitly built on the preliminary benchmark, these issues are load-bearing and must be addressed before the vision statement can be accepted.

major comments (5)
  1. [Section II-C, Figure 3] The benchmark setup is not sufficiently specified to support the headline throughput claim. The paper reports no epsilon value used for lc and lc-simd, gives no configuration or tuning details for any baseline codec, provides no repeated-run statistics or error bars, and evaluates a single dataset (CCNews). The statement that "Results on other datasets exhibit similar trends" is asserted without supporting data. Since the authors themselves note in Section IV-A that learned-compressor cost depends on key-gap variance, a single favorable dataset cannot establish generality. Please report the epsilon settings, baseline parameters (e.g., block sizes and optimization targets), hardware details beyond the CPU model, and results on at least one or two additional datasets, or temper the generalization claim accordingly.
  2. [Section I vs. Section II-C] The reported speedup against OptP4Delta is internally inconsistent: Section I states lc-simd is 1.68x faster than OptP4Delta, while Section II-C reports 2.316x. From the table, 6.535/2.822 = 2.316 for the row labeled optpfor, whereas 6.535/3.881 = 1.684 matches the row labeled opt-vbyte. It appears the Introduction may have confused OptP4Delta with opt-vbyte. This discrepancy undermines confidence in the precision of the benchmark reporting and must be corrected and reconciled.
  3. [Section II-C, Figure 3a] The claim that lc-simd achieves a "comparable" compression ratio is overstated relative to several baselines. In Figure 3a, lc-simd uses 8.841 bits/int, which is 19.7% worse than BIC (7.384 bits/int) and 6.5% worse than OptP4Delta (8.301 bits/int); it is comparable only to the faster SIMD-oriented codecs such as opt-vbyte (8.983) and QMX (9.701). Since the paper uses the combination of ratio and speed to argue that learned compression can replace existing methods, please qualify the claim as applying to SIMD-optimized baselines and discuss whether the extra space is acceptable for the target workloads.
  4. [Section III-B] The comparison between lc-simd and Snappy is not apples-to-apples. The paper cites a 546 MB/s decompression throughput for Snappy in LevelDB and a 6.535 GiB/s throughput for lc-simd (12.26x) without controlling for data type, compression ratio, or workload; Snappy operates on arbitrary byte streams in a KV-store setting, while lc-simd compresses sorted integer document IDs. The sentence also claims a "much better compression ratio" without presenting any ratio measurement for Snappy on the same data. Please either provide a controlled comparison on the same input and task or clearly frame the numbers as illustrative back-of-the-envelope figures rather than benchmark evidence.
  5. [Section IV-A and Section II-A] The paper relies on BitTuner [41] for the closed-form optimal epsilon, but the cited resource is a GitHub repository rather than a peer-reviewed publication, and no derivation or evaluation of the formula is included. Since the choice of epsilon directly determines the reported compression ratio, the benchmark is not reproducible without knowing how epsilon was selected. Please cite a published source or provide the derivation, and state explicitly how epsilon was chosen for the experiments.
minor comments (6)
  1. [Section II-C, Table 3a] The table uses the row label "optpfor" while the text refers to "OptP4Delta"; please unify the naming and verify that the cited reference [18] is indeed the method measured.
  2. [Section I, Definition 1] The compression ratio is defined as size(Kc)/size(K), which is a fraction, but the benchmark table reports average bits/int; please make the connection between the two metrics explicit.
  3. [Section III-C, after Table I] The sentence "Additionally, it would be interesting to integrate the learned structures with conventional data summary techniques designed for AQP [55]" ends without a substantive continuation; please complete the thought or remove the dangling text.
  4. [Figure 4] The figure contains typos: "Rnage" should be "Range" and the second panel's "Possible Rnage" should be "Possible Range".
  5. [References] The reference for LZ4 ("Etremely fast compression") contains a typo and should be "Extremely fast compression"; also, the GitHub link for SALAD [45] points to a temporary branch and should be updated to a stable, archival location.
  6. [Section II-C] The paper states that all methods were compiled with g++ -O3 and auto-vectorization enabled, but it does not report compiler version, SIMD ISA flags (e.g., AVX2/AVX-512), or whether the baselines were built from their recommended configurations; adding this information would improve reproducibility.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the headline result is an empirical benchmark, and the author-cited theory is background rather than a derivation forcing the measured speedup.

full rationale

The paper's central claim is an empirical benchmark in Section II-C (Figure 3): the SIMD-optimized learned compressor lc-simd is reported to reach 6.535 GiB/s on CCNews, with concrete throughput and compression-ratio numbers, a stated hardware setup, and comparisons to external baselines from the inverted-index compression literature. The measured results are not derived from the paper's own equations: the ϵ-PLA encoding Kc = (f, Δ) and the residual bit-width formula are standard definitions, and the benchmark could in principle be reproduced or falsified externally. The author-connected references are [40] (same-group arXiv paper on learned-index effectiveness), [41] (BitTuner repository), and [45] (SALAD repository). These are used as background pointers: BitTuner's optimal-epsilon formula is presented as a tuning insight rather than used to compute the benchmark outcome, and SALAD is cited only for SIMD implementation details. No equation in the paper reduces to the claimed speedup by construction, and no fitted parameter is renamed as a prediction. The reproducibility concerns noted by the reader -- one dataset, no reported epsilon, no baseline tuning details, and the inconsistent 1.68x vs. 2.316x speedup over OptP4Delta -- are correctness, fairness, and verifiability risks, not circularity. Under the strict definition requiring a specific reduction or definitional equivalence, no circular step is exhibited, so the score is low.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central benchmark depends mainly on the data being amenable to PLA approximation; the theoretical performance arguments rely on prior results from the same and other groups. No new theoretical entities are introduced.

free parameters (1)
  • error bound epsilon for learned compressor = not reported
    Controls the trade-off between model size and residual size (Section II-A). The benchmark does not state the epsilon used for lc and lc-simd, so the reported compression ratio and throughput may be contingent on a favorable choice.
assumptions (3)
  • domain assumption Sorted integer lists in the target workloads can be approximated by an error-bounded piecewise linear function with few segments.
    If this fails, the segment count or residuals explode and learned compression has no benefit. This is the core data distribution assumption behind Section II and the benchmark.
  • domain assumption The theoretical space-time complexity results and the optimal-epsilon formula from [28], [31], [40], [41] are correct.
    The paper uses Table I and the Bopt formula to argue for query support and hyper-parameter tuning; these are cited, not proven or re-derived in this paper.
  • standard math O'Rourke's online algorithm [39] computes a minimal-segment epsilon-PLA in linear time.
    Assumed as a standard algorithmic fact; used implicitly in the encoding and in the complexity statements.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learned Data Compression: Challenges and Opportunities for the Future." pith.science (2026). https://pith.science/paper/FTRSBKR7

@misc{pith2026241210770,
  author       = {Pith},
  title        = {Pith review of: Learned Data Compression: Challenges and Opportunities for the Future},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FTRSBKR7}},
  note         = {Machine review of arXiv:2412.10770}
}
read the original abstract

Compressing integer keys is a fundamental operation among multiple communities, such as database management (DB), information retrieval (IR), and high-performance computing (HPC). Recent advances in \emph{learned indexes} have inspired the development of \emph{learned compressors}, which leverage simple yet compact machine learning (ML) models to compress large-scale sorted keys. The core idea behind learned compressors is to \emph{losslessly} encode sorted keys by approximating them with \emph{error-bounded} ML models (e.g., piecewise linear functions) and using a \emph{residual array} to guarantee accurate key reconstruction. While the concept of learned compressors remains in its early stages of exploration, our benchmark results demonstrate that an SIMD-optimized learned compressor can significantly outperform state-of-the-art CPU-based compressors. Drawing on our preliminary experiments, this vision paper explores the potential of learned data compression to enhance critical areas in DBMS and related domains. Furthermore, we outline the key technical challenges that existing systems must address when integrating this emerging methodology.

Figures

Figures reproduced from arXiv: 2412.10770 by the authors.

Figure 1
Figure 1. (left) Illustration of the disproportionate growth be [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. A toy example of learned integer compressor based on an error-bounded PLA model. [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Preliminary benchmark results for the original learned compressor implementation [28] ( [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: (a) Skip pointers in conventional inverted index designs. [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]
Figure 5
Figure 5. Figure 5: Illustration of a vector quantizer (VQ). When product [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: A graph model of the key partition problem. The path in [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
Figure 7
Figure 7. Figure 7: Illustration of the GPU architecture characteristics. [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis

    cs.DB 2025-06

Reference graph

Works this paper leans on

88 extracted references · 71 canonical work pages · cited by 1 Pith paper

  1. [41]

    BitTuner,

    “BitTuner,” https://github.com/qyliu-hkust/BitTuner, accessed: 2024-10- 20

    work page 2024

  2. [1]

    The big challenges of big data,

    V . Marx, “The big challenges of big data,” Nature, vol. 498, no. 7453, pp. 255–260, 2013

    2013

  3. [2]

    Big data, but are we ready?

    O. Trelles, P. Prins, M. Snir, and R. C. Jansen, “Big data, but are we ready?” Nature Reviews Genetics , vol. 12, no. 3, pp. 224–224, 2011

    2011

  4. [3]

    Mobile computing: the next decade,

    M. Satyanarayanan, “Mobile computing: the next decade,” ACM SIG- MOBILE Mobile Computing and Communications Review, vol. 15, no. 2, pp. 2–10, 2011

    2011

  5. [4]

    Computation offloading toward edge computing,

    L. Lin, X. Liao, H. Jin, and P. Li, “Computation offloading toward edge computing,” Proceedings of the IEEE , vol. 107, no. 8, pp. 1584–1607, 2019

    2019

  6. [5]

    RocksDB,

    “RocksDB,” https://rocksdb.org/, accessed: 2024-10-20

    2024

  7. [6]

    Lsm-based storage techniques: a survey,

    C. Luo and M. J. Carey, “Lsm-based storage techniques: a survey,” The VLDB Journal, vol. 29, no. 1, pp. 393–418, 2020

    2020

  8. [7]

    M. T. ¨Ozsu, P. Valduriez et al. , Principles of distributed database systems. Springer, 1999, vol. 2

    1999

Show all 88 references
  1. [8]

    Comet: An active distributed {Key-Value} store,

    R. Geambasu, A. A. Levy, T. Kohno, A. Krishnamurthy, and H. M. Levy, “Comet: An active distributed {Key-Value} store,” in 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10), 2010

    2010

  2. [9]

    Techniques for inverted index compres- sion,

    G. E. Pibiri and R. Venturini, “Techniques for inverted index compres- sion,” ACM Computing Surveys (CSUR), vol. 53, no. 6, pp. 1–36, 2020

    2020

  3. [10]

    Survey of vector database management systems,

    J. J. Pan, J. Wang, and G. Li, “Survey of vector database management systems,” The VLDB Journal , vol. 33, no. 5, pp. 1591–1615, 2024

    2024

  4. [11]

    Universal codeword sets and representations of the integers,

    P. Elias, “Universal codeword sets and representations of the integers,” IEEE transactions on information theory , vol. 21, no. 2, pp. 194–203, 1975

    1975

  5. [12]

    Run-length encodings (corresp.),

    S. Golomb, “Run-length encodings (corresp.),” IEEE transactions on information theory, vol. 12, no. 3, pp. 399–401, 1966

    1966

  6. [13]

    A compression method for clustered bit-vectors,

    J. Teuhola, “A compression method for clustered bit-vectors,” Informa- tion processing letters , vol. 7, no. 6, pp. 308–311, 1978

    1978

  7. [14]

    Adaptive variable-length coding for efficient compression of spacecraft television data,

    R. Rice and J. Plaunt, “Adaptive variable-length coding for efficient compression of spacecraft television data,” IEEE Transactions on Com- munication Technology, vol. 19, no. 6, pp. 889–897, 1971

    1971

  8. [15]

    Simd-based decoding of posting lists,

    A. A. Stepanov, A. R. Gangolli, D. E. Rose, R. J. Ernst, and P. S. Oberoi, “Simd-based decoding of posting lists,” in Proceedings of the 20th ACM international conference on Information and knowledge management , 2011, pp. 317–326

    2011

  9. [16]

    Challenges in building large-scale information retrieval systems,

    J. Dean et al., “Challenges in building large-scale information retrieval systems,” in Keynote of the 2nd ACM international conference on web search and data mining (WSDM) , vol. 10, no. 1498759.1498761, 2009

    2009

  10. [17]

    Super-scalar ram- cpu cache compression,

    M. Zukowski, S. Heman, N. Nes, and P. Boncz, “Super-scalar ram- cpu cache compression,” in 22nd International Conference on Data Engineering (ICDE’06). IEEE, 2006, pp. 59–59

    2006

  11. [18]

    Inverted index compression and query processing with optimized document ordering,

    H. Yan, S. Ding, and T. Suel, “Inverted index compression and query processing with optimized document ordering,” in Proceedings of the 18th international conference on World wide web , 2009, pp. 401–410

    2009

  12. [19]

    Efficient storage and retrieval by content and address of static files,

    P. Elias, “Efficient storage and retrieval by content and address of static files,” Journal of the ACM (JACM) , vol. 21, no. 2, pp. 246–260, 1974

    1974

  13. [20]

    Partitioned elias-fano indexes,

    G. Ottaviano and R. Venturini, “Partitioned elias-fano indexes,” in Pro- ceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval , 2014, pp. 273–282

    2014

  14. [21]

    Quasi-succinct indices,

    S. Vigna, “Quasi-succinct indices,” in Proceedings of the sixth ACM international conference on Web search and data mining , 2013, pp. 83– 92

    2013

  15. [22]

    Exploiting clustering in inverted file compres- sion,

    A. Moffat and L. Stuiver, “Exploiting clustering in inverted file compres- sion,” in Proceedings of Data Compression Conference-DCC’96. IEEE, 1996, pp. 82–91

    1996

  16. [23]

    Binary interpolative coding for effective index compression,

    ——, “Binary interpolative coding for effective index compression,” Information Retrieval, vol. 3, pp. 25–47, 2000

    2000

  17. [24]

    A method for the construction of minimum-redundancy codes,

    D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the IRE , vol. 40, no. 9, pp. 1098–1101, 1952

    1952

  18. [25]

    Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding,

    J. Duda, “Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding,” arXiv preprint arXiv:1311.2540 , 2013

    2013 arXiv

  19. [26]

    Arithmetic coding revisited,

    A. Moffat, R. M. Neal, and I. H. Witten, “Arithmetic coding revisited,” ACM Transactions on Information Systems (TOIS) , vol. 16, no. 3, pp. 256–294, 1998

    1998

  20. [27]

    The case for learned index structures,

    T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The case for learned index structures,” in Proceedings of the 2018 international conference on management of data , 2018, pp. 489–504

    2018

  21. [28]

    A learned approach to design compressed rank/select data structures,

    A. Boffa, P. Ferragina, and G. Vinciguerra, “A learned approach to design compressed rank/select data structures,” ACM Transactions on Algorithms (TALG), vol. 18, no. 3, pp. 1–28, 2022

    2022

  22. [29]

    A “learned

    ——, “A “learned” approach to quicken and compress rank/select dictio- naries,” in 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX) . SIAM, 2021, pp. 46–59

    2021

  23. [30]

    The pgm-index: a fully-dynamic com- pressed learned index with provable worst-case bounds,

    P. Ferragina and G. Vinciguerra, “The pgm-index: a fully-dynamic com- pressed learned index with provable worst-case bounds,” Proceedings of the VLDB Endowment , vol. 13, no. 8, pp. 1162–1175, 2020

    2020

  24. [31]

    Why are learned indexes so effective?

    P. Ferragina, F. Lillo, and G. Vinciguerra, “Why are learned indexes so effective?” in International Conference on Machine Learning . PMLR, 2020, pp. 3123–3132

    2020

  25. [32]

    PostgreSQL,

    “PostgreSQL,” https://www.postgresql.org/, accessed: 2024-10-20

    2024

  26. [33]

    “Oracle,” https://www.oracle.com/, accessed: 2024-10-20

    2024

  27. [34]

    Apache Solr,

    “Apache Solr,” https://solr.apache.org/, accessed: 2024-10-20

    2024

  28. [35]

    Elasticsearch: The Official Distributed Search & Analytics Engine,

    “Elasticsearch: The Official Distributed Search & Analytics Engine,” https://www.elastic.co/elasticsearch, accessed: 2024-10-20

    2024

  29. [36]

    Cc-news-en: A large english news corpus,

    J. Mackenzie, R. Benham, M. Petri, J. R. Trippas, J. S. Culpepper, and A. Moffat, “Cc-news-en: A large english news corpus,” in Proc. CIKM, 2020, pp. 3077–3084

    2020

  30. [37]

    Approximate query process- ing: No silver bullet,

    S. Chaudhuri, B. Ding, and S. Kandula, “Approximate query process- ing: No silver bullet,” in Proceedings of the 2017 ACM International Conference on Management of Data , 2017, pp. 511–519

    2017

  31. [38]

    Sketch techniques for approximate query processing,

    G. Cormode, “Sketch techniques for approximate query processing,” Foundations and Trends in Databases. NOW publishers , vol. 15, 2011

    2011

  32. [39]

    An on-line algorithm for fitting straight lines between data ranges,

    J. O’Rourke, “An on-line algorithm for fitting straight lines between data ranges,” Commun. ACM, vol. 24, no. 9, pp. 574–578, 1981

    1981

  33. [40]

    Why are learned indexes so effective but sometimes ineffective?

    Q. Liu, S. Han, Y . Qi, J. Peng, J. Li, L. Lin, and L. Chen, “Why are learned indexes so effective but sometimes ineffective?” arXiv preprint arXiv:2410.00846, 2024

    2024 arXiv

  34. [42]

    Alex: an updatable adaptive learned index,

    J. Ding, U. F. Minhas, J. Yu, C. Wang, J. Do, Y . Li, H. Zhang, B. Chandramouli, J. Gehrke, D. Kossmann et al. , “Alex: an updatable adaptive learned index,” in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data , 2020, pp. 969–984

    2020

  35. [43]

    R. J. Serfling, Approximation theorems of mathematical statistics. John Wiley & Sons, 2009

    2009

  36. [44]

    Modern b-tree techniques,

    G. Graefe et al., “Modern b-tree techniques,” Foundations and Trends® in Databases, vol. 3, no. 4, pp. 203–402, 2011

    2011

  37. [45]

    SALAD: SIMD-Aware Learned Data Compression,

    “SALAD: SIMD-Aware Learned Data Compression,” https: //github.com/qyliu-hkust/salad/tree/PGM-INDEX-SIMD-TEMP, accessed: 2024-10-20

    2024

  38. [46]

    In vacuo and in situ evaluation of simd codecs,

    A. Trotman and J. Lin, “In vacuo and in situ evaluation of simd codecs,” in Proceedings of the 21st Australasian Document Computing Symposium, 2016, pp. 1–8

    2016

  39. [47]

    When prefetching works, when it doesn’t, and why,

    J. Lee, H. Kim, and R. Vuduc, “When prefetching works, when it doesn’t, and why,” ACM Transactions on Architecture and Code Optimization (TACO), vol. 9, no. 1, pp. 1–29, 2012

    2012

  40. [48]

    Modern information retrieval: A brief overview,

    A. Singhal et al. , “Modern information retrieval: A brief overview,” IEEE Data Eng. Bull. , vol. 24, no. 4, pp. 35–43, 2001

    2001

  41. [49]

    The log-structured merge-tree (lsm-tree),

    P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil, “The log-structured merge-tree (lsm-tree),” Acta Informatica, vol. 33, pp. 351–385, 1996

    1996

  42. [50]

    Towards flexibility and robustness of lsm trees,

    A. Huynh, H. A. Chaudhari, E. Terzi, and M. Athanassoulis, “Towards flexibility and robustness of lsm trees,” The VLDB Journal , pp. 1–24, 2024

    2024

  43. [51]

    “Redis,” https://redis.io/, accessed: 2024-10-20

    2024

  44. [52]

    LevelDB,

    “LevelDB,” https://github.com/google/leveldb, accessed: 2024-10-20

    2024

  45. [53]

    Etremely fast compression,

    “Etremely fast compression,” https://lz4.org/, accessed: 2024-06-12

    2024

  46. [54]

    Snappy: A fast compressor/decompressor,

    “Snappy: A fast compressor/decompressor,” https://google.github.io/ snappy/, accessed: 2024-06-12

    2024

  47. [55]

    A survey of approximate quantile computation on large-scale data,

    Z. Chen and A. Zhang, “A survey of approximate quantile computation on large-scale data,” IEEE Access, vol. 8, pp. 34 585–34 597, 2020

    2020

  48. [56]

    Algorithm 65: find,

    C. A. Hoare, “Algorithm 65: find,” Communications of the ACM, vol. 4, no. 7, pp. 321–322, 1961

    1961

  49. [57]

    Theory and network applications of dynamic bloom filters,

    D. Guo, J. Wu, H. Chen, and X. Luo, “Theory and network applications of dynamic bloom filters,” in Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications . Citeseer, 2006, pp. 1–12

    2006

  50. [58]

    Performance-optimal filtering: Bloom overtakes cuckoo at high throughput,

    H. Lang, T. Neumann, A. Kemper, and P. Boncz, “Performance-optimal filtering: Bloom overtakes cuckoo at high throughput,” Proceedings of the VLDB Endowment , vol. 12, no. 5, pp. 502–515, 2019

    2019

  51. [59]

    R* optimizer validation and performance evaluation for local queries,

    L. F. Mackert and G. M. Lohman, “R* optimizer validation and performance evaluation for local queries,” in Proceedings of the 1986 ACM SIGMOD international conference on Management of data , 1986, pp. 84–95

    1986

  52. [60]

    Perf join: An alternative to two-way semijoin and bloomjoin,

    Z. Li and K. A. Ross, “Perf join: An alternative to two-way semijoin and bloomjoin,” in Proceedings of the fourth international conference on Information and knowledge management , 1995, pp. 137–144

    1995

  53. [61]

    Optimizing bloom filter: Challenges, solutions, and comparisons,

    L. Luo, D. Guo, R. T. Ma, O. Rottenstreich, and X. Luo, “Optimizing bloom filter: Challenges, solutions, and comparisons,” IEEE Communi- cations Surveys & Tutorials , vol. 21, no. 2, pp. 1912–1949, 2018

    1912

  54. [62]

    Stable learned bloom filters for data streams,

    Q. Liu, L. Zheng, Y . Shen, and L. Chen, “Stable learned bloom filters for data streams,” Proceedings of the VLDB Endowment, vol. 13, no. 12, pp. 2355–2367, 2020

    2020

  55. [63]

    A model for learned bloom filters and optimizing by sandwiching,

    M. Mitzenmacher, “A model for learned bloom filters and optimizing by sandwiching,” Advances in Neural Information Processing Systems , vol. 31, 2018

    2018

  56. [64]

    Retrieval- augmented generation for knowledge-intensive nlp tasks,

    P. Lewis, E. Perez, A. Piktus, F. Petroni, V . Karpukhin, N. Goyal, H. K ¨uttler, M. Lewis, W.-t. Yih, T. Rockt ¨aschel et al. , “Retrieval- augmented generation for knowledge-intensive nlp tasks,” Advances in Neural Information Processing Systems , vol. 33, pp. 9459–9474, 2020

    2020

  57. [65]

    The high-performance vector database built for scale,

    “The high-performance vector database built for scale,” https://milvus. io/, accessed: 2024-06-12

    2024

  58. [66]

    Pinecone: The vector database to build knowledgeable AI,

    “Pinecone: The vector database to build knowledgeable AI,” https: //www.pinecone.io/, accessed: 2024-06-12

    2024

  59. [67]

    Product quantization for nearest neighbor search,

    H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” IEEE transactions on pattern analysis and machine intelligence, vol. 33, no. 1, pp. 117–128, 2010

    2010

  60. [68]

    Optimized product quantization,

    T. Ge, K. He, Q. Ke, and J. Sun, “Optimized product quantization,” IEEE transactions on pattern analysis and machine intelligence, vol. 36, no. 4, pp. 744–755, 2013

    2013

  61. [69]

    Additive quantization for extreme vector compression,

    A. Babenko and V . Lempitsky, “Additive quantization for extreme vector compression,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , 2014, pp. 931–938

    2014

  62. [70]

    Deltapq: lossless product quantization code compression for high dimensional similarity search,

    R. Wang and D. Deng, “Deltapq: lossless product quantization code compression for high dimensional similarity search,” Proceedings of the VLDB Endowment, vol. 13, no. 13, pp. 3603–3616, 2020

    2020

  63. [71]

    Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan,

    F. Andr ´e, A.-M. Kermarrec, and N. Le Scouarnec, “Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan,” in 42nd International Conference on Very Large Data Bases, vol. 9, no. 4, 2016, p. 12

    2016

  64. [72]

    A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search,

    M. Wang, X. Xu, Q. Yue, and Y . Wang, “A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search,” Proceedings of the VLDB Endowment, vol. 14, no. 11, pp. 1964– 1978, 2021

    1964

  65. [73]

    Hashing techniques: A survey and taxonomy,

    L. Chi and X. Zhu, “Hashing techniques: A survey and taxonomy,” ACM Computing Surveys (Csur) , vol. 50, no. 1, pp. 1–36, 2017

    2017

  66. [74]

    Enhancing address translations in throughput processors via compres- sion,

    X. Tang, Z. Zhang, W. Xu, M. T. Kandemir, R. Melhem, and J. Yang, “Enhancing address translations in throughput processors via compres- sion,” in Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, 2020, pp. 191–204

    2020

  67. [75]

    Understanding and alleviating the impact of the flash address translation on solid state devices,

    Y . Zhou, F. Wu, P. Huang, X. He, C. Xie, and J. Zhou, “Understanding and alleviating the impact of the flash address translation on solid state devices,” ACM Transactions on Storage (TOS), vol. 13, no. 2, pp. 1–29, 2017

    2017

  68. [76]

    Translation ranger: Operating system support for contiguity-aware tlbs,

    Z. Yan, D. Lustig, D. Nellans, and A. Bhattacharjee, “Translation ranger: Operating system support for contiguity-aware tlbs,” in Proceedings of the 46th International Symposium on Computer Architecture , 2019, pp. 698–710

    2019

  69. [77]

    Hcftl: A locality-aware flash translation layer for efficient address translation,

    Y . Pan, H. Chen, J. Zhao, and Y . Xu, “Hcftl: A locality-aware flash translation layer for efficient address translation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 41, no. 8, pp. 2477–2489, 2021

    2021

  70. [78]

    Are up- datable learned indexes ready?

    C. Wongkham, B. Lu, C. Liu, Z. Zhong, E. Lo, and T. Wang, “Are up- datable learned indexes ready?” Proceedings of the VLDB Endowment , vol. 15, no. 11, pp. 3004–3017, 2022

    2022

  71. [79]

    Decomposed bounded floats for fast compression and queries,

    C. Liu, H. Jiang, J. Paparrizos, and A. J. Elmore, “Decomposed bounded floats for fast compression and queries,” Proceedings of the VLDB Endowment, vol. 14, no. 11, pp. 2586–2598, 2021

    2021

  72. [80]

    Gorilla: A fast, scalable, in-memory time series database,

    T. Pelkonen, S. Franklin, J. Teller, P. Cavallaro, Q. Huang, J. Meza, and K. Veeraraghavan, “Gorilla: A fast, scalable, in-memory time series database,” Proceedings of the VLDB Endowment , vol. 8, no. 12, pp. 1816–1827, 2015

    2015

  73. [81]

    Sprintz: Time series compression for the internet of things,

    D. Blalock, S. Madden, and J. Guttag, “Sprintz: Time series compression for the internet of things,” Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies , vol. 2, no. 3, pp. 1– 23, 2018

    2018

  74. [82]

    Ieee standard for floating-point arithmetic,

    “Ieee standard for floating-point arithmetic,” IEEE Std 754-2019 (Revi- sion of IEEE 754-2008) , pp. 1–84, 2019

    2019

  75. [83]

    Fcbench: Cross-domain benchmarking of lossless compression for floating-point data,

    X. Chen, J. Tian, I. Beaver, C. Freeman, Y . Yan, J. Wang, and D. Tao, “Fcbench: Cross-domain benchmarking of lossless compression for floating-point data,” Proceedings of the VLDB Endowment , vol. 17, no. 6, pp. 1418–1431, 2024

    2024

  76. [84]

    Gputerasort: high performance graphics co-processor sorting for large database management,

    N. Govindaraju, J. Gray, R. Kumar, and D. Manocha, “Gputerasort: high performance graphics co-processor sorting for large database management,” in Proceedings of the 2006 ACM SIGMOD international conference on Management of data , 2006, pp. 325–336

    2006

  77. [85]

    Efficient join algorithms for large database tables in a multi-gpu environment,

    R. Rui, H. Li, and Y .-C. Tu, “Efficient join algorithms for large database tables in a multi-gpu environment,” in Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases, vol. 14, no. 4. NIH Public Access, 2020, p. 708

    2020

  78. [86]

    Improving execution efficiency of just-in-time compilation based query processing on gpus,

    J. Paul, B. He, S. Lu, and C. T. Lau, “Improving execution efficiency of just-in-time compilation based query processing on gpus,” Proceedings of the VLDB Endowment , vol. 14, no. 2, pp. 202–214, 2020

    2020

  79. [87]

    Analyzing and implementing gpu hash tables,

    M. A. Awad, S. Ashkiani, S. D. Porumbescu, M. Farach-Colton, and J. D. Owens, “Analyzing and implementing gpu hash tables,” in 2023 Symposium on Algorithmic Principles of Computer Systems (APOCS) . SIAM, 2023, pp. 33–50

    2023

  80. [88]

    Iiu: Specialized architecture for inverted index search,

    J. Heo, J. Won, Y . Lee, S. Bharuka, J. Jang, T. J. Ham, and J. W. Lee, “Iiu: Specialized architecture for inverted index search,” in Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems , 2020, pp. 1...

    2020

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.