Theoretical breakthrough might enhance knowledge storage

A trio of researchers that features William Kuszmaul—a pc science Ph.D. pupil at MIT—has made a discovery that might result in extra environment friendly knowledge storage and retrieval in computer systems.

The group’s findings relate to so-called “linear-probing hash tables,” which have been launched in 1954 and are among the many oldest, easiest, and quickest data constructions accessible immediately. Data constructions present methods of organizing and storing knowledge in computer systems, with hash tables being one of the vital generally utilized approaches. In a linear-probing hash desk, the positions by which info could be saved lie alongside a linear array.

Suppose, as an example, {that a} database is designed to retailer the Social Security numbers of 10,000 folks, Kuszmaul suggests. “We take your Social Security number, x, and we’ll then compute the hash function of x, h(x), which gives you a random number between one and 10,000.” The subsequent step is to take that random quantity, h(x), go to that place within the array, and put x, the Social Security quantity, into that spot.

If there’s already one thing occupying that spot, Kuszmaul says, “you just move forward to the next free position and put it there. This is where the term ‘linear probing’ comes from, as you keep moving forward linearly until you find an open spot.” In order to later retrieve that Social Security quantity, x, you simply go to the designated spot, h(x), and if it is not there, you progress ahead till you both discover x or come to a free place and conclude that x isn’t in your database.

There’s a considerably completely different protocol for deleting an merchandise, equivalent to a Social Security quantity. If you simply left an empty spot within the hash desk after deleting the knowledge, that might trigger confusion if you later tried to search out one thing else, because the vacant spot may erroneously counsel that the merchandise you are searching for is nowhere to be discovered within the database. To keep away from that downside, Kuszmaul explains, “you can go to the spot where the element was removed and put a little marker there called a ‘tombstone,’ which indicates there used to be an element here, but it’s gone now.”

This basic process has been adopted for greater than half a century. But in all that point, virtually everybody utilizing linear-probing hash tables has assumed that if you happen to enable them to get too full, lengthy stretches of occupied spots would run collectively to type “clusters.” As a outcome, the time it takes to discover a free spot would go up dramatically—quadratically, in reality—taking as long as to be impractical. Consequently, folks have been skilled to function hash tables at low capability—a apply that may precise an financial toll by affecting the quantity of {hardware} an organization has to buy and preserve.

But this time-honored precept, which has lengthy militated towards excessive load elements, has been completely upended by the work of Kuszmaul and his colleagues, Michael Bender of Stony Brook University and Bradley Kuszmaul of Google. They discovered that for purposes the place the variety of insertions and deletions stays about the identical—and the quantity of information added is roughly equal to that eliminated—linear-probing hash tables can function at excessive storage capacities with out sacrificing velocity.

In addition, the group has devised a brand new technique, referred to as “graveyard hashing,” which entails artificially rising the variety of tombstones positioned in an array till they occupy about half the free spots. These tombstones then reserve areas that can be utilized for future insertions.

This strategy, which runs opposite to what folks have usually been instructed to do, Kuszmaul says, “can lead to optimal performance in linear-probing hash tables.” Or, as he and his coauthors preserve of their paper, the “well-designed use of tombstones can completely change the … landscape of how linear probing behaves.”

Kuszmaul wrote up these findings with Bender and Kuszmaul in a paper posted earlier this 12 months that will likely be offered in February on the Foundations of Computer Science (FOCS) Symposium in Boulder, Colorado.

Kuszmaul’s Ph.D. thesis advisor, MIT pc science professor Charles E. Leiserson (who didn’t take part on this analysis), agrees with that evaluation. “These new and surprising results overturn one of the oldest conventional wisdoms about hash table behavior,” Leiserson says. “The lessons will reverberate for years among theoreticians and practitioners alike.”

As for translating their outcomes into apply, Kuszmaul notes, “there are many considerations that go into building a hash table. Although we’ve advanced the story considerably from a theoretical standpoint, we’re just starting to explore the experimental side of things.”