Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees

T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read This paper claims that in LSM-tree key-value stores, a learned index trained on both index-lookup cost and storage data-access cost can improve read throughput by 1.19x to 2.21x over state-of-the-art methods while preserving write…

desk verdict Genuine dual-objective contribution for learned LSM indexes, but the single-block access guarantee is unproven and the RL tuning partly fits the benchmark. read the letter →

arxiv 2502.05369 v2 pith:2IEJMUC5 submitted 2025-02-07 cs.DB cs.LGmath.OC

Alireza Heidari , Amirhossein Ahmadi , Wei Zhang This is my paper · ORCID
classification cs.DBcs.LGmath.OC
keywords learnedindexLSMtreekey-valuestoreRocksDBreadamplificationreinforcementlearningpiecewiselinearapproximationdual-objectiveoptimization
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

The paper argues that prior learned indexes for LSM trees optimize only the in-memory index lookup while ignoring the dominant cost of reading the data block from storage. DobLIX trains its model with two objectives: keep the predicted position error within a bound $E$, and keep every data block below a maximum size $b_{\max}$ so that a lookup needs exactly one block read. The model's output is offset-adjusted to the retrieved block, and a stored per-block error bound confines the final binary search to that block. In RocksDB, this design yields 1.19x to 2.21x higher throughput and lower tail latency than the baselines, and it handles variable-length keys and values. A Q-learning agent tunes $E$, $b_{\max}$, and the choice between two model families, PLA and PRA, in response to the workload.

What carries the argument

The load-bearing machinery is a dual-objective training procedure that enforces two constraints on every segment: block size $|B_i| \le b_{\max}$ and model error $\le E$. During lookups, the model output is adjusted by subtracting the block's offset, $M_{\text{adj}}(k) = M(k) - \text{offset}$, and the stored per-segment error bound confines binary search to one block. The paper offers two model families: PLA, a piecewise linear spline with radix points, and PRA, which partitions by $b_{\max}$ and fits linear regression per segment. An RL agent selects between them and tunes $E$, $b_{\max}$, and the model type.

What would settle it

Instrument a build of DobLIX to count how many data blocks are loaded per point lookup, and run it on a dataset where keys are dense near the boundary between two blocks, such as many small KVs followed by one large KV that forces a block boundary; if any lookup whose model interval $[M_{\text{adj}}(k)-E, M_{\text{adj}}(k)+E]$ straddles that boundary loads two blocks, then the single-block-access guarantee is violated.

Watch

Extended reading notes

Core claim

The central claim is that the bottleneck in LSM lookups is not the learned index itself but the coordination between index prediction and storage block layout. By training the index to minimize both the index-lookup error and the number and size of loaded blocks, DobLIX achieves single-block read amplification with block sizes capped at $b_{\max}$. The paper introduces two approximation methods, PLA and PRA, and uses an offset-adjusted prediction $M_{\text{adj}}(k) = M(k) - \text{offset}$ to locate keys within the loaded block, with stored per-segment errors limiting the final search. It further optimizes the last-mile search by skipping common key prefixes and comparing only a fixed number of bytes decoded as integers. The paper reports that this design improves throughput by 1.19x to 2.21x and reduces tail latency by up to 2.13x in read-only workloads compared with existing learned-index and native-index baselines.

Load-bearing premise

The entire speedup rests on the assumption that the model's prediction interval always stays inside the single block it names, so no lookup ever needs to load a second block.

Editorial extensions

If this is right

  • Point lookups in LSM stores should see 1.19x to 2.21x higher throughput and lower tail latency than the tested baselines, with the largest gains in read-only workloads.
  • Block loading and last-mile KV search cease to be the dominant lookup costs because each query reads at most one block and searches only the model's error interval.
  • Index size and write amplification stay at or below native RocksDB: for 64-byte keys the DobLIX index is about 25.9% smaller, and compaction time is comparable or slightly lower.
  • Variable-length keys and values, which prior learned LSM indexes could not handle, work under the same model because common prefixes are stripped and only fixed-size integer suffixes are compared.
  • The RL tuning agent can adapt $E$, $b_{\max}$, and the PLA/PRA choice online, so the method tracks workload shifts without manual reconfiguration.

Reading between the lines

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

  • Beyond the paper: if the single-block guarantee holds in general, the real design lever is the Pareto trade-off between model error and block size, and the tuning agent could be extended to allow a small number of block reads per lookup instead of strictly one.
  • This design implies that the same dual-objective training should transfer to other LSM engines with immutable, sorted files, such as LevelDB or Cassandra's storage engine; the paper does not test those systems.
  • Readers could test the core guarantee directly by checking whether the adjusted prediction interval ever crosses a block boundary on adversarial key distributions; if it does, a per-block error bound rather than a per-segment bound would be needed.
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

