An Algorithm for a Better Bookshelf

Summary

Drop in at a library, and you’ll likely notice that most shelves aren’t full—librarians leave some empty space on each shelf. That way, when they get new books, they can slot them into place without having to move too many other books.It’s a simple-enough idea, but one that arises in a host of settings in computer science that involve sorted data, such as an alphabetically ordered census repository, or a list of connections between members of a social network. In such situations, where the entries can number in the hundreds of billions, the strategic positioning of empty spaces takes on great significance.“Problems are getting bigger and bigger as we get more and more data,” said Helen Xu, an assistant professor in the School of Computational Science and Engineering at the Georgia Institute of Technology (Georgia Tech) in Atlanta. “At these scales, it becomes important to efficiently manage how you add new entries.”The bookshelf problem (which computer scientists call the “list labeling” problem) is one of the most basic topics in the field of data structures. “It’s the kind of problem you’d teach to freshman or sophomore undergraduates,” said Guy Blelloch, a professor of computer science at Carnegie Mellon University in Pittsburgh.Yet until recently, there was a wide gap between what computer scientists could achieve algorithmically and what they knew about the theoretical lower limit on how many books you should expect to have to move when a new book arrives. On the algorithmic side, “There was pretty much no progress for 30 years or more,” Blelloch said.Now, researchers have come up with a new algorithm that comes close to that theoretical lower limit. Blelloch described it as “a very elegant result.”The new approach will “hopefully open the door to new applications of list labeling in settings where it wasn’t useful before because the cost was infeasible,” said William Kuszmaul, an assistant professor of computer science at Carnegie Mellon University and one of ...