## Abstract

This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional log n-bit pointers can be replaced with o(log n)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an element in an array filled to load factor 1 - δ, then the optimal tiny-pointer size is Θ(log log log n + log δ^{-1}) bits in the fixed-size case, and Θ(log δ^{-1}) expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we revisit five classic data-structure problems. We show that: • A data structure storing n v-bit values for n keys with constant-time modifications/queries can be implemented to take space nv + O(n log^{(r)} n) bits, for any constant r > 0, as long as the user stores a tiny pointer of expected size O(1) with each key-here, log^{(r)} n is the r-th iterated logarithm. • Any binary search tree can be made succinct with constant-factor time overhead, and can even be made to be within O(n) bits of optimal if we allow for O(log^{∗} n)-time modifications-this holds even for rotation-based trees such as the splay tree and the red-black tree. • Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-time overhead and 1 + o(1) space overhead. • Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-time overhead and with an additional space consumption of log^{(r)} n + O(log j) bits per j-bit value for an arbitrary constant r > 0 of our choice. • Given an external-memory array A of size (1 + ε)n containing a dynamic set of up to n key-value pairs, it is possible to maintain an internal-memory stash of size O(n log ε^{-1}) bits so that the location of any key-value pair in A can be computed in constant time (and with no IOs). These are all well studied and classic problems, and in each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.

Original language | English (US) |
---|---|

Title of host publication | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 |

Publisher | Association for Computing Machinery |

Pages | 477-508 |

Number of pages | 32 |

ISBN (Electronic) | 9781611977554 |

State | Published - 2023 |

Event | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy Duration: Jan 22 2023 → Jan 25 2023 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2023-January |

### Conference

Conference | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 |
---|---|

Country/Territory | Italy |

City | Florence |

Period | 1/22/23 → 1/25/23 |

## ASJC Scopus subject areas

- Software
- General Mathematics