4 major / 4 minor

Summary. DobLIX is a learned index for LSM-tree key-value stores, implemented in RocksDB. Per SST, it trains either a piecewise linear approximation (PLA) or a piecewise regression approximation (PRA) model that aims to jointly optimize index lookup and data-block access, with a maximum model error E and a maximum block size b_max. A Q-learning agent periodically chooses the model type, E, and b_max, and the lookup path uses an offset-adjusted model output to narrow the last-mile search and compares only a prefix-limited portion of string keys. The paper reports throughput improvements of 1.19x to 2.21x versus RocksDB, Bourbon, and TridentKV on several datasets and workloads, lower tail latency, smaller index size, and comparable compaction overhead.

Significance. If the single-block guarantee and the evaluation held, DobLIX would be a useful contribution: it directly targets the interaction between learned index predictions and storage block layout in a widely used LSM engine, handles variable-size keys and values, and ships a public artifact plus a fairly broad benchmark suite. The paper also gives a latency breakdown and ablation-style analysis, which is valuable. However, the central claim that every lookup requires exactly one block read is not proven, and the empirical gains are entangled with per-dataset RL tuning and lack of statistical confidence, so the significance is currently conditional on additional justification and cleaner experiments.

major comments (4)
  1. [§3.2, §3.5, Algs. 1-3] The central single-block access claim is not established. Block selection is described as a binary search over the offset array using the model output M(k) (§3.2 and step 7 of Fig. 6), but Algs. 1-3 only enforce |M(k)-I(k)| <= E (or per-segment E') for the global index I(k). For the last key of block B_i, whose true global index is end_i, the model may legally output end_i + epsilon with 0 < epsilon <= E; when end_i + epsilon >= offset_{i+1}, the offset-array lookup selects B_{i+1} even though the key is in B_i. The offset adjustment M_adj(k) = M(k) - B_i.offset described in §3.5 is applied to the search range after block selection and cannot repair the wrong block choice. No boundary-key verification or fallback read is specified. Because the paper attributes its read-amplification reduction to 'single block access' (§3.2, takeaway in §4.2.1), this is a load-bearing gap that must be closed with a proof, an additional per-block containment condition, or an algorithmic guard.
  2. [§4.1.6, §4.7] The RL-based tuning is trained on a 1% sample drawn from the same datasets used in the throughput experiments, and the RL hyperparameters alpha and gamma are selected by sensitivity tests on these same workloads (§4.1.6). The agent then chooses model type, E, and b_max per dataset. Consequently, the reported gains in Fig. 11 are partly the result of per-dataset tuning rather than a demonstration that the agent adapts to unseen distributions, which is the claim of the abstract and §3.6. A clean evaluation should train the agent on a held-out dataset or workload and evaluate on different ones, or compare against an untuned/random configuration to isolate the contribution of the RL component.
  3. [§4.1.5, Fig. 11] No repeated runs, error bars, or confidence intervals are reported for any throughput, latency, or index-size measurement. The headline numbers in Fig. 11 are single measurements, and the text reports average improvements without dispersion. Given the known variability of NVMe benchmarks, the claimed 1.19x-2.21x gains cannot be distinguished from noise. Please report means and standard deviations over multiple runs, or bootstrap confidence intervals, for at least the main comparisons.
  4. [§3.5] The last-mile optimization that compares only K bytes after the common prefix also lacks a correctness argument. If two distinct keys in the search range share the same next K bytes after the trie-level prefix, a comparison limited to those bytes cannot identify the target key. The text says this 'ensuring that the key can be identified' (§3.5), but no uniqueness assumption is stated for the K-byte suffix within the error range, and no fallback to a full comparison is described. This needs either a proof that collisions cannot occur or an explicit fallback in the search procedure.
minor comments (4)
  1. [Abstract and §4.2.1] The abstract states throughput improvements of 1.19x to 2.21x, but §4.2.1 reports a WH speedup versus RocksDB of 1.04x; the reported range should be reconciled or qualified.
  2. [§4.2.4 and Fig. 12] The spelling 'TridenKV' appears in Fig. 12 and §4.2.4; the system name should be consistent with 'TridentKV'.
  3. [Fig. 8] Panel labels use 'E > E0' and 'E < E0', while the text compares E and E'; these error quantities should be defined consistently in the caption and body.
  4. [§4.4] The claim that DobLIX 'even decreases storage and write amplification compared to RocksDB native indexing' is stronger than what Fig. 15(a) supports; for 8-byte keys the index sizes are nearly equal, and the 25.9% improvement is shown for 64-byte keys.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: DobLIX's algorithmic contributions are constructive and its measured gains are not derived from fitted parameters.

full rationale

DobLIX's derivation chain is not circular. The PLA and PRA algorithms (Algorithms 1-3) construct models and block partitions directly from the KV set, with explicit error bounds and maximum block sizes, and the last-mile search (Section 3.5) uses the stored model output and error range to narrow the search within an already loaded block. These are constructive steps, not definitions that presuppose the claimed result. The dual-objective optimization is a stated design criterion, and the measured throughput improvements are empirical results, not predictions derived from the model equations. The RL agent (Section 3.6) does tune parameters such as E, b_max, and model choice, and Section 4.1.6 states that a 1% sample of each dataset is used to train the agent before evaluation. This is a legitimate empirical configuration step: the paper reports measured throughput of the tuned system, not a parameter-free prediction, so it does not reduce the reported gains to the fitted inputs by construction. There is no reliance on a self-citation chain or an imported uniqueness theorem; the cited external techniques (e.g., RSS, RMI) are used as building blocks with independent support. The concern that the single-block access guarantee is not proven from the stated error bounds is a soundness or correctness issue, not circularity: the error bound would need an additional guard or proof, but the claim is not equivalent to its input by definition. Overall, the paper is self-contained in its algorithmic derivation, and no circular step can be exhibited.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central performance claim rests on several fitted or tuned parameters: the PLA error E, the max block size b_max, the reward weight nu, and RL hyperparameters, all chosen or tuned on the benchmark data. The one-block-read guarantee is an unproven ad hoc assumption. No new entities (particles, forces, dimensions) are introduced.

free parameters (5)
  • E (maximum model error for PLA) = 32 to 256, tuned by RL agent
    Controls block splitting in Algorithm 1; tuned on a 1% sample of benchmark data; directly affects last-mile search range and index size.
  • b_max (maximum block size) = 4KB to 32KB, tuned by RL agent
    Primary data-access parameter; determines block partitioning in Algorithms 1-3; tuned on benchmark data.
  • nu (reward weight in RL reward) = 1 for main experiments, varied 0-1 in Section 4.7
    Balances latency versus index size in the reward; set to favor performance.
  • alpha, gamma (RL learning rate, discount) = 0.2, 0.8
    Chosen by sensitivity test; no theoretical justification.
  • epsilon (exploration rate) = initial 0.99, min 0.02
    Decay schedule; standard Q-learning exploration.
assumptions (4)
  • domain assumption SSTs are immutable and sorted, so a trained LI model remains valid for the SST lifetime.
    Standard LSM property, invoked in Section 3.1.
  • ad hoc to paper The model error bound E (or per-block E') after offset adjustment confines the last-mile search to a single block.
    Needed for the one-block-read claim in Sections 3.2 and 3.5; not proven.
  • domain assumption The RL agent's Q-learning over the 32-state space converges and generalizes from a 1% sample to the full workload.
    Standard RL assumption, no convergence analysis; used in Section 3.6 and Section 4.1.6.
  • domain assumption Latency and index-size measurements are stationary within an experiment.
    The reward is computed from averages; no drift analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees." pith.science (2026). https://pith.science/paper/2IEJMUC5

@misc{pith2026250205369,
  author       = {Pith},
  title        = {Pith review of: DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2IEJMUC5}},
  note         = {Machine review of arXiv:2502.05369}
}
read the original abstract

In this paper, we introduce DobLIX, a dual-objective learned index specifically designed for Log-Structured Merge(LSM) tree-based key-value stores. Although traditional learned indexes focus exclusively on optimizing index lookups, they often overlook the impact of data access from storage, resulting in performance bottlenecks. DobLIX addresses this by incorporating a second objective, data access optimization, into the learned index training process. This dual-objective approach ensures that both index lookup efficiency and data access costs are minimized, leading to significant improvements in read performance while maintaining write efficiency in real-world LSM-tree systems. Additionally, DobLIX features a reinforcement learning agent that dynamically tunes the system parameters, allowing it to adapt to varying workloads in real-time. Experimental results using real-world datasets demonstrate that DobLIX reduces indexing overhead and improves throughput by 1.19 to 2.21 times compared to state-of-the-art methods within RocksDB, a widely used LSM-tree-based storage engine.

Figures

Figures reproduced from arXiv: 2502.05369 by the authors.

Figure 1
Figure 1. Lookup Latency Breakdown. Read performance on 10 million 8-byte KVs of the Wiki dataset using the native RocksDB index. The multi-level structure of LSMs [49, 53] results in significant drops in read performance due to high read amplification [45]. The levels are divided into Sorted String Tables (SSTs) that contain KV pairs ordered by keys, with SSTs comprising fixed-size blocks (ranging from 4𝐾𝐵 to 32𝐾𝐵), and retr… view at source ↗
Figure 2
Figure 2. Comparison of LI Solutions on SSTs. Considering block partitioning 𝑃𝑎𝑟𝐵𝑙𝑜𝑐𝑘 and the indexing 𝐼𝐼𝑛𝑑𝑒𝑥𝐵𝑙𝑜𝑐𝑘 as stochastic vari￾ables. a) Small fixed-size blocks, b) Large fixed-size blocks with a guarantee on max block size. c) Variable block size with a model output (𝑀′ (𝑘)) guarantee to load one block. d) Perfect solution with guarantees on model output (𝑀(𝑘)) for one block access with opti￾mized block size. This ove… view at source ↗
Figure 4
Figure 4. LI on Persistent Storage. The model last-mile search range may require loading multiple pages from the storage. CDF estimating 𝑝(𝑥 ≤ 𝑘) and 𝑁 is the key count, to guide queries from the root to the correct layer. Due to complex models, many LIs use piecewise linear models to approximate the CDF [43, 63]. Predict the key’s position as 𝑝𝑜𝑠 = 𝑚 ×𝑘 +𝑎 (with error 𝐸); 𝑚, 𝑎 are learned parameters, and 𝐸 crucial for final … view at source ↗
Figures from the paper (10 more)
Figure 5
Figure 5. Figure 5: DobLIX Architecture in Write Flow. Persistant Storage Memory Pr Keys . . . . . . Active MemTable Immutable MemTable Queue Data Block Data Block Index Block B1 Data Block . . . . . . SSTj￾2 Learned Index Model . . . Bt Bm 1 2 3 4 5 6 7 8 Lookup(ki) SSTj SSTj￾1 SSTj￾2 LS…
Figure 7
Figure 7. Figure 7: LI Models. 𝐵𝑖 s represent the actual blocks added to SSTs. comes to searching for specific points during lookup processes, we employ a binary search on the points derived from the piecewise approximation to precisely pinpoint the required location, which is referred to…
Figure 8
Figure 8. Figure 8: Comparison of PLA and PRA under different data dis￾tributions. (a) 𝐸 ′ < 𝐸, indicating PRA performs better. (b) 𝐸 < 𝐸 ′ , indicating PLA performs better. 𝑙𝑖𝑛𝑒. In this context, 𝑎𝑖 is defined as ℛ(︀𝑖⌋︀(︀0⌋︀(︀1⌋︀, 𝑥𝑖 corresponds to ℛ(︀𝑖⌋︀(︀0⌋︀(︀0⌋︀, and 𝑚𝑖 is calculated …
Figure 10
Figure 10. Figure 10: RL Tuning Agent Overview. using the above adjustment, the coordination of model output for our solution (i.e., Fig. 2d) is transformed to the retrieved block 𝐵2. Subsequently, DobLIX performs a binary search within the specified model error range 𝐸 𝑃 𝑗 𝐿 on 𝑀𝑎𝑑 𝑗 (.).…
Figure 11
Figure 11. Figure 11: Throughput Comparison (upper Figure) and Tail Latency Comparison (lower Figure). 4.1.6 Parameters. By default, all methods adhere to the default configuration settings of RocksDB. The default configurations of Bourbon and TridentKV are also employed. For certain param…
Figure 14
Figure 14. Figure 14: Impact of various key-value sizes. YCSB{B,C,D} workloads, DobLIX demonstrates superior through￾put of 481𝐾, 607𝐾, and 916𝐾 𝑜𝑝𝑠⇑𝑠𝑒𝑐, respectively. On average, DobLIX increases throughput by 1.32×, 1.42×, and 2.02× compared to TridentKV, Bourbon, and RocksDB, respective…
Figure 13
Figure 13. Figure 13: Throughput Comparison on YCSB macrobenchmarks and various distribution workloads. 16 64 256 1KB 4KB (a) Key size 0 0.2 0.4 0.6 0.8 1 Throughput (1 0 5 o p s / s e c) 16 64 256 1KB 4KB (b) Value size 0 0.2 0.4 0.6 0.8 1 UDB ZippyDBUP2X (c) Variable KV 0 0.2 0.4 0.6 0.8…
Figure 15
Figure 15. Figure 15: (a) Average index size, (b) Compaction time, (c) Effect of cache size on throughput. 4.4 Storage and Write Amplification Fig. 15a shows the index size for the AMZN and LOGN datasets with 8- and 64-byte key sizes. We omit Bourbon as it only works with 8-byte numerical …
Figure 16
Figure 16. Figure 16: RL agent parameter tuning. Each row shows two plots for one specific workload and reward parameter, The right plot shows the improvement in the throughput and estimated index size during the workload. The left plot shows the reward heatmap at the end of the experiment…
Figure 18
Figure 18. Figure 18: Final throughput robustness of the RL agent based on the percentage of initial samples to total data (x-axis), evaluated across three different total learning episodes (a, b, c). Each boxplot represents throughput distribution over 30 training runs, with the median (l…

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. Filter-Centric Vector Indexing: Geometric Transformation for Efficient Filtered Vector Search

    cs.DB 2025-06 reject novelty 6.0 of 10

    FCVI subtracts a scaled filter vector from each segment of an embedding, turning filtered vector search into plain ANN search in a re-coordinated space.

Reference graph

Works this paper leans on

74 extracted references · 63 canonical work pages · cited by 1 Pith paper

  1. [1]

    2011. LevelDB. https://opensource.googleblog.com/2011/07/leveldb-fast- persistent-key-value-store.html. Last accessed 2025-07-11

    work page 2011

  2. [2]

    FB Dataset

    2019. FB Dataset. https://doi.org/10.7910/DVN/JGVF9A/Y54SI9. Last accessed 2025-07-11

    work page doi:10.7910/dvn/jgvf9a/y54si9 2019

  3. [3]

    OSM Dataset

    2019. OSM Dataset. https://console.cloud.google.com/marketplace/product/ openstreetmap/geo-openstreetmap. Last accessed 2025-07-11

    work page 2019

  4. [4]

    WikiTS Dataset

    2019. WikiTS Dataset. https://doi.org/10.7910/DVN/JGVF9A/SVN8PI. Last accessed 2025-07-11

    work page doi:10.7910/dvn/jgvf9a/svn8pi 2019

  5. [5]

    Bourbon Code

    2020. Bourbon Code. https://github.com/edydfang/Bourbon. Last accessed 2025-07-11

    work page 2020

  6. [6]

    TridentKV Code

    2021. TridentKV Code. https://github.com/emperorlu/Learned-RocksDB. Last accessed 2025-07-11

    work page 2021

  7. [7]

    Jacob D Abernethy, Robert Schapire, and Umar Syed. 2024. Lexicographic op- timization: Algorithms and stability. In International Conference on Artificial Intelligence and Statistics. PMLR, 2503–2511

    work page 2024

  8. [8]

    Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press

    2004

Show all 74 references
  1. [9]

    Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. 2020. Character- izing, modeling, and benchmarking RocksDB key-value workloads at facebook. In Proceedings of the 18th USENIX Conference on File and Storage Technologies (Santa Clara, CA, USA) (FAST’20). USENIX Associ...

    2020

  2. [10]

    Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wal- lach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. 2008. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS) 26, 2 (2008), 1–26

    2008

  3. [11]

    Subarna Chatterjee, Mark F Pekala, Lev Kruglyak, and Stratos Idreos. 2024. Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than- Memory Cloud Storage Engines. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–28

    2024

  4. [12]

    Altannar Chinchuluun and Panos M Pardalos. 2007. A survey of recent devel- opments in multiobjective optimization. Annals of Operations Research 154, 1 (2007), 29–50

    2007

  5. [13]

    Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears

    Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing (Indianapolis, Indiana, USA) (SoCC ’10). ACM, New York, NY, USA, 143–154. https:/...

    2010 doi

  6. [14]

    Graham Cormode and Marios Hadjieleftheriou. 2008. Finding frequent items in data streams. Proceedings of the VLDB Endowment 1, 2 (2008), 1530–1541

    2008

  7. [15]

    Arpaci-Dusseau, and Remzi H

    Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2020. From WiscKey to Bourbon: a learned index for log-structured merge trees. In Proceedings of the 14th USENIX Conference on Operating Systems Des...

    2020

  8. [16]

    Niv Dayan, Manos Athanassoulis, and Stratos Idreos. 2018. Optimal bloom filters and adaptive merging for LSM-trees. ACM Transactions on Database Systems (TODS) 43, 4 (2018), 1–48

    2018

  9. [17]

    Niv Dayan and Stratos Idreos. 2018. Dostoevsky: Better space-time trade-offs for LSM-tree based key-value stores via adaptive removal of superfluous merging. In Proceedings of the 2018 International Conference on Management of Data. 505–520

    2018

  10. [18]

    Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, et al. 2020. ALEX: an updatable adaptive learned index. SIGMOD

    2020

  11. [19]

    Nan Ding and Radu Soricut. 2017. Cold-start reinforcement learning with softmax policy gradient. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS’17). Curran Associates Inc., Red Hook, NY, USA, 2814–2823

    2017

  12. [20]

    Siying Dong, Andrew Kryczka, Yanqin Jin, and Michael Stumm. 2021. Evolution of Development Priorities in Key-value Stores Serving Large-scale Applications: The RocksDB Experience. In19th USENIX Conference on File and Storage Technolo- gies (FAST 21). USENIX Association, 33–49....

    2021

  13. [21]

    Alexandra Fedorova, Craig Mustard, Ivan Beschastnikh, Julia Rubin, Augustine Wong, Svetozar Miucin, and Louis Ye. 2018. Performance comprehension at WiredTiger. In Proceedings of the 2018 26th ACM Joint Meeting on European Soft- ware Engineering Conference and Symposium on the...

    2018

  14. [22]

    Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proc. VLDB Endow. 13, 8 (April 2020), 1162–1175. https://doi.org/10.14778/3389133.3389135

    2020

  15. [23]

    Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. Fiting-tree: A data-aware index structure. In SIGMOD

    2019

  16. [24]

    Alireza Heidari, Amirhossein Ahmadi, and Wei Zhang. 2025. UpLIF: An Up- datable Self-tuning Learned Index Framework. In Database Engineered Applica- tions, Richard Chbeir, Sergio Ilarri, Yannis Manolopoulos, Peter Z. Revesz, Jorge Bernardino, and Carson K. Leung (Eds.). Spring...

    2025

  17. [25]

    Alireza Heidari, Amirhossein Ahmadi, Zefeng Zhi, and Wei Zhang. 2024. Metahive: A cache-optimized metadata management for heterogeneous key- value stores. arXiv preprint arXiv:2407.19090 (2024)

    2024 arXiv

  18. [26]

    Alireza Heidari, Ihab F Ilyas, and Theodoros Rekatsinas. 2020. Approximate infer- ence in structured instances with noisy categorical observations. In Uncertainty in Artificial Intelligence. PMLR, 412–421

    2020

  19. [27]

    Alireza Heidari, Shrinu Kushagra, and Ihab F Ilyas. 2020. On sampling from data with duplicate records. arXiv preprint arXiv:2008.10549 (2020)

    2020 arXiv

  20. [28]

    Alireza Heidari, Joshua McGrath, Ihab F Ilyas, and Theodoros Rekatsinas. 2019. Holodetect: Few-shot learning for error detection. In Proceedings of the 2019 International Conference on Management of Data . 829–846

    2019

  21. [29]

    Alireza Heidarikhazaei. 2021. Structured Prediction on Dirty Datasets. (2021)

    2021

  22. [30]

    Chaudhari, Evimaria Terzi, and Manos Athanas- soulis

    Andy Huynh, Harshal A. Chaudhari, Evimaria Terzi, and Manos Athanas- soulis. 2022. Endure: a robust tuning paradigm for LSM trees under work- load uncertainty. Proc. VLDB Endow. 15, 8 (April 2022), 1605–1618. https: //doi.org/10.14778/3529337.3529345

    2022

  23. [31]

    Andy Huynh, Harshal A Chaudhari, Evimaria Terzi, and Manos Athanassoulis

  24. [32]

    Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H Noh, and Young-ri Choi

  25. [33]

    Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2020. RadixSpline: a single-pass learned index. In Proceedings of the third international workshop on exploiting artificial intelligence techniques for data management . 1–5

    2020

  26. [34]

    Kornilios Kourtis, Nikolas Ioannou, and Ioannis Koltsidas. 2019. Reaping the performance of fast NVM storage with uDepot. In 17th USENIX Conference on File and Storage Technologies (FAST 19) . USENIX Association, Boston, MA, 1–15. https://www.usenix.org/conference/fast19/prese...

    2019

  27. [35]

    Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. In SIGMOD

    2018

  28. [36]

    Avinash Lakshman and Prashant Malik. 2010. Cassandra: a decentralized struc- tured storage system. ACM SIGOPS operating systems review 44, 2 (2010), 35–40

    2010

  29. [37]

    Shane Culpepper, and Renata Borovica-Gajic

    Hai Lan, Zhifeng Bao, J. Shane Culpepper, and Renata Borovica-Gajic. 2023. Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices. Proc. ACM Manag. Data 1, 2, Article 139 (jun 2023), 22 pages. https://doi.org/10.1145/3589284

    2023 doi

  30. [38]

    Baptiste Lepers, Oana Balmau, Karan Gupta, and Willy Zwaenepoel. 2019. Kvell: the design and implementation of a fast persistent key-value store. InProceedings of the 27th ACM Symposium on Operating Systems Principles . 447–461

    2019

  31. [39]

    Pengfei Li, Yu Hua, Pengfei Zuo, Zhangyu Chen, and Jiajie Sheng. 2023. ROLEX : A Scalable RDMA-oriented Learned Key-Value Store for Dis- aggregated Memory Systems. In 21st USENIX Conference on File and Storage Technologies (FAST 23). 99–114

    2023

  32. [40]

    Pengfei Li, Hua Lu, Qian Zheng, Long Yang, and Gang Pan. 2020. LISA: A learned index structure for spatial data. In Proceedings of the 2020 ACM SIGMOD international conference on management of data . 2119–2133

    2020

  33. [41]

    Pengfei Li, Hua Lu, Rong Zhu, Bolin Ding, Long Yang, and Gang Pan. 2023. DILI: A Distribution-Driven Learned Index. VLDB (2023). https://doi.org/10.14778/ 3598581.3598593

    2023

  34. [42]

    Yongkun Li, Chengjin Tian, Fan Guo, Cheng Li, and Yinlong Xu. 2019. ElasticBF : Elastic Bloom Filter with Hotness Awareness for Boosting Read Performance in Large Key-Value Stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). 739–752

    2019

  35. [43]

    Ester Livshits, Alireza Heidari, Ihab F Ilyas, and Benny Kimelfeld. 2020. Approx- imate denial constraints. arXiv preprint arXiv:2005.08540 (2020)

    2020 arXiv

  36. [44]

    Baotong Lu, Jialin Ding, Eric Lo, Umar Farooq Minhas, and Tianzheng Wang

  37. [45]

    Kai Lu, Nannan Zhao, Jiguang Wan, Changhong Fei, Wei Zhao, and Tongliang Deng. 2022. TridentKV: A Read-Optimized LSM-Tree Based KV Store via Adap- tive Indexing and Space-Efficient Partitioning. IEEE Transactions on Parallel and Distributed Systems 33, 8 (2022), 1953–1966. htt...

    2022 doi

  38. [46]

    Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Hariharan Gopalakrishnan, Andrea C Arpaci-Dusseau, and Remzi H Arpaci-Dusseau. 2017. Wisckey: Sepa- rating keys from values in ssd-conscious storage. ACM Transactions On Storage (TOS) 13, 1 (2017), 1–28

    2017

  39. [47]

    Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska. 2020. Benchmarking learned indexes. Proc. VLDB Endow. 14, 1 (Sept. 2020), 1–13. https://doi.org/10.14778/ 3421424.3421425

    2020

  40. [48]

    Dingheng Mo, Fanchao Chen, Siqiang Luo, and Caihua Shan. 2023. Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads. Proceedings of the ACM on Management of Data 1, 3 (2023), 1–25

    2023

  41. [49]

    Dingheng Mo, Siqiang Luo, and Stratos Idreos. 2025. How to Grow an LSM- tree? Towards Bridging the Gap Between Theory and Practice. arXiv preprint arXiv:2504.17178 (2025)

    2025 arXiv

  42. [50]

    Barzan Mozafari, Eugene Zhen Ye Goh, and Dong Young Yoon. 2015. Cliffguard: A principled framework for finding robust database designs. InProceedings of the 2015 ACM SIGMOD international conference on management of data . 1167–1182

    2015

  43. [51]

    Ibrahim Sabek and Tim Kraska. 2023. The Case for Learned In-Memory Joins. (2023). https://doi.org/10.14778/3587136.3587148

    2023

  44. [52]

    Subhadeep Sarkar and Manos Athanassoulis. 2022. Dissecting, designing, and optimizing LSM-based data stores. In Proceedings of the 2022 International Con- ference on Management of Data . 2489–2497

    2022

  45. [53]

    Subhadeep Sarkar, Niv Dayan, and Manos Athanassoulis. 2023. The LSM design space and its read optimizations. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 3578–3584

    2023

  46. [54]

    Benjamin Spector, Andreas Kipf, Kapil Vaidya, Chi Wang, Umar Farooq Minhas, and Tim Kraska. 2021. Bounding the Last Mile: Efficient Learned String Indexing. CoRR abs/2111.14905 (2021). arXiv:2111.14905 https://arxiv.org/abs/2111.14905

    2021 arXiv

  47. [55]

    Zhaoyan Sun, Xuanhe Zhou, and Guoliang Li. 2023. Learned index: A com- prehensive experimental evaluation. Proceedings of the VLDB Endowment 16, 8 (2023), 1992–2004

    2023

  48. [56]

    Dejun Teng, Lei Guo, Rubao Lee, Feng Chen, Siyuan Ma, Yanfeng Zhang, and Xiaodong Zhang. 2017. LSbM-tree: Re-enabling buffer caching in data manage- ment for mixed reads and writes. In 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS) . IEEE, 68–79

    2017

  49. [57]

    Hengrui Wang, Te Guo, Junzhao Yang, and Huanchen Zhang. 2024. GRF: A Global Range Filter for LSM-Trees with Shape Encoding. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27

    2024

  50. [58]

    Wenlong Wang and David Hung-Chang Du. 2024. LearnedKV: Integrating LSM and Learned Index for Superior Performance on SSD. arXiv preprint arXiv:2406.18892 (2024)

    2024 arXiv

  51. [59]

    Youyun Wang, Chuzhe Tang, Zhaoguo Wang, and Haibo Chen. 2020. SIndex: a scalable learned index for string keys. In Proceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems. 17–24

    2020

  52. [60]

    Yi Wang, Jianan Yuan, Shangyu Wu, Huan Liu, Jiaxian Chen, Chenlin Ma, and Jianbin Qin. 2024. LeaderKV: Improving Read Performance of KV Stores via Learned Index and Decoupled KV Table. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlan...

    2024

  53. [61]

    Zhonghua Wang, Chen Ding, Fengguang Song, Kai Lu, Jiguang Wan, Zhihu Tan, Changsheng Xie, and Guokuan Li. 2024. WIPE: A Write-Optimized Learned Index for Persistent Memory. ACM Trans. Archit. Code Optim. 21, 2, Article 22 (feb 2024), 25 pages. https://doi.org/10.1145/3634915

    2024 doi

  54. [62]

    Christopher JCH Watkins and Peter Dayan. 1992. Q-learning. Machine learning 8 (1992), 279–292

    1992

  55. [64]

    Fenggang Wu, Ming-Hong Yang, Baoquan Zhang, and David HC Du. 2020. AC- Key : Adaptive caching for LSM-based Key-Value stores. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). 603–615

    2020

  56. [65]

    Giorgos Xanthakis, Antonios Katsarakis, Giorgos Saloustros, and Angelos Bilas

  57. [66]

    Yifan Yang and Shimin Chen. 2024. LITS: An Optimized Learned Index for Strings. Proceedings of the VLDB Endowment 17, 11 (2024), 3415–3427

    2024

  58. [67]

    Qiaolin Yu, Chang Guo, Jay Zhuang, Viraj Thakkar, Jianguo Wang, and Zhichao Cao. 2024. CaaS-LSM: compaction-as-a-service for LSM-based key-value stores in storage disaggregated infrastructure. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–28

    2024

  59. [68]

    Jiaoyi Zhang and Yihan Gao. 2022. CARMI: A Cache-Aware Learned Index with a Cost-Based Construction Algorithm. VLDB (2022). https://doi.org/10.14778/ 3551793.3551823

    2022

  60. [69]

    arXiv preprint arXiv:2407.15581 (2024)

    vLSM: Low tail latency and I/O amplification in LSM-based KV stores. arXiv preprint arXiv:2407.15581 (2024)

    2024 arXiv

  61. [70]

    Zhou Zhang, Zhaole Chu, Peiquan Jin, Yongping Luo, Xike Xie, Shouhong Wan, Yun Luo, Xufei Wu, Peng Zou, Chunyang Zheng, et al . 2022. PLIN: A persis- tent learned index for non-volatile memory with high performance and instant recovery. Proceedings of the VLDB Endowment 16, 2 ...

    2022

  62. [71]

    Zhutao Zhuang, Xinqi Zeng, and Zhiguang Chen. 2025. DumpKV: Learning Based Lifetime Aware Garbage Collection for Key Value Separation in LSM- Tree. Proc. VLDB Endow. 18, 4 (May 2025), 1223–1236. https://doi.org/10.14778/ 3717755.3717778

    2025

  63. [73]

    Jiaoyi Zhang, Kai Su, and Huanchen Zhang. 2024. Making In-Memory Learned Indexes Efficient on Disk. Proc. ACM Manag. Data 2, 3, Article 151 (may 2024), 26 pages. https://doi.org/10.1145/3654954

    2024 doi

  64. [2019]

    In 17th USENIX Conference on File and Storage Technologies (FAST 19)

    SLM-DB : Single-Level Key-Value store with persistent memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19) . 191–205

  65. [2021]

    VLDB Endow

    APEX: a high-performance learned index on persistent memory.Proc. VLDB Endow. 15, 3 (nov 2021), 597–610. https://doi.org/10.14778/3494124.3494141

    2021

  66. [2024]

    The VLDB Journal (2024), 1–24

    Towards flexibility and robustness of LSM trees. The VLDB Journal (2024), 1–24

    2024

Pith tools

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