Undergraduate Upends a 40-Year-Old Data Science Conjecture | Quanta Magazine
A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
Hasnain says:
Gotta love new breakthroughs. This was really cool and interesting and I’ll have to read the paper
“Farach-Colton, Krapivin and Kuszmaul wanted to see if that same limit also applied to non-greedy hash tables. They showed that it did not by providing a counterexample, a non-greedy hash table with an average query time that’s much, much better than log x. In fact, it doesn’t depend on x at all. “You get a number,” Farach-Colton said, “something that is just a constant and doesn’t depend on how full the hash table is.” The fact that you can achieve a constant average query time, regardless of the hash table’s fullness, was wholly unexpected — even to the authors themselves.”
Posted on 2025-02-12T02:28:22+0000