In a 1985 paper, computer scientist Andrew Yao, who would win the AM Turing Award, argued that the best way to find an individual element or an empty place is under hash tables with a specific set of properties to go through randomly -an approach known as a uniform investigation. He also said that in the worst scenario, where you are looking for the last remaining open place, you can never do better than x. For 40 years, most computer scientists have accepted that the assumption of Yao was true.
Krapivin was not withheld by conventional wisdom for the simple reason he was unaware of it. “I did it without knowing about Yao’s assumption,” he said. His investigations with small tips led to a new type of hash table – one that did not relate to uniform investigation. And for this new hash table is the time required for the worst cases and insertions proportional to (log x)2—Var faster than x. This result directly contradicted the assumption of Yao. Farach-Colton and Kuszmaul helped Krapivin show it (log x)2 is the optimal, unbeatable bound for the popular class hash tables you wrote about.
“This result is beautiful in that it addresses and solve such a classic problem,” says Guy Blelloch of Carnegie Mellon.
“It’s not just that they refute [Yao’s conjecture]They also found the best possible answer to his question, ”said Sephr Assadi of the University of Waterloo. “We were able to know the right answer for another 40 years.”
In addition to the revival of Yao’s assumption, the new article also contains which many people consider an even more astonishing result. This relates to a related, although slightly different, situation: In 1985, Yao not only looked at the worst cases for queries, but also at the average time taken on all possible queries. He has proven that hash tables with certain properties – including those mentioned as ‘greedy’ means that new elements must be placed in the first available place – can never reach an average time better than log x.
Farach-Colton, Krapivin and Kuszmaul wanted to see if the same limit also applies to non-crazy hash tables. They have shown that this is not done by providing a counter-example, a non-geared hash table with an average query time that is much, much better than log x. In reality it is not dependent x Not at all. “You get a number,” Farach-Colton said, “something that is just a constant and does not depend on how full the hash table is.” The fact that you can reach a constant average question time, regardless of the fullness of the hash table, was completely unexpected – even for the writers themselves.
The results of the team may not lead to immediate applications, but that’s not all that matters, Conway said. ‘It is important to better understand these kinds of data structures. You do not know when a rash like this will unlock something that you can do better in practice. ‘
Original story Reprinted with permission from Quanta Magazine, an editorial independent publication of the Simons Foundation whose mission is to improve the public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.