• Paper Introduction: Introduces a new data-structural object called the tiny pointer. In many applications, traditional $\\log n $-bit pointers can be replaced with $o (\\log n )$-bit tiny pointers with a constant-factor time overhead.
• Research Contributions: Develops a comprehensive theory of tiny pointers, providing optimal constructions for fixed-size and variable-size tiny pointers. If a tiny pointer references an element in an array with a load factor of $1 - 1 / k$, the optimal sizes are $\\Theta(\\log \\log \\log n + \\log k) $ bits in the fixed-size case and $ \\Theta (\\log k) $ expected bits in the variable-size case. The constructions also involve revisiting classic problems related to balls and bins.
• Applications: Uses tiny pointers to revisit five classic data-structure problems including the data-retrieval problem, succinct dynamic binary search trees, space-efficient stable dictionaries, space-efficient dictionaries with variable-size keys, and the internal-memory stash problem. Tiny pointers make natural space-inefficient solutions using pointers become space-efficient without additional cost.
• Subject and Citation Information: Belongs to the field of Data Structures and Algorithms (cs.DS). Cite as arXiv:2111.12800 [cs.DS] (or arXiv:2111.12800v1 [cs.DS]) and https://doi.org/10.48550/arXiv.2111.12800. Submission history shows it was from Guido Tagliavini on Wed, 24 Nov 2021 21:14:33 UTC with a file size of 165 KB.