Cover Image

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kuszmaul, William, Liang, Jingxun, Zhou, Renfei
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fingerprint Filters Are Optimal
by: Kuszmaul, William, et al.
Published: (2025)

Optimal Static Fully Indexable Dictionaries
by: Liang, Jingxun, et al.
Published: (2025)

Static Retrieval Revisited: To Optimality and Beyond
by: Hu, Yang, et al.
Published: (2025)

Optimal Non-Oblivious Open Addressing
by: Bender, Michael A., et al.
Published: (2025)

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
by: Kuszmaul, William, et al.
Published: (2024)

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

SPIDER: Improved Succinct Rank and Select Performance
by: Laws, Matthew D., et al.
Published: (2024)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
by: Kuszmaul, William
Published: (2025)

Tight Analyses of Ordered and Unordered Linear Probing
by: Braverman, Mark, et al.
Published: (2025)

Scheduling Jobs with Work-Inefficient Parallel Solutions
by: Kuszmaul, William, et al.
Published: (2024)

The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
by: Kuszmaul, William, et al.
Published: (2021)

Succinct Data Structures for Segments
by: Bille, Philip, et al.
Published: (2024)

Efficient $d$-ary Cuckoo Hashing at High Load Factors by Bubbling Up
by: Kuszmaul, William, et al.
Published: (2025)

Succinct Data Structures for Baxter Permutation and Related Families
by: Chakraborty, Sankardeep, et al.
Published: (2024)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
by: Balakrishnan, Girish, et al.
Published: (2023)

Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
by: Ferragina, Paolo, et al.
Published: (2025)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Succinct Planar Encoding with Minor Operations
by: Kammer, Frank, et al.
Published: (2023)

Succinct Graph Representations and Algorithmic Applications
by: Ullah, Ahammed, et al.
Published: (2026)

Succinct Encodings of Binary Trees with Application to AVL Trees
by: Chizewer, Jeremy, et al.
Published: (2023)

A Nearly Quadratic Improvement for Memory Reallocation
by: Farach-Colton, Martin, et al.
Published: (2024)

History-Independent Load Balancing
by: Bender, Michael A., et al.
Published: (2026)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
by: Kenneth, Yotam, et al.
Published: (2023)

Optimal Bounds for Open Addressing Without Reordering
by: Farach-Colton, Martin, et al.
Published: (2025)

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
by: Hammer, Nina, et al.
Published: (2022)

The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
by: Munch, Elizabeth, et al.
Published: (2025)

Layered List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings
by: Elberfeld, Michael, et al.
Published: (2025)

Vantage Point Selection Algorithms for Bottleneck Capacity Estimation
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
by: Kirkpatrick, Yael, et al.
Published: (2026)

Engineering Rank/Select Data Structures for Large-Alphabet Strings
by: Arroyuelo, Diego, et al.
Published: (2023)

Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Succinct Preferential Attachment Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
by: Bartal, Yair, et al.
Published: (2024)

Efficient Dynamic Rank Aggregation
by: Alimi, Morteza, et al.
Published: (2025)

Dynamic Rank, Basis, and Matching
by: Brand, Jan van den, et al.
Published: (2026)

Theory Meets Practice for Bit Vectors Supporting Rank and Select
by: Kurpicz, Florian, et al.
Published: (2025)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)