Labs researcher honoured with SIGMOD 2018 Best Paper award

[Curt_Hopkins]

Kimberly Keeton

By Curt Hopkins, Managing Editor, Hewlett Packard Labs

Labs distinguished technologist Kimberly Keeton, former Labs intern Huangchen Zhang, and their collaborators have won the Best Paper award at this year’s SIGMOD.

Their paper, “SuRF: Practical Range Query Filtering with Fast Succinct Tries,” presents the Succinct Range Filter (SuRF), a fast and compact filter data structure for approximate membership tests. Zhang will present the paper as part of the technical program at the conference this June in Houston.  

Filters are often used with low-level storage engines used in general-purpose databases. These storage engines, such as the log-structured merge tree, store data in multiple levels, some on slow storage devices. Retrievals from these engines may incur multiple time-intensive I/O operations. Avoiding those expenses calls for in-memory filtering data structures that can help locate query items without costly I/Os.

Bloom filters, “data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set,” are good example of these time-intensive operations. They’re small enough to reside in memory and have only “one-sided” errors and if the key is present, the Bloom filter returns true. But if the key is absent, the filter may experience a false positive. Although Bloom filters are useful for single-key lookups, such as “Is key 42 present?” they can’t handle range queries, Such as “Are there between 42 and 100 keys present?”

Unlike traditional Bloom filters, SuRF supports both single-key lookups and common range queries and are tunable for different applications.

“We enable range filtering through a succinct data structure that fits in memory, even though it summarizes a large amount of data,” says Keeton.

The paper also describes an implementation of SuRF in the popular, open-source RocksDB, evaluating SuRF as a replacement for RocksDB’s Bloom filters,

The paper forms part of Zhang’s dissertation at Carnegie Mellon University. (Keeton is on his dissertation committee.)

“While SuRF represents a significant improvement over traditional Bloom filters, it also highlights the power of collaboration between industry and academia”, says Cullen Bash. 

The paper’s coauthors include Hyeontaek Lim, David Andersen, and Andrew Pavlo of Carnegie Mellon University, Michael Kaminsky of Intel Research, and Viktor Leis of the Technical University of Munich.

This recognition is not Keeton’s first and is unlikely to be Zhang’s last.