Lab. 2: Sadakane

Personal Information

Kunihiko Sadakane
Kunihiko Sadakane

Department of Mathematical Informatics, Graduate School of Information Science and Technology

Professor

Room 341, Engineering Building 6, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656
Tel: 03-5841-6955 (ext. 26955)
Fax: 03-5841-6955

E-mail:sada@mist.i.u-tokyo.ac.jp

[Home Page]

Biography

March 1995 Bachelor Degree from Department of Information Science, Faculty of Science, The University of Tokyo
March 2000 Ph.D. from Department of Information Science, Graduate School of Science, The University of Tokyo
April 2000 Assistant Professor, Graduate School of Information Sciences, Tohoku University
April 2003 Associate Professor, Faculty of Information Science and Electrical Engineering, Kyushu University
April 2009 Associate Professor, National Institute of Informatics
March 2014 Professor, National Institute of Informatics
April 2014 Professor, Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo

Research Themes

・Algorithms and data structures for big data processing
・Theory and Applications of succinct data structures

Main paper and books

Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung: Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. SIAM J. Comput. 38(6): 2162-2178 (2009)
Kunihiko Sadakane: Compressed Suffix Trees with Full Functionality. Theory Comput. Syst. 41(4): 589-607 (2007)
Kunihiko Sadakane, Gonzalo Navarro: Fully-Functional Succinct Trees. SODA 2010: 134-149

Discrete Informatics Laboratory (Mathematical Informatics Lab. 2)

Discrete Informatics Laboratory (Mathematical Informatics Lab. 2) Home Page of Lab. 2→
Kunihiko Sadakane
Kunihiko Sadakane

Professor
Hiroshi Hirai
Hiroshi Hirai

Associate Professor
Yasushi Kawase
Yasushi Kawase

Project Associate Professor
Algorithms and Data Structures
We study algorithms and data structures for efficient processing of discrete data such as strings and graphs. We consider succinct data structures which can process compressed big data without decompression, indexing data structures for fast graph processing, etc. We also apply those theories to practical applications such as genome informatics and geographical information systems.
Discrete Optimization
We study optimization problems on discrete systems by making full use of discrete mathematics such as graph, network, and matroid. We also study related mathematical structures such as convexity, symmetry, sparsity, hierarchy, and metric, from algebraic and algorithmic point of view. We aim at developing practical and beautiful applied mathematics.
Compressed Discrete Structure Processing based on Graph Representations
Our research motivation is to develop techniques for solving NP-hard problems or processing big data in practical situations. Binary decision diagrams (BDDs) are ones of our favorite data structure that represent discrete structure compactly. We present algorithms to construct compact index or enumerate all solutions efficiently for large-scale data compressed by BDDs.