CS Paper Radar

FastHeapDict: Permanent Slot Indexing for Efficient Decrease-Key Operations in Indexed Priority Queues

Hojjat T. Goudarzi, Arash Torabi Goodarzi, Mohammad Amir Eshraghi

cs.DS ·submitted 2026-10-30 00:22 UTC · v1
code/data

Abstract

Efficient decrease-key support remains an important practical concern in priority queues used by shortest-path and graph-processing algorithms. Although duplicate-entry heaps avoid explicit decrease-key operations and are simple to implement, they may accumulate many stale entries when tentative priorities are repeatedly improved. This paper presents FastHeapDict, an indexed binary min-heap based on permanent slot indexing. Instead of repeatedly locating keys through hash-table lookups during heap repair, FastHeapDict assigns each key a stable integer slot and stores that slot directly in heap entries. As a result, position updates during sift-up and sift-down operations are performed through integer indexing while preserving the usual indexed-heap interface. We evaluate FastHeapDict in both Python and C++20 using Dijkstra's algorithm as the primary experimental workload. The benchmarks include constructed dense stress graphs, randomized dense graph variants, and comparisons against duplicate-entry heaps and existing priority-queue alternatives. Across the tested Python workloads, FastHeapDict consistently outperforms the duplicate-entry heapq baseline and the tested heapdict and pqdict implementations. In the C++20 implementation, FastHeapDict also achieves strong constant-factor improvements over std::priority_queue duplicates, std::set-based decrease-key, and std::multiset duplicates. These results indicate that permanent slot indexing can provide a compact and effective implementation strategy for indexed priority queues in workloads where priority updates are frequent.

Comment
9 pages, 8 figures. Preprint; Python and C++20 implementations. Source code and benchmark artifacts available at https://github.com/hojjatgoudarzi/FastHeapDict

Closest papers

Nearest neighbours by meaning across the whole index.

GrAND: GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search

cs.DC cs.DB ·2026-08-21 ·Karthik Venkatasubba, Shivendra Deshpande, Shivram S, Jyothi Vedurada
similarity 0.62
Abstract

Modern Approximate Nearest Neighbour Search (ANNS) applications operate over continuously evolving vector collections and require graph indexes that sustain high-throughput searches while incorporating insertions and deletions with high recall. However, most GPU graph indexes are static or provide limited update support. Updates require neighbour discovery, reverse-edge creation, pruning, and deletion-induced graph repair; executing these operations concurrently introduces redundant distance computations and conflicting accesses to shared adjacency lists. Background-rebuild-based deletion further incurs substantial computation, additional memory consumption, and interference with foreground queries. We present GrAND (GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search), a GPU-native collection of dynamic-update algorithms for two popular graph indexes, Vamana and CAGRA. GrAND consolidates graph repair across a batch, eliminating redundant pruning computations, and employs a lock-free find-and-replace strategy for parallel adjacency-list updates. For reliable in-place deletion, GrAND constructs an on-demand reverse graph on the GPU, accurately identifying incoming edges without permanently duplicating the index. We evaluate GrAND on seven real-world datasets across five streaming workloads, comparing it against SVFusion and FreshDiskANN-GPU (our GPU adaptation of FreshDiskANN). GrAND improves overall workload throughput by 2.2x-8.7x and 6.5x-25.4x, respectively, while maintaining high search throughput and recall over sustained updates.

0.14

Synchronized Rebuilds:The Hidden Cost of Concurrent Inserts in Learned Indexes

cs.DB ·2026-10-24 ·Emmilly Immaculate Namuganga, Laurent Bindschaedler
benchmark similarity 0.62
Abstract · 15 pages, 4 figures, 4 tables

Nine years after learned indexes were proposed, their advantage on read-mostly data is well established, and a standard benchmark rates their best concurrent version as almost ready for use. Across more than 4000 runs of 13 indexes, we find that each design pays for concurrent inserts in a different way. Gapped-array indexes rebuild their nodes in synchronized bursts, at positions that follow from three constants in the source. Model-placement indexes use three to four times the memory, buffered indexes take two to three times as long. Three of five concurrent learned indexes lost keys or stopped making progress. Standard benchmarks miss both the bursts and the lost keys. The bursts cost far more than in B-trees because each rebuild copies a node a thousand times larger than a page and, under concurrency, blocks every operation that reaches the node. The typical B-tree fix of randomizing node density only spreads the bursts out, while smaller nodes trade them for longer run times at scale. Two standard systems techniques remove them: a buffer that exists only while a node is rebuilt, and background rebuilds. We show that on 400M real keys, these techniques reduce the number of inserts whose latency exceeds 100$μ$s by two orders of magnitude at one thread, and by one at sixteen when spare cores run the background threads, at a third to half the run time of the buffered designs.

