Pith. sign in

REVIEW 3 major objections 5 minor 35 references

A workload-driven partitioning scheme balances both data and query load on processing-in-memory indexes while preserving spatial locality for range aggregates.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 14:10 UTC pith:BE53O7QZ

load-bearing objection Solid, honest systems paper with a genuinely new query density-driven partitioning scheme for PIM indexes; the load-balance theorem is conditional on a representative reference workload, and the paper says so clearly in Section 6.4. the 3 major comments →

arxiv 2607.29070 v1 pith:BE53O7QZ submitted 2026-07-31 cs.DB

Query Density-Driven Partitioning for Spatiotemporal Load Balancing on Processing-in-Memory Systems

Takato Hideshima , Shigeyuki Sato , Tomoharu Ugawa This is my paper
classification cs.DB
keywords query density-driven partitioningspatiotemporal load balancingprocessing-in-memoryrange-aggregate queriesB+-Forestskewed querieskey-range partitioning
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper argues that query density—the number of queries hitting a unit of data—is the right target for partitioning ordered-key indexes on processing-in-memory (PIM) systems. It proposes identifying hot (high-density) key ranges, giving at most one hot range to each processor, and keeping the remaining cold ranges contiguous and evenly sized. This yields provable bounds on both data size and query load per processor, controlled by a tuning parameter α. The authors build B+-Forest, a B+-tree variant using this partitioning, and show experimentally that it stays balanced under skewed queries where density-unaware partitioning fails, while supporting range-aggregate queries efficiently and matching the point-query performance of the state-of-the-art PIM index.

Core claim

The central claim is that partitioning by query density reconciles two goals previously in tension: spatiotemporal load balancing under skewed queries and spatial locality for range-aggregate queries. The paper proves that, for any positive integer α, the greedy hot-range selection yields per-processor data load < (1/α+1) D/P + M_d and query load < (α+1) Q/P + M_q, where D is total data, Q total reference queries, P the number of processors, and M_d, M_q are per-chunk maxima; a double-scan improvement tightens the cold-range query bound to roughly (α+1)/3 · Q/P for α>1. Experiments with a Zipf-composite workload show that a B+-Forest implementation achieves a near-constant query imbalance fa

What carries the argument

Query density—the count of reference queries hitting a data chunk divided by the chunk's size—and the partition parameter α, which sets the maximum window width for a hot range as D/(αP). Hot ranges are extracted greedily or by a double scan, with at most P hot ranges total, and each processor receives at most one; cold ranges are assigned contiguously in a base-partition layout, preserving locality. The routing table has at most 3P entries, so it stays in CPU cache. These pieces combine to give the per-processor data and query bounds proven in Theorems A.9 and B.6.

Load-bearing premise

The reference workload used to identify hot ranges must be representative of the queries that will actually arrive; the paper's own Section 6.4 shows that if a cold partition heats up after partitioning, the query imbalance factor can jump to 26, and then the theoretical bounds no longer apply.

What would settle it

