ICS Researchers Receive Best Paper Award at Algorithms and Data Structures Symposium

A conversation between two scholars that started at a conference in Italy — and continued on a connecting flight to Newark, New Jersey — sparked an idea that led to an award-winning paper. As Michael Goodrich, a Distinguished Professor of computer science at UC Irvine, chatted with Turing-Award winner Robert Tarjan, they came up with some preliminary ideas regarding a new type of binary search tree. Goodrich later shared the ideas with Ofek Gila, his Ph.D. student in the Donald Bren School of Information and Computer Sciences (ICS).

This started a collaboration between the trio that led to a new method for balancing binary search trees, which is outlined in the paper, “Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent.”

“It is nice that Ofek’s first paper was with a Turing-Award winner,” says Goodrich, “which is like a Nobel Prize in computer science.” Furthermore, the 2023 Algorithms and Data Structures Symposium (WADS 2023) is now recognizing their work with the symposium’s Best Paper Award.

Binary Search Trees
“Binary search trees are one of the most fundamental data structures in computer science,” explains Gila, who earned his B.S. in computer science and in physics from UCI in 2021. These search trees have many applications in the field, including for managing databases, prioritizing order packets in network routers, and managing memory. “The problem with binary search trees, however, is that how good they are is directly connected to how ‘balanced’ they are,” says Gila, “and by default, they can become very unbalanced, leading them to be impractical.”

To address this, researchers have invented various methods for balancing binary search trees, but each has its own trade-offs in terms of balance versus costs (in time, memory or expense). In 2018, Tarjan and his colleagues introduced the “zip trees” method of balancing binary search trees, which offers several advantages over previous methods. Zip trees are simple, require very little additional time and space, and have a property called “history independence” that is useful in cryptography.

Zip-zip Trees
However, zip trees do still have a few drawbacks, which Goodrich, Gila and Tarjan worked to address. “Our new paper introduces zip-zip trees, which essentially fixes the problems in zip trees while keeping all the benefits,” says Gila. Specifically, their new approach:

• makes the tree more balanced, so that all search and update operations run faster, just based on the use of a small number of random bits;
• offers persistence, letting users see what the search tree looked like in the past; and
• can be programmed to be “biased,” letting users prioritize certain values (which has applications in databases, when you want to make the most common queries run the fastest).

“This is the first publication I played an important role in,” says Gila, “and getting this award is certainly validating.”

— Shani Murray