Dominik Kempa Receives Stony Brook Trustees Faculty Award for Breakthroughs in Compressed Indexing

Packing an entire library into a few boxes would save space. But what if you needed to find one exact sentence without unpacking every box first? That challenge is at the heart of Dominik Kempa's research in compressed indexing, an area of theoretical computer science that asks how massive datasets can remain compact while still supporting efficient search, access, comparison and pattern matching.

Dominik Kempa, assistant professor of computer science

For his recent breakthroughs in data compression and theoretical computer science, Kempa, assistant professor in Stony Brook University's Department of Computer Science, has received the Stony Brook Trustees Faculty Award. The award recognizes promising early-career faculty and provides support to advance their research and scholarship.

"Receiving this award is very meaningful to me," Kempa said. "I see it not only as recognition of my work, but also of the broader area of theoretical computer science that this work belongs to."

Although Kempa's work is theoretical, it is motivated by concrete challenges in modern computing: how to store, search and process datasets that can reach petabytes and beyond. Genomic databases, collections of source code, web archives and versioned documents such as Wikipedia can contain enormous amounts of information - and enormous amounts of repetition.

Two human genomes, for example, are 99.9 percent the same on average. Different versions of a document may differ only by a few words. Large code repositories often contain repeated or slightly modified fragments. In each case, the amount of genuinely new information may be much smaller than the raw size of the data suggests.

Compression helps by avoiding the need to store the same information over and over again. But the goal is not to summarize the data or discard detail. In many cases, the small differences are the most important part.

"In genomics, a single mutation can be crucial for diagnosis or treatment; in source code, one changed character can break a system," Kempa said. "So the goal is not to 'summarize' the data or throw details away, but to compress it while preserving every bit exactly."

The difficulty is that compressed data is often harder to work with. A compressed file may take up less space, but if researchers must decompress an entire dataset every time they want to search, analyze or compare it, the benefits of compression can quickly disappear.

Kempa's research asks whether it is possible to have both: massive data kept in compressed form while still supporting powerful operations such as searching, indexing, comparing and accessing pieces of the original data efficiently.

In one recent line of work, Kempa and his collaborators tackled a central challenge in string processing: how to support powerful search and indexing operations without giving up the space savings of compression. Their 2023 paper, "Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space," which appeared at the 64th IEEE Symposium on Foundations of Computer Science, showed that suffix-array queries - a fundamental tool in string processing, data compression and bioinformatics - could be supported in essentially the same compressed space previously thought sufficient only for much simpler tasks.

A more recent paper, "Tight Lower Bounds for Central String Queries in Compressed Space," which appeared at the 2026 ACM-SIAM Symposium on Discrete Algorithms, helped complete the picture by identifying the optimal query-time limits for many central string queries in near-optimal compressed space.

Together, the results give researchers a clearer benchmark for what is possible - and what is inherently limited - when computing directly on compressed data.

Compressed indexing keeps highly repetitive data - such as genomes, source code and versioned documents - in compact form while still supporting efficient operations such as search, random access, comparison and pattern matching.

"The contribution of this line of work is not only a better compressed index," Kempa said, "but a much deeper understanding of the interplay between compression, indexing and efficient computation."

Kempa's work has involved students and collaborators at Stony Brook and beyond. At Stony Brook, he has worked with Rajat De, Eric Chiu and Ankith Reddy Adudodla. His external collaborators include Tomasz Kociumaka of the Max Planck Institute for Informatics and Ben Langmead of Johns Hopkins University.

"Stony Brook has been an excellent place to develop this research program," said Kempa. He credits the Department of Computer Science's supportive intellectual environment and opportunities for interaction across algorithms and data structures, as well as mentorship from computer science colleagues Michael Bender and Steven Skiena.

"Dominik's recent results have advanced our understanding of what is possible when computing directly on compressed data," said Samir Das, professor and chair of the Department of Computer Science. "His work combines deep theoretical insight with a problem of enormous practical importance, and this award is a very well-deserved recognition of his impact."

The research has also been supported by Kempa's NSF CAREER Award, "Scalable and Flexible Indexing of Compressed Sequences," and a Simons Foundation Junior Faculty Fellowship.

The Trustees Faculty Award will provide additional visibility and flexible support as Kempa continues to expand this research program.

Future directions include designing compressed indexes that are closer to practical use; extending the theory to dynamic data, where datasets change over time; exploring multidimensional compressed data such as images, maps and matrices; and continuing to identify the computational barriers that shape algorithms operating on compressed data.