Take the paper's workload-sensitivity setup (ZcAmp) and amplify the query density of the coldest base partition by a factor growing from 1 to 100, measuring the query imbalance factor of B+-Forest after a single static partition. If the imbalance factor grows linearly with the amplification factor rather than staying bounded near the predicted (α+1)Q/P + M_q, the load-balance guarantee is conditional on workload stasis and would collapse under drift.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • PIM-backed key-value stores can execute batched range aggregates—not just point and scan queries—without sacrificing skew resistance.
  • The α parameter gives a tunable trade-off: smaller α emphasizes query balance, larger α emphasizes data balance, so memory-limited systems can pick a feasible operating point.
  • Because the partitioning is index-agnostic, it can be layered onto other ordered-key data structures, not only B+-trees.
  • B+-Forest's throughput keeps improving with much larger query batches than PIM-tree can process, up to 1.1G in the experiments.
  • The proof guarantees hold for any reference workload with well-defined per-chunk query counts, assuming the workload is representative.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The query-density idea could be extended to dynamic rebalancing: online detection of newly-hot ranges would let a system migrate only those ranges, rather than rebuilding all partitions; the paper's concurrent work sketches this path.
  • The same density-driven separation of hot and cold ranges might apply to CPU-side distributed key-value stores where locality and load balancing are both concerns, though the communication model differs.
  • A testable extension is to use learned or sampled query statistics instead of a full reference workload, trading partitioning quality for lower profiling cost.
  • The observed degradation with very high skew and small data (Zipf 1.2, D=200M) suggests that chunk granularity, not the partitioning scheme itself, is the bottleneck; choosing chunk size adaptively could recover balance.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes query density-driven key-range partitioning for PIM systems, aiming to achieve both load balance (query load and data size) and spatial locality for batched range-aggregate queries. The partitioning scheme identifies hot ranges by query density and distributes at most one hot partition per DPU, leaving the rest as cold, contiguous ranges. The authors instantiate this in B+-Forest, a PIM-oriented B+-tree variant on UPMEM hardware, and give appendix proofs bounding per-DPU data and query loads for a fixed reference workload (Theorems A.9 and B.6). Experiments on real UPMEM hardware compare B+-Forest with a density-unaware chains-on-chains partitioned B+-tree and with PIM-tree, reporting better skew resistance under memory constraints, comparable point-get performance, and efficient range-aggregate processing. The paper includes a workload-sensitivity study (Section 6.4) and an explicit scope-and-limitations statement that offline full rebalancing is assumed, with online rebalancing deferred to a concurrent paper.

Significance. If the results hold, the paper makes a solid contribution: a workload-driven partitioning scheme for PIM key-value stores that provably balances query load and data size for a given reference workload while preserving spatial locality for range-aggregate queries. The appendix contains detailed proofs, and the evaluation on real UPMEM hardware with up to 2,538 DPUs is a strength. The paper demonstrates a clear advantage over a density-unaware chain-on-chains baseline under space constraints, and it honestly reports the sensitivity to workload drift. However, the central guarantee is conditional on the reference workload being representative; Section 6.4 shows that a 10x amplification of one cold partition raises the query imbalance factor from 2.8 to 26. This conditionality is acknowledged in the limitations paragraph but is not reflected in the unqualified abstract/title claims.

major comments (3)
  1. [Title/Abstract vs. Section 6.4 and Scope and Limitations] The abstract and title claim 'spatiotemporal load balancing' without qualification, but Theorems A.9 and B.6 bound loads only with respect to the reference workload NQrys used in Algorithm 1. Section 6.4 shows that under workload drift (ZcAmp(b20,10)) the query imbalance factor jumps to 26, and the paper's own scope statement says rebalancing is offline and deferred to a concurrent paper. This is not an internal proof error, but it is a load-bearing limitation of the central claim as stated. The authors should qualify the abstract/title and the main claims to specify that the guarantees and experiments assume a stationary workload matching the reference; otherwise the reader may reasonably infer robustness to workload changes that the system does not provide.
  2. [Section 6.1 and Section 6.4] The main experimental evaluation uses the first warm-up batch as the reference workload and evaluates on batches drawn from the same distribution (Section 6.1). Figures 7, 11, and 12 therefore demonstrate performance only when the actual workload matches the reference. Section 6.4 is the only experiment that deviates from the reference, and it shows a large imbalance increase. This circularity does not invalidate the comparison to density-unaware partitioning under stationary skew, but it does mean the empirical claim of 'skew resistance' is not tested against workload shift. The paper should make this explicit in the evaluation summary and, if possible, include additional drift experiments beyond the single amplification scenario in Section 6.4.
  3. [Theorems A.9 and B.6; hot-partition bound includes M_q] The hot-partition query-load bound includes M_q, the maximum number of queries hitting a single data chunk (Theorems A.2 and B.3). For coarse chunk granularity or extreme skew, M_q can be as large as O(Q), making the per-DPU query bound trivial. The paper acknowledges the negative effect of chunking in Section 6.3, but the abstract and theorem statements do not highlight that the strength of the guarantee depends on the chunk size. Since chunk size is a free parameter, the authors should state this dependency explicitly when summarizing the bounds, and report M_q or the observed chunk-level query counts in the experimental setup.
