Seminars

NO.240 New Era of Data Structures: From Strings to Graphs, and more

Shonan Village Center

February 23 - 26, 2026 (Check-in: February 22, 2026 )

Organizers

  • Sankardeep Chakraborty
    • The University of Tokyo
  • Kunihiko Sadakane
    • The University of Tokyo
  • Srinivasa Rao Satti
    • Norwegian University of Science and Technology

Overview

Description of the Meeting

Data structures are essential to the design of algorithms and the retrieval of information. Given the explosion of data nowadays, the relevance of “compact” and “efficient” data structures has become extremely critical in the efficiency of numerous large-scale applications, such as internet routing, road mapping, cloud storage, similarity searches, data compression, and machine learning. Consequently, understanding the computational efficiency of these data structures — what they can and cannot achieve — is a fundamental issue in both the theoretical and practical domains. The seminar aims to bring together data structure researchers from various research directions to discuss several recent developments, investigate, and propose ambitious research directions for future exploration. In particular, the following research directions deserve further discussion:

●Data structure lower bounds

Despite approximately seven decades of successful research in data structures and algorithms, significant exponential gaps persist between the best-known upper and lower bounds for many fundamental data structure problems. These problems include dynamic reachability queries in graphs, pattern matching, and online matrix multiplication, among others. Recently, communication complexity and information theory have become powerful mathematical tools for analyzing time-space tradeoffs and establishing unconditional lower bounds on static and dynamic data structures. The aim of the seminar is to unite experts and enthusiasts to foster discussion and collaboration on some of the major unresolved issues in the field of data structure lower bounds.

●Graph compression

Graphs are among the most frequently utilized types of data. As the sizes of these graphs generated by various applications continue to grow, it becomes essential to design efficient data structures for storage and rapid querying. To achieve this, we explore three different approaches that have been recently investigated by various researchers.

(a) Much of the recent research focuses on succinct data structures for specific classes of graphs, leveraging their structural properties. These data structures can substitute the traditional (space-inefficient) adjacency lists/matrices in graph algorithms while still supporting efficient degree, adjacency, and neighborhood queries. Examples include succinct data structures for interval graphs, chordal graphs, and permutation graphs, among others.

(b) Another approach involves using grammar compression algorithms, such as the RePair algorithm, to compress adjacency lists of web graphs. This method, combined with data structures like k^2-trees, offers state-of-the-art compression for web and network graphs. Moreover, basic queries like in-neighbors and out-neighbors can be efficiently executed on these structures.

(c) Finally, a method involves assigning “small-sized” labels to the vertices of the graphs, enabling required queries to be supported solely by examining these labels, thus eliminating the need for storing any global data structures.
Still, there remains a wide range of important open problems and potential for future work in all these directions.

●From strings to graphs, automata, and others

Data compression algorithms were developed for strings first, and they were extended to trees and a class of graphs called Wheeler graphs. Recently they were further extended for compressing all automata and regular languages. We can classify these objects by a parameter “co-lex width”. In this meeting, we consider to further extend these concepts in various directions.

(a) We consider extensions of the co-lex width for wider classes of formal languages, graphs, and other objects. We also consider relationships with other parameters such as tree width, rank width, etc.

(b) We develop FPT (fixed parameter tractable) algorithms on graphs parameterized by the co-lex width. This enables us to understand the difficulties of problems.