A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.

Sometime in the fall of 2021, Andrew Krapivin, an undergraduate at Rutgers University, encountered a paper that would change his life. At the time, Krapivin didn’t give it much thought. But two years later, when he finally set aside time to go through the paper (“just for fun,” as he put it), his efforts would lead to a rethinking of a widely used tool in computer science.

The paper’s title, “Tiny Pointers,” referred to arrowlike entities that can direct you to a piece of information, or element, in a computer’s memory. Krapivin soon came up with a potential way to further miniaturize the pointers so they consumed less memory. However, to achieve that, he needed a better way of organizing the data that the pointers would point to.

...read more at quantamagazine.org