A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
Here’s a link to the paper “Tiny Pointers” https://arxiv.org/pdf/2111.12800 those editors at Quantamagazine writes their summary in a strange fashion, for instance using x in stead of n which is normally used in computer science when talking about big O notation.
In the article, x is not the size of the hash table, it is the inverse of the table’s filling fraction. A 1000-element table that is 90% full has x=10, N=1000.
Since they’re not discussing scaling of data sizes, would be confusing to use O(N) notation or people would make that assumption.
You are correct it’s an confusing article Quantamagazine have written, why do they start highlighting “Tiny Pointers” https://arxiv.org/pdf/2111.12800 when “Optimal Bounds for Open Addressing Without Reordering” https://arxiv.org/pdf/2501.02305 is the main paper, and it disproves part of Tiny Pointers.
Here’s a link to the paper “Tiny Pointers” https://arxiv.org/pdf/2111.12800 those editors at Quantamagazine writes their summary in a strange fashion, for instance using x in stead of n which is normally used in computer science when talking about big O notation.
In the article, x is not the size of the hash table, it is the inverse of the table’s filling fraction. A 1000-element table that is 90% full has x=10, N=1000.
Since they’re not discussing scaling of data sizes, would be confusing to use O(N) notation or people would make that assumption.
This is the paper the article is about: https://arxiv.org/pdf/2501.02305
You are correct it’s an confusing article Quantamagazine have written, why do they start highlighting “Tiny Pointers” https://arxiv.org/pdf/2111.12800 when “Optimal Bounds for Open Addressing Without Reordering” https://arxiv.org/pdf/2501.02305 is the main paper, and it disproves part of Tiny Pointers.