Approximately 70 years ago, an engineer named Hans Peter Luhn, working at IBM, made a significant impact on the field of computer science. Luhn had already secured multiple patents, including one for a device capable of measuring the thread count of a cloth and another for a guide that determined the mixed drinks one could create using ingredients found in their kitchen.
In a 1953 internal IBM paper, a new technique for storing and retrieving information was proposed. This technique, known as the hash table, has since been incorporated into nearly all computational systems.
Hash tables are a significant category of data structures. They provide a highly convenient way to access and modify information in large databases. However, there is an inevitable trade-off that comes with this technology.
W. Wesley Peterson highlighted the main technical challenge that hash tables present in a 1957 paper that appeared in the IBM Journal of Research and Development. Efficiency is crucial, as they must be able to retrieve the necessary information quickly. However, it is important for them to be small in size and use minimal memory. These twin objectives are inherently contradictory. When the hash table has more memory, accessing and modifying a database can be done more quickly. On the other hand, hash tables that use less space tend to make operations slower. Since Peterson presented this challenge, researchers have been striving to discover the optimal equilibrium between time and space.
Computer scientists have recently mathematically proven that they have discovered the most efficient balance. The solution emerged from a duo of recent papers that nicely complemented each other. “These papers address a longstanding question regarding space-time trade-offs and present unexpected results that are expected to have a lasting impact,” commented Michael Mitzenmacher, a computer scientist at Harvard University who was not involved in the studies.
“I would certainly say it’s significant,” remarked Rasmus Pagh, a computer scientist at the University of Copenhagen. Many individuals have dedicated their efforts to tackling this problem, striving to maximize space utilization without compromising on time efficiency. This is the one I would have really enjoyed solving.
Making a Hash of It
Hash tables have stood the test of time and remain a fundamental and efficient data structure that is widely utilized. These operations serve three fundamental purposes: adding new items to the database, accessing or checking the existence of an item, and removing items. A hash table can have a temporary lifespan, only existing while a specific program is running, or it can be a permanent component of your computer’s operating system. Web browsers like Chrome or Safari often come equipped with multiple built-in hash tables designed to manage various types of data.
In a hash table, the entries are stored as pairs, where each pair consists of an item and a key. The key is used to identify the corresponding information. When a key is plugged into a hash table’s query algorithm, it will efficiently lead you straight to the corresponding item. Although it may not seem particularly remarkable, this feature can be incredibly useful for large databases, saving a significant amount of time.
Let’s take a very simple example, like the Oxford English Dictionary, which contains definitions for over 600,000 words. If a digital edition utilizes a hash table, you can easily employ a provided word as a key and directly access the definition. Without a hash table, the dictionary would depend on a slower search mechanism, where it would gradually narrow down the options to find the requested definition. Hash tables are incredibly efficient at finding words, taking only a fraction of a second, regardless of the size of the dictionary. However, other methods may experience longer search times as the number of words in the dictionary grows. Another advantage of a hash table is its ability to keep the dictionary dynamic, allowing for easy insertion of new words and deletion of outdated ones.
Researchers have dedicated extensive time and effort to constructing hash tables that aim to optimize speed and memory usage. In the 20th century, solutions often focused on providing substantial improvements in either time or space. Later in 2003, researchers demonstrated the potential for a significant improvement in efficiency, both in terms of time and space. It took researchers another two decades to determine the optimal balance between the two.
The Data Shuffle
In 2022, a significant milestone was achieved at a prominent computer science conference held in Rome. At that location, a group put forward a hash table with innovative features that promised unparalleled efficiency in terms of both time and space. The first author of the paper (listed alphabetically) was Michael Bender of Stony Brook University, so it is commonly known as the Bender et al. hash table. Although the team did not attempt to create a working hash table, they demonstrated that it could potentially be built based on the features they described.
The group created a trade-off curve to assess the performance of the hash table they developed. This curve is a graphical representation that illustrates the time per operation (insertion or deletion) on one axis and the memory space required on the other. However, it is worth noting that this graph presents a unique perspective on space. Due to their construction, hash tables require additional memory beyond the absolute minimum needed to store a specific set of items. Computer scientists refer to this additional space as “wasted bits,” although they are not truly wasted and serve a certain purpose. The space axis on a trade-off curve quantifies the number of bits that are not utilized efficiently for each key.
Through the analysis of a trade-off curve, researchers can determine the optimal speed for a hash table based on a specific amount of space. One can also reverse the question to determine the minimum space required for a specific operation time. According to William Kuszmaul, a theoretical computer scientist at Harvard and co-author of the 2022 paper, a small change in one variable typically results in a corresponding small change in the other. By doubling the time, you might be able to reduce the number of wasted bits per key.
However, the hash table they designed is an exception to this. “By increasing the time slightly, the number of wasted bits per key decreases exponentially,” stated Kuszmaul. The trade-off curve was extremely steep, surpassing all expectations.
The team constructed their hash table in two separate sections. They utilized a highly efficient primary data structure that stored items without any unnecessary bits, along with a secondary data structure that facilitated quick retrieval of queried items. Although the group did not come up with the concept of a secondary data structure, they did make a significant breakthrough that enabled the creation of their highly efficient hash table: The primary structure’s method of organizing its stored items determines the structure’s overall memory efficiency.
Each item in the primary structure is assigned preferred storage locations, ranked from best to worst. When an item is in its optimal position, it is marked with the number 1 and stored in the secondary data structure. When asked about the query, the secondary structure gives a precise location in the primary structure by providing the number 1.
When the item is ranked as the 100th best, the secondary data structure assigns it the number 100. Furthermore, due to the utilization of binary, the system accurately portrays the numerical value 100 as 1100100. Storing the number 1100100 requires more memory compared to the number 1, which is assigned to an item in the best spot. These differences become quite significant when you’re dealing with a large number of items, such as a million.
After careful analysis, the team discovered a way to optimize memory consumption in the secondary structure without sacrificing query times. By continuously rearranging items in the primary data structure to their preferred locations, significant memory reduction can be achieved.
“No one had previously recognized the potential to enhance data compression by reorganizing information,” Pagh explained. “That was a significant revelation in the Bender paper.”
The authors demonstrated that their invention set a new standard for the most efficient hash tables, making it the most optimal data structure in terms of both time and space efficiency. However, there was still a chance that someone else could achieve even greater success.
Bound to Succeed
In an effort to enhance the hash table developed by the Bender team, a group led by Huacheng Yu, a computer scientist at Princeton University, embarked on a project the following year. “We put in a lot of effort, but unfortunately, we were unable to achieve our goal,” expressed Renfei Zhou, a student at Tsinghua University in Beijing and a member of Yu’s team. It was at that moment when we began to suspect that their upper bound was actually a lower bound – the absolute best outcome that could be attained. “Once the upper bound matches the lower bound, that’s when the game comes to an end and you’ll have your answer.” Regardless of one’s intelligence, a hash table cannot yield superior results.
Yu’s team used a unique approach to confirm their suspicion by calculating a minimum value based on fundamental principles. They concluded that in order to perform an insertion or deletion, a hash table, or any data structure for that matter, needs to access the computer’s memory a certain number of times. By determining the minimum number of times necessary for a hash table that conserves space, one could then multiply it by the constant time required per access. This would provide a lower estimate for the overall runtime.
However, without prior knowledge of the hash table, other than its space efficiency, it becomes a challenge for the researchers to determine the minimum number of memory accesses needed. They discovered it solely through theoretical analysis, drawing from a seemingly unrelated field known as the theory of communication complexity. This field examines the number of bits needed to transmit information between two parties. Finally, the team achieved their goal: They determined the number of memory accesses a data structure needs for each operation.
This was their most significant accomplishment. They were able to determine the minimum amount of time it would take for a space-efficient hash table to run. They observed that it perfectly aligned with the Bender hash table. “Initially, we believed it could be enhanced,” Zhou stated. We discovered that our initial assumption was incorrect. As a result, Peterson’s problem was finally resolved.
In addition to addressing the long-standing question, Kuszmaul mentioned that the remarkable aspect of the Yu proof lies in its wide applicability. “The lower bound is applicable to all potential data structures, even those that have not yet been created.” It’s clear that the Bender hash table is unmatched when it comes to memory and speed, making it the ultimate choice for data storage.
Hashing Into the Future
Although the new hash table is incredibly efficient, it seems unlikely that anyone will attempt to build it in the near future. Constructing it is quite complex. “A fast algorithm in theory may not always translate to fast performance in practice,” Zhou remarked.
According to Kuszmaul, it is common for discrepancies between theory and practice to endure for a significant period of time. This is often due to theorists disregarding constant factors. When performing an operation, there is usually a constant number that multiplies the time it takes. The specific value of this constant may not matter from a theoretical perspective. “But in practice, constants are truly important,” he stated. “In the real world, a factor of 10 can completely change the outcome.”
Hash tables continue to make advancements in their design and functionality, although they have not yet reached the theoretical ideal. For instance, Bender, Kuszmaul, and other researchers created the new hash table named IcebergHT. It has proven to be significantly superior to previous versions. According to Kuszmaul, it is significantly faster than the most space-efficient hash table currently available, while also using significantly less space than the fastest hash table.
Mitzenmacher expresses optimism for the potential benefits that may arise from the 2023 result. The discovery of a new lower bound, particularly one that involves innovative techniques, often opens up possibilities for tackling related problems.
According to computer scientist Piotr Indyk of the Massachusetts Institute of Technology, there is a sense of intellectual satisfaction that accompanies the resolution of a challenging and persistent problem. “When it is determined that specific data structures cannot be enhanced any further, it can help to concentrate the research effort.” At long last, data researchers can shift their focus from Peterson’s challenge and delve into the abundance of new problems in theoretical computer science.
