“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.”
Tiny Pointers
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 条,统计用全部提及“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…”
“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…”
- Tiny Pointers ↗aaossa · 2025-02-10 · 2 分
- Tiny Pointers ↗KnuthIsGod · 2025-02-11 · 4 分
- Tiny Pointers ↗levzettelin · 2025-02-12 · 163 分