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.
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.
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.
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.
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.
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.