0.32

PaB-tree: Parallel B+-tree with Batch Updates

cs.DS cs.DBcs.DC ·2026-11-06 ·Ziyang Men, Yan Gu, Yihan Sun, Helen Xu
similarity 0.62
Abstract

The B+-tree is a ubiquitous search index due to its provable I/O (cache) efficiency. Yet unlike batch-parallel binary search trees, which are both fast and widely available, no batch-parallel B+-tree offers strong empirical performance together with provable, near-optimal I/O efficiency. Prior B+-tree-based designs are either parallel but purely theoretical, with no high-performance implementation, or concurrent indexes such as the Bw-tree and Masstree, which run an order of magnitude slower on batch updates. We present PaB-tree, the first batch-parallel B+-tree with guarantees on work, span, and cache complexity alongside strong practical performance. Its core challenge -- repairing node overflows and underflows without eroding the tree's I/O advantage -- is resolved by one simple invariant: a repair never touches a sibling and is always pushed to the parent. A Promote primitive reduces batch construction and insertion to repeated node promotion, and batch deletion to reinsertion. Batch updates take O(B log_B n) work and O(log_B n) I/O per element, matching the sequential B+-tree bounds, with polylogarithmic span. Against highly-optimized parallel and concurrent baselines, PaB-tree delivers the best overall performance trade-off: up to 1.4x faster on construction and up to 3.6x faster on batch insertion than the strongest baseline, while preserving B+-tree query efficiency.

0.15

CHERI-D Reincarnate: efficient multicore CHERI temporal memory safety through allocation reincarnation (draft version)

cs.AR cs.CR ·2026-09-10 ·Yuecheng Wang, Jonathan Woodruff, Simon W. Moore
similarity 0.61
Abstract

We propose CHERI-D Reincarnate (Reinc), an architectural extension to CHERI for scalable and efficient temporal memory safety. Prior work CHERI-D has a finite-width generation ID stored at a fixed location, requiring an object to be quarantined when its ID is exhausted. Reinc further provides use-after-free mitigation while permitting immediate freed memory reuse for objects through allocation reincarnation: rather than quarantining an allocation slot upon ID exhaustion, Reinc dynamically assigns a new ID to that slot when its current ID is exhausted. Exhausted IDs are quarantined and later reclaimed, while the underlying memory remains available for immediate reuse. By quarantining IDs rather than memory, Reinc enables continuous reuse of memory in the common case, substantially reducing both memory-sweep frequency and quarantine memory overhead. Reinc further introduces coherent ID caching while retaining a fully decentralized ID organization. Temporal metadata remains colocated with the memory it protects, preserving locality while avoiding centralized metadata structures. To support multicore execution, Reinc connects physical coherence events to the virtually addressed ObjID buffer using lightweight reverse-map and filter-based mechanisms. We implement Reinc as a hardware-software co-design spanning CHERI-Toooba (superscalar FPGA softcore), QEMU, LLVM/Clang and CheriBSD. Across our evaluated workloads, Reinc substantially reduces memory-sweep frequency and memory quarantine while incurring low performance and hardware overhead.

0.28

Revisiting Index Performance under High Cache-Miss Penalties

cs.DB ·2026-11-16 ·Mathew M. Kim, Beomseok Nam
similarity 0.60
Abstract

Modern data-intensive applications often query very large datasets, making index performance critical. Recent index structures exploit the fine-grained access capabilities of emerging storage devices such as DCPMM and CXL. However, existing benchmarks typically evaluate indexes in isolation using saturated, closed-loop workloads that emphasize maximum throughput. Such workloads favor highly concurrent designs while overlooking the application work that follows an index lookup and competes for cache, memory bandwidth, and CPU resources. We present AuxBench - a microbenchmark that evaluates indexes as auxiliary access paths within larger application workloads. Using AuxBench, we evaluate four byte-addressable indexes under controlled post-lookup memory activity, concurrency, and request arrival patterns. Our experiments show that post-lookup memory activity can change the relative performance of competing indexes, that concurrency-oriented designs may lose their advantages when substantial application work is introduced, and that time-varying request arrivals can produce severe tail latency near saturation. These findings demonstrate why index-only benchmarks may not adequately predict performance in larger application workloads

0.22

SARP: An On-SSD Index for KVCache with Fast Prefix Matching and Recovery

cs.DB ·2026-10-19 ·Jun Kong, Qi Lin, Zhichao Cao
similarity 0.59
Abstract

Distributed LLM serving relies on a global index to locate reusable key-value cache (KVCache) blocks through prefix matching. Losing the index after a crash or restart forces affected requests to recompute existing KVCache on GPUs. Persisting the index restores access after a failure. Existing persistent indexes face a tension between prefix-matching performance and recovery time. A snapshot-backed in-memory index supports fast prefix matching, but rebuilding the full index delays recovery. An on-SSD index avoids this rebuild, but adds storage accesses to prefix matching. Our core insight is that extending a matched prefix over a short span typically requires distinguishing only a few token sequences, suggesting that sparse in-memory routing state may suffice. Prefix matching also accesses block metadata in sequence order, allowing metadata for consecutive blocks to be retrieved together. We present SARP (Sparse Adaptive Routing and Packing), an on-SSD KVCache index for fast recovery and prefix matching. SARP groups consecutive block IDs and metadata into segments to amortize storage accesses across multiple blocks. A compact in-memory routing directory identifies candidate segments using entries at selected block positions. SARP limits segment retrievals and uses compact filters to prioritize candidates with longer potential matches. After retrieval, SARP verifies block IDs against the query and reuses only KVCache blocks covered by the verified prefix. After a restart, SARP restores the sparse routing directory from a snapshot. Across four multi-turn chat and agentic workloads, SARP recovers 8.0x to 77.5x faster than the in-memory index baselines and delivers 1.15x to 66.6x the request throughput of the on-SSD index baselines, while reusing only 0.0030% to 0.029% fewer tokens than exact prefix matching.

0.24

LeanSparse: Memory-Efficient Serving for Native Sparse-Attention LLMs

cs.DC ·2026-11-03 ·Zaifeng Pan, Chris Wu, Xinwei Qiang, Zhengding Hu, Zhongkai Yu +1 more
similarity 0.59
Abstract

Sparse attention limits the history read by each query, but serving long contexts still requires substantial GPU memory. Existing KV offloading systems retain the full history of indexer keys on GPU, limiting decode concurrency. Prefill's temporary memory demand can further delay admission even when enough memory remains for the same request's subsequent decode. We present LeanSparse, a serving system that reduces both decode's persistent memory use and prefill's temporary memory demand. Our design exploits two observations: prefill consumes historical data one layer at a time, and decode can identify promising candidates before comparing their original indexer scores. During prefill, LeanSparse streams layer histories through two reusable GPU buffers, overlapping next-layer loading with ongoing model computation. During decode, coarse-to-fine indexing searches compact representations and retrieves original indexer keys only for candidate refinement. Separate indexer key and KV caches reuse data across generation steps. We implement LeanSparse in SGLang and evaluate it on DeepSeek-V4-Flash. At 950K context length, LeanSparse supports 2.95$\times$ as many concurrent requests and achieves 2.14$\times$ decode throughput over HiSparse. On multi-turn Open-SWE traces, it reduces median time to first token from 21.6 to 0.6s and median session completion time by 17.7% relative to ECHO.

0.16

Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage

cs.DB ·2026-11-02 ·Zehai Yang, Fengyi Tao, Wenzhuo Dong, Shimin Chen
similarity 0.58
Abstract

Large-scale ANNS systems often exploit storage in addition to DRAM for supporting vector search. The central question is how to divide the work between memory and storage for achieving both high query throughput-recall and good index maintenance performance. Existing storage-optimized ANNS paradigms fall short of providing a complete answer: disk-resident graph indexes have difficulty in supporting efficient vector deletions, while posting-list systems often incur more disk I/Os for queries. In this paper, we introduce a refinement-centered paradigm for storage-optimized ANNS systems. We propose Recast as a concrete design of this paradigm. Recast stores raw vectors on disk and keeps an IVF index with our RecastQ quantization encoding in memory. For an ANNS query, Recast selects nprobe inverted lists and performs SIMD-based FastScan on their RecastQ codes to identify refinement candidates in memory. It then retrieves candidate vectors from disk, computes exact distances, and refines the top-K result. To reduce disk I/Os, RecastQ computes uncertainty intervals containing true distances with high probability. Our QUIC policy selects a minimal refinement set based on these intervals, minimizing candidate-retrieval I/Os. Both the on-disk raw vectors and the in-memory IVF structure support insertions and deletions. Experiments on real-world data sets show that Recast processes batched insertions and deletions 3.10-37.27x faster than SPFresh and OdinANN, while its QPS at 0.99 recall changes by at most 6.9% after updating 50% of the corpus. For static queries at 0.99 recall, Recast achieves 1.56-2.01x the QPS of the strongest baseline with the matched memory budget on each data set, while requiring 1.22-6.75x less external storage than the evaluated systems. At matched in-memory space, RecastQ also provides a better Recall-refinement frontier than RaBitQ.

0.13