SPIDER: Fast rank and select queries

Paper Title:

SPIDER: Improved Succinct Rank and Select Performance

Published on:

8 May 2024

Primary Category:

Data Structures and Algorithms

Paper Authors:

Matthew D. Laws,

Jocelyn Bliven,

Kit Conklin,

Elyes Laalai,

Samuel McCauley,

Zach S. Sturdevant

Bullets

Key Details

•

Introduces SPIDER, a fast new succinct rank/select data structure

•

Uses just 3.82% extra space, outperforms prior approaches

•

Optimized for cache efficiency via metadata interleaving

•

Predictions accelerate select queries, inspired by learned indices

•

New best rank query times on large inputs; narrowed select time gap

Explore the topics in this paper

bit vectors

rank operations

select queries

space efficiency

sparse data structures

AI generated summary

SPIDER: Fast rank and select queries

This paper introduces SPIDER, a new succinct data structure for answering rank and select queries on bit vectors. SPIDER uses only 3.82% extra space, yet outperforms prior methods. For rank queries, SPIDER is the fastest known method on large inputs. For select queries, it narrows the performance gap between space-efficient and less space-efficient techniques. Key ideas include interleaving metadata with the bit vector to improve cache performance, and using predictions to accelerate select queries.