Tiny Pointers

Michael A. Bender

doi:10.1145/3700594

Tiny Pointers

2025-10-01

0

OA

AI

Martı́n Farach-Colton

DOI：10.1145/3700594

查看原文

摘要

En 中文

本文介绍了一种新的数据结构对象，我们称之为tiny pointer。在许多应用中，传统的log n位指针可以用o(log n)位的tiny pointer替代，代价仅为常数倍的时间开销和较小的失败概率。我们发展了tiny pointer的全面理论，并给出了固定大小tiny pointer（即所有tiny pointer必须大小相同）和可变大小tiny pointer（即平均tiny pointer大小必须较小，但部分tiny pointer可以较大）的最优构造方法。如果tiny pointer引用了一个填充因子为1-delta的数组中的项目，则固定大小情况下最优的tiny pointer大小为O(log log log n + log delta(-1))位，可变大小情况下为O(log delta(-1))期望位。我们的tiny pointer构造还要求我们重新审视几个与球和桶相关的经典问题；这些结果可能具有独立的研究价值。使用tiny pointer，我们将tiny pointer应用于五种经典数据结构问题。我们证明：-存储n个v位值、对应n个键的数据结构，若修改/查询时间为常数倍，则可实现的存储空间为nv + O(n log((r))n)位，对于任意常数r > 0，只要用户为每个键存储一个期望大小为O(1)的tiny pointer（其中log((r)) n为r次迭代对数）。-任何二叉搜索树都可以被压缩，即达到最优空间的(1 + o(1))倍，时间开销为常数倍，甚至允许O(log(& lowast;) n)时间修改时，可达到最优空间n位以内——这一点对旋转树（如splay tree和red-black tree）也成立。-任何固定容量的键值字典都可以在常数倍时间开销和(1 + 0(1))倍空间开销下实现稳定（即插入后项目不移动）。-任何要求统一大小值的键值字典，都可以在常数倍时间开销下支持任意大小值，且每个I位值的额外空间消耗为log((r)) n + O(log j)位，其中r > 0为任意常数。给定一个外部存储数组A，大小为(1 + epsilon)n，包含最多n个键值对的动态集合，可以通过维护一个大小为O(n log epsilon(-1))位的内部存储stash，使得A中任何键值对的位置能在常数时间内计算（且无需I/O操作）。在每种情况下，tiny pointer允许我们将原本空间低效的指针解决方案转化为免费的空间高效方案。

Keyword:

pointers

space-efficient

balanced allocation

balls and bins

hashing

load balancing

randomized algorithms

retrieval

Tiny Pointers

摘要

AI总结

期刊

机构

引用论文