按年被提到
20212025 · 6 次2026
算法与数据结构›经典算法与数据结构·arXiv:2111.12800 · cs.DS

Tiny Pointers

Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini · 2021
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 6 人首次 2025-02-10 · 最近 2025-03-20
6不同的人
2活跃月份
5讨论串
0被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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. 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 - 1 / k$, then the optimal tiny-pointer size is $Θ(\log \log \log n + \log k) $ bits in the fixed-size case, and $ Θ(\log k) $ 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: 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. These are all well-studied 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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论isaacfrond · 2025-02

“The paper is here: https://arxiv.org/pdf/2111.12800 Curiously, Andrew Krapivin, the genious undergrad in the article, is not one of the authors.”

Undergraduate shows that searches within hash tables can be much faster原评论 ↗
评论mangodrunk · 2025-02

“Well said. I really dislike the narrative here, that ignorance is something that leads to discovery. One, the poster gives two examples, as if there's something we should gain for such a small sample. In addition to that, one of the examples isn't valid. The student's former professor is a co-author of the "Tiny Pointers" [1] paper that he was reading and…”

Undergraduate shows that searches within hash tables can be much faster原评论 ↗
评论PaulHoule · 2025-03

“For a long time I've thought about various sorts of weird pointer organization (think of the compressed pointers used in modern JVMs or "tiny pointers" [1] or 8086 code that uses a 16-byte aligned segment pointer to point to a struct or array and uses and ordinary pointer to point to things inside that structure) It doesn't seem too weird to me to make s…”

Ask HN: Why some languages use 1 byte for boolean type原评论 ↗
被提交为 story · 3 次