minor comments (5)
  1. [Section 4.2] The text says the number of partitions is 'at most 3P'. This is true only if one counts both the cold intervals (which can be split by multiple hot ranges per base partition) and the hot partitions. The derivation would benefit from a one-sentence explanation, e.g., P cold intervals plus at most H extra cold intervals from splits plus H hot partitions gives at most P+2H <= 3P.
  2. [Section 3 vs. Section 5] Section 3 defines RAQs assuming only an associative reduction with identity, but Section 5 states B+-Forest is dedicated to commutative reduction operators. The postprocessing step likely requires commutativity. Please reconcile these definitions or clarify that non-commutative RAQs are not supported.
  3. [Algorithm 2 (line 4) and Section 4.3] The use of max over an empty set is described only in the body text ('max S produces -∞'), not in the pseudocode. Readers may find the algorithm under-specified without this note; consider adding an explicit default value in the pseudocode or table of symbols.
  4. [Section 6.5 and Figure 13] The comparison with PIM-tree is explicitly said to be 'not a direct comparison', but Figure 13 presents PIM-tree scan-batch times as evidence that RAQs on PIM-tree would be costly. This is a fair qualitative argument, but the caption and text should clarify that the comparison is workload-level, not a like-for-like implementation comparison, to avoid overinterpretation.
  5. [Appendix A and B, typos] There are several typos: 'subseqeunce' in Definition A.4, 'The The CPU' at the start of Section 5.2, 'forcus' in the proof of Theorem B.6, and inconsistent use of 'h*' vs. '× h' in Algorithm 3 comments. A careful proofreading pass is needed.

Circularity Check

0 steps flagged

No significant circularity: the load-balance theorems are derived from the reference-workload input, and workload drift is explicitly tested as a limitation rather than presented as a prediction.

full rationale

The paper's central derivation is self-contained: Algorithm 1 takes the reference workload NQrys as an input, and Theorems A.9 and B.6 prove load bounds as functions of that input. These proofs are not fitted to the experimental data and do not assume the conclusion; they follow from the hot/cold partition construction. The experimental setup uses the first warm-up batch as the reference workload and evaluates on subsequent batches from the same distribution, but the paper does not rename this fit as a prediction. Section 6.4 explicitly tests deviation from the reference workload, reporting that amplifying a cold base partition raises the query imbalance factor from 2.8 to 26, and the Scope and Limitations paragraph states that online dynamic rebalancing is deferred to a concurrent paper [16]. These are stated limitations about workload stationarity, not circular reductions. The only self-citations are a pointer to the concurrent online-rebalancing paper and an implementation technique (occupancy embedding); neither is load-bearing for the partitioning theorem. The comparison against density-unaware chains-on-chains partitioning and PIM-tree is an external benchmark, and the parameter alpha is swept and chosen to satisfy memory constraints rather than fitted to the evaluated workload. Therefore the derivation chain does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 0 invented entities

The central load-balance bounds rest on a small set of domain assumptions: a representative reference workload, sorted data chunks, an associative/commutative reduction, and the UPMEM programming model. There are two tunable parameters (α and chunk size) that are not fitted to the performance results. No new physical or conceptual entities are introduced.

free parameters (2)
  • α (partitioning parameter) = 10 in main experiments
    Controls the trade-off between query load balance and data size balance. In the experiments it is set to achieve the memory constraint (data imbalance factor ≤ 1.1); the paper also sweeps α from 1 to 65 to map the trade-off.
  • Data chunk size = Not specified numerically
    The granularity of data chunks used for hot/cold partition extraction. It affects spatial locality and the M_d and M_q slack terms in the load bounds. The paper notes the chunk granularity is derived from the B+-Forest implementation, not from the partitioning scheme itself.
axioms (5)
  • domain assumption The reference workload (NQrys) is representative of the actual query distribution.
    The partitioning algorithm identifies hot ranges from this workload; if it is unrepresentative, the load-balance guarantees degrade, as shown in Section 6.4.
  • domain assumption The reduction operator is associative and has an identity (and is commutative in the implementation).
    Range-aggregate queries combine partial results from multiple DPUs on the CPU; Section 3 states associativity+identity, Section 5 restricts to commutative operators, a stronger condition that is not flagged.
  • domain assumption Input key-value pairs are sorted in key order and uniformly divided into data chunks of known size.
    Algorithm 1 creates base partitions by splitting the sorted data by size; this requires the sorted order and known chunk sizes.
  • domain assumption UPMEM computational model: no shared memory between CPU and DPUs, communication is CPU-initiated, DPUs run homogeneous kernels.
    B+-Forest's routing/evaluation/postprocessing design is tailored to this model (Section 2).
  • domain assumption Range-aggregate queries in the workload have a typical range length of about 100 items.
    The paper states this assumption from real-world Facebook workloads (Section 3); long ranges would amplify query routing and weaken spatial locality.

pith-pipeline@v1.3.0-daily-deepseek · 25647 in / 14095 out tokens · 133256 ms · 2026-08-03T14:10:46.510187+00:00 · methodology

0 comments
read the original abstract

Processing-in-Memory (PIM) systems, which consist of many processors with small local memory, have recently emerged as commercial products and attracted much attention as a means of overcoming the memory wall, particularly in the context of in-memory database technology. The state-of-the-art PIM-oriented index PIM-tree has been demonstrated to achieve asymptotically good spatiotemporal load balancing---query loads and data sizes are balanced among processors---for skewed queries, by trading spatial locality. Unfortunately, such a sacrifice of spatial locality hinders the PIM-oriented processing of range-aggregate queries. To achieve both spatiotemporal load balancing and efficiently executing range-aggregate queries on PIM systems, we develop a query density-driven key-range partitioning scheme. It balances query density among PIM processors, allowing us to strike a balance between query load and data size via a parameter. We then develop B${}^\text{+}$-Forest, a PIM-oriented B${}^\text{+}$-tree variant based on our partitioning scheme. Experimental results demonstrated that it exhibits higher skew resistance than a B${}^\text{+}$-tree based on space-constrained, query-load-balanced, density-unaware partitioning, and performance comparable to PIM-tree in point-get queries, as well as efficient support for range-aggregate queries.

Figures

Figures reproduced from arXiv: 2607.29070 by Shigeyuki Sato, Takato Hideshima, Tomoharu Ugawa.

Figure 1
Figure 1. Figure 1: Overview of query density-driven partitioning. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: c. Now, we consider assigning a small number of partitions Ordered Data Query Density (a) Data-balanced one-dimensional partitioning. Ordered Data Query Density (b) Query-balanced one-dimensional partitioning. Ordered Data Query Density (c) Query density-driven partitioning [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Too few hot ranges selected in Algorithm [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Implementation of the routing table with an exam [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Workflow of B+ -Forest processing an RAQ batch. records the RAQs into the appropriate local arrays according to the routing table. After that, the local arrays of all threads are gathered, producing sub-batches. Evaluation. Given a sub-batch of RAQs, the DPU calculates the partial result of each RAQ through aggregation over both B+ -trees. The partial results are stored in a resultant array in order. This … view at source ↗
Figure 8
Figure 8. Figure 8: Trade-off between the imbalance factor of data and [PITH_FULL_IMAGE:figures/full_fig_p007_8.png] view at source ↗
Figure 10
Figure 10. Figure 10: Area plot of the imbalance factor of queries for [PITH_FULL_IMAGE:figures/full_fig_p008_10.png] view at source ↗
Figure 13
Figure 13. Figure 13: is inevitable. Therefore, the results have demonstrated that B + -Forest works well for RAQs. 0.6 0.8 1.0 1.2 Zipf skewness 0 1000 2000 Avg. batch processing time [ms] CPU Communication PIM [PITH_FULL_IMAGE:figures/full_fig_p009_13.png] view at source ↗
Figure 12
Figure 12. Figure 12: Throughput of batched queries on B+ -Forest. Here, we emphasize the virtues of B+ -Forest for two major points. One is that B+ -Forest supports efficient RAQs. As illustrated in Figs. 12a and 12b, batched RAQs had no less than 50% of through￾put as get-batch up to Zipf(1.0); even at Zipf(1.2), it was 44.2%. The ratio of throughput shrinkage is a very small constant com￾pared to the number of hit items, wh… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 4 canonical work pages

  1. [1]

    Young, Frank Liu, and Jeffrey S

    Kazi Asifuzzaman, Narasinga Rao Miniskar, Aaron R. Young, Frank Liu, and Jeffrey S. Vetter. 2023. A Survey on Processing-in-Memory Techniques: Advances and Challenges.Memories - Materials, Devices, Circuits and Systems4 (2023), 100022:1–100022:11. doi:10.1016/j.memori.2022.100022

    arXiv 2023

  2. [2]

    Arthur Bernhardt, Andreas Koch, and Ilia Petrov. 2023. pimDB: From Main- Memory DBMS to Processing-in-Memory DBMS-Engines on Intelligent Memo- ries. InProceedings of the 19th International Workshop on Data Management on New Hardware (DaMoN ’23). ACM, 44–52. doi:10.1145/3592980.3595312

    arXiv 2023

  3. [3]

    Mike Butts. 2007. Synchronization through Communication in a Massively Parallel Processor Array.IEEE Micro27, 5 (2007), 32–40. doi:10.1109/MM.2007. 4378781

    work page doi:10.1109/mm.2007 2007

  4. [4]

    Zhichao Cao, Siying Dong, Sagar Vemuri, and David H.-C. Du. 2020. Characteriz- ing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST ’20). USENIX, 209–223. https://www.usenix.org/conference/fast20/presentation/ cao-zhichao

    2020

  5. [5]

    Chen Chen, Wenshao Zhong, and Xingbo Wu. 2022. Building an Efficient Key- Value Store in a Flexible Address Space. InProceedings of the Seventeenth European Conference on Computer Systems (EuroSys ’22). ACM, 51–68. doi:10.1145/3492321. 3519555

    doi:10.1145/3492321 2022

  6. [6]

    Iris Ba- har

    Jiwon Choe, Andrew Crotty, Tali Moreshet, Maurice Herlihy, and R. Iris Ba- har. 2022. HybriDS: Cache-Conscious Concurrent Data Structures for Near- Memory Processing Architectures. InProceedings of the 34th ACM Sympo- sium on Parallelism in Algorithms and Architectures (SPAA ’22). ACM, 321–332. doi:10.1145/3490148.3538591

    arXiv 2022

  7. [7]

    Iris Bahar

    Jiwon Choe, Amy Huang, Tali Moreshet, Maurice Herlihy, and R. Iris Bahar. 2019. Concurrent Data Structures with Near-Data-Processing: An Architecture-Aware Implementation. InProceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’19). ACM, 297–308. doi:10.1145/3323165. 3323191

    work page doi:10.1145/3323165 2019

  8. [8]

    Sara Cohen. 2006. User-Defined Aggregate Functions: Bridging Theory and Practice. InProceedings of the 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD ’06). ACM, 49–60. doi:10.1145/1142473.1142480

    arXiv 2006

  9. [9]

    Lixiao Cui, Kedi Yang, Yusen Li, Gang Wang, and Xiaoguang Liu. 2025. PIMLex: A High-Performance Learned Index with Processing-in-Memory. InProceedings of the 23rd USENIX Conference on File and Storage Technologies (FAST ’25). USENIX, 287–303. https://www.usenix.org/conference/fast25/presentation/cui

    2025

  10. [10]

    Benoît Dupont de Dinechin. 2015. Kalray MPPA®: Massively Parallel Processor Array: Revisiting DSP Acceleration with the Kalray MPPA Manycore Processor. In2015 IEEE Hot Chips 27 Symposium (HCS). IEEE, 1–27. doi:10.1109/HOTCHIPS. 2015.7477332 10 Query Density-Driven Partitioning for Spatiotemporal Load Balancing on Processing-in-Memory Systems

    arXiv 2015

  11. [11]

    Yann Falevoz and Julien Legriel. 2024. Energy Efficiency Impact of Processing in Memory: A Comprehensive Review of Workloads on the UPMEM Architecture. In Euro-Par 2023: Parallel Processing Workshops. Springer, 155–166. doi:10.1007/978- 3-031-48803-0_13

    doi:10.1007/978- 2024

  12. [12]

    Yannis Foufoulas and Alkis Simitsis. 2023. User-Defined Functions in Modern Data Engines. In2023 IEEE 39th International Conference on Data Engineering (ICDE ’23). IEEE, 3593–3598. doi:10.1109/ICDE55515.2023.00276

    arXiv 2023

  13. [13]

    Eran Gilad, Edward Bortnikov, Anastasia Braginsky, Yonatan Gottesman, Eshcar Hillel, Idit Keidar, Nurit Moscovici, and Rana Shahout. 2020. EvenDB: Optimizing Key-Value Storage for Spatial Locality. InProceedings of the Fifteenth European Conference on Computer Systems (EuroSys ’20). ACM, 1–16. doi:10.1145/3342195. 3387523

    doi:10.1145/3342195 2020

  14. [14]

    Oliveira, and Onur Mutlu

    Juan Gómez-Luna, Izzat El Hajj, Ivan Fernandez, Christina Giannoula, Geraldo F. Oliveira, and Onur Mutlu. 2022. Benchmarking a New Paradigm: Experimental Analysis and Characterization of a Real Processing-in-Memory System.IEEE Access10 (2022), 52565–52608. doi:10.1109/ACCESS.2022.3174101

    arXiv 2022

  15. [15]

    Naoya Hatta, Shuntaro Tsunoda, Kouhei Uchida, Taichi Ishitani, Toru Koizumi, Ryota Shioya, and Kei Ishii. 2025. PEZY-SC4s: The Fourth Generation MIMD Many-core Processor with High Energy Efficiency and Flexibility for HPC and AI Applications. In2025 IEEE Hot Chips 37 Symposium (HCS). IEEE, 1–42. doi:10. 1109/HCS66204.2025.11154388

    arXiv 2025

  16. [16]

    Takato Hideshima, Shigeyuki Sato, and Tomoharu Ugawa. 2026. Spatiotemporal Load Balancing for Near-Memory Accelerated Databases by Partial Resharding. InWorkshop Proceedings of the 55th International Conference on Parallel Processing (ICPP Workshops ’26). ACM, 8 pages. doi:10.1145/3816891.3834892 To appear

    arXiv 2026

  17. [17]

    Takato Hideshima and Tomoharu Ugawa. 2025. Exploring B+-Tree Implementa- tions Using Scratchpad Memory. InProceedings of the 16th ACM SIGOPS Asia- Pacific Workshop on Systems (APSys ’25). ACM, 75–81. doi:10.1145/3725783. 3764412

    doi:10.1145/3725783 2025

  18. [18]

    Yifan Hua, Shengan Zheng, Weihan Kong, Cong Zhou, Kaixin Huang, Ruoyan Ma, and Linpeng Huang. 2024. RADAR: A Skew-Resistant and Hotness-Aware Ordered Index Design for Processing-in-Memory Systems.IEEE Trans. Parallel Distrib. Syst.35, 9 (2024), 1598–1614. doi:10.1109/TPDS.2024.3424853

    arXiv 2024

  19. [19]

    Gibbons, Guy E

    Hongbo Kang, Phillip B. Gibbons, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, and Charles McGuffey. 2021. The Processing-in-Memory Model. InProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’21). ACM, 295–306. doi:10.1145/3409964.3461816

    arXiv 2021

  20. [20]

    Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip B

    Hongbo Kang, Yiwei Zhao, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip B. Gibbons. 2022. PIM-Tree: A Skew-Resistant Index for Processing-in-Memory.Proc. VLDB Endow.16, 4 (2022), 946–958. doi:10.14778/ 3574245.3574275 https://github.com/cmuparlay/PIM-tree

    arXiv 2022

  21. [21]

    Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip B

    Hongbo Kang, Yiwei Zhao, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip B. Gibbons. 2023. PIM-trie: A Skew-Resistant Trie for Processing-in-Memory. InProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’23). ACM, 1–14. doi:10.1145/3558481. 3591070

    work page doi:10.1145/3558481 2023

  22. [22]

    Kepe, Eduardo C

    Tiago R. Kepe, Eduardo C. de Almeida, and Marco A. Z. Alves. 2019. Database Processing-in-Memory: An Experimental Study.Proc. VLDB Endow.13, 3 (2019), 334–347. doi:10.14778/3368289.3368298

    arXiv 2019

  23. [23]

    Sukhan Lee, Shin-haeng Kang, Jaehoon Lee, Hyeonsu Kim, Eojin Lee, Seungwoo Seo, Hosang Yoon, Seungwon Lee, Kyounghwan Lim, Hyunsung Shin, Jinhyun Kim, Seongil O, Anand Iyer, David Wang, Kyomin Sohn, and Nam Sung Kim

  24. [24]

    Matthias Lieber and Wolfgang E. Nagel. 2014. Scalable High-Quality 1D Par- titioning. In2014 International Conference on High Performance Computing & Simulation (HPCS ’14). IEEE, 112–119. doi:10.1109/HPCSim.2014.6903676

    arXiv 2014

  25. [25]

    Qiyu Liu, Maocheng Li, Yuxiang Zeng, Yanyan Shen, and Lei Chen. 2025. How Good Are Multi-Dimensional Learned Indexes? An Experimental Survey.VLDB J.34, 2 (2025), 17:1–17:29. doi:10.1007/s00778-024-00893-6

    doi:10.1007/s00778-024-00893-6 2025

  26. [26]

    Joel Nider, Craig Mustard, Andrada Zoltan, John Ramsden, Larry Liu, Jacob Grossbard, Mohammad Dashti, Romaric Jodin, Alexandre Ghiti, Jordi Chauzi, and Alexandra Fedorova. 2021. A Case Study of Processing-in-Memory in Off- the-Shelf Systems. InProceedings of the 2021 USENIX Annual Technical Conference (USENIX ATC ’21). USENIX, 117–130. https://www.usenix....

    2021

  27. [27]

    Ali Pınar and Cevdet Aykanat. 2004. Fast Optimal Load Balancing Algorithms for 1D Partitioning.J. Parallel and Distrib. Comput.64, 8 (2004), 974–996. doi:10. 1016/j.jpdc.2004.05.003

    2004

  28. [28]

    Junru Shen, Miao Cai, Kangyue Gao, Baoliu Ye, and Guo Cheng. 2025. HeatList: The Case for Retrofitting In-memory Range Index with Hotspot Awareness. In Proceedings of the 54th International Conference on Parallel Processing (ICPP ’25). ACM, 362–373. doi:10.1145/3754598.3754627

    arXiv 2025

  29. [29]

    Zhaoyan Sun, Xuanhe Zhou, and Guoliang Li. 2023. Learned Index: A Compre- hensive Experimental Evaluation.Proc. VLDB Endow.16, 8 (2023), 1992–2004. doi:10.14778/3594512.3594528

    arXiv 2023

  30. [30]

    UPMEM SAS. [n. d.]. UPMEM – UPMEM is Releasing a True Processing-in- Memory (PIM) Acceleration Solution. https://www.upmem.com/. Accessed on December 18, 2024

    2024

  31. [31]

    Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. 2022. ParGeo: A Library for Parallel Computational Geometry. In Proceedings of the 30th Annual European Symposium on Algorithms (ESA ’22). Schloss Dagstuhl, 88:1–88:19. doi:10.4230/LIPICS.ESA.2022.88

    doi:10.4230/lipics.esa.2022.88 2022

  32. [32]

    Brian Wheatman, Randal Burns, Aydin Buluç, and Helen Xu. 2024. CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers. InProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP ’24). ACM, 348–363. doi:10.1145/3627535.3638492

    arXiv 2024

  33. [33]

    Yue Yang and Jianwen Zhu. 2016. Write Skew and Zipf Distribution: Evidence and Implications.ACM Trans. Storage12, 4 (2016), 21:1–21:19. doi:10.1145/2908557

    work page doi:10.1145/2908557 2016

  34. [34]

    Wenshao Zhong, Chen Chen, Xingbo Wu, and Song Jiang. 2021. REMIX: Efficient Range Query for LSM-trees. InProceedings of the 19th USENIX Conference on File and Storage Technologies (FAST ’21). USENIX, 51–64. https://www.usenix.org/ conference/fast21/presentation/zhong A Proof of the Properties of the Greedy Hot Selection Algorithm We prove the properties s...

    2021

  35. [2021]

    InProceedings of the 48th Annual International Symposium on Computer Architecture (ISCA ’21)

    Hardware Architecture and Software Stack for PIM Based on Commercial DRAM Technology. InProceedings of the 48th Annual International Symposium on Computer Architecture (ISCA ’21). IEEE, 43–56. doi:10.1109/ISCA52012.2021.00013

    arXiv 2021