# Space-efficient Static Trees and Graphs

Guy Jacobson

(presented by Vaibhav Sagar (@vbhvsgr))

# Data structures take up too much space!

## A pointer to *n* possible locations needs log_{2}*n* bits

## Data structures with *n* items need *O*(*n*log_{2}*n*) space for pointers!

## The rent is too damn high!

## Unlabeled binary trees only need 2*n* + *o*(*n*) bits

## One approach: balanced parentheses?

## Better space usage, but inefficient to use

## How do we get efficient space usage *and* efficient operations?

## Metrics for space and time

- Space: measured in bits
- Time: measured in bit-accesses

## Rank

*r**a**n**k*_{e}(*S*, *i*): The number of *e*s at or before index *i*

## Select

*s**e**l**e**c**t*_{e}(*S*, *i*): The index of the *i*th *e*

## Time complexity

*O*(log_{2}*n*) at the time of writing, *O*(1) now!

## Rank/Select beyond bitmaps

## Implicit bitmap

## Level-order binary marked

## Level-order binary marked

*l**e**f**t*-*c**h**i**l**d*(*m*) = 2 ⋅ *r**a**n**k*(*m*)
*r**i**g**h**t*-*c**h**i**l**d*(*m*) = 2 ⋅ *r**a**n**k*(*m*) + 1
*p**a**r**e**n**t*(*m*) = *s**e**l**e**c**t*(⌊*m*/2⌋)

## Level-order unary degree sequence

## Level-order unary degree sequence

*f**i**r**s**t*-*c**h**i**l**d* = *s**e**l**e**c**t*_{0}(*r**a**n**k*(*m*)) + 1
*n**e**x**t*-*s**i**b**l**i**n**g* = *m* + 1
*p**a**r**e**n**t*(*m*) = *s**e**l**e**c**t*(*r**a**n**k*_{0}(*m*))

## Parentheses balancing

## Bounded pagenumber graphs

## Bounded pagenumber graphs

*n**o**d**e*-*t**o*-*e**d**g**e*(*m*) = *r**a**n**k*_{0}(*s**e**l**e**c**t*(*m*) + 1)
*e**d**g**e*-*t**o*-*n**o**d**e*(*e*) = *r**a**n**k*(*s**e**l**e**c**t*_{0}(*e*))

# Succinct data structures today

## Semi-indexing

## Compact Data Structures