The Graduate School of Information Science and Technology Department of Mathematical Informatics
Job title
Professor
Degree
Doctor of Science(The University of Tokyo)
Profile
Kunihiko SADAKANE received B.S., M.S., and Ph.D. degrees from Department of Information Science, University of Tokyo in 1995, 1997 and 2000, respectively. He was a research associate at Graduate School
of Information Sciences, Tohoku University from 2000 to 2003, an associate professor at Faculty of Information Science and Electrical Engineering, Kyushu University from 2003 to 2009, an associate professor at National Institute of Informatics from 2009 to 2014, and a professor at National Institute of Informatics at 2014. He has been a professor at the University of Tokyo from 2014. His research interest includes information retrieval, data structures, and data compression. He is a member of IPSJ and IEICE.
Theoretical Computer Science 532(1) 14-30 May 2014 [Refereed]
Recent advances in biotechnology and web technology are continuously generating huge collections of similar strings. People now face the problem of storing them compactly while supporting fast pattern searching. One compression scheme called relat...
IEEE/ACM Transactions on Computational Biology and Bioinformatics 9(6) 1629-1638 Nov 2012 [Refereed]
Structural alignment has been shown to be an effective computational method to identify structural noncoding RNA (ncRNA) candidates as ncRNAs are known to be conserved in secondary structures. However, the complexity of the structural alignment al...
Alexander Bowe, Taku Onodera, Kunihiko Sadakane, Tetsuo Shibuya
Proceedings of WABI 7534 225-235 Sep 2012 [Refereed]
We propose a new succinct de Bruijn graph representation. If the de Bruijn graph of k-mers in a DNA sequence of length N has m edges, it can be represented in 4m + o(m) bits. This is much smaller than existing ones. The numbers of outgoing and inc...
Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara, Gabriel Valiente
Information Sciences 197 77-90 Aug 2012 [Refereed]
The Robinson–Foulds distance, a widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two phylogenetic networks N1, N2 with n leaf labels and at most m nodes and e edges each, the Robins...
Proceedings of ICALP LNCS 7391 510-521 Jul 2012 [Refereed]
We present a new data structure called the Compressed Random Access Memory (CRAM) that can store a dynamic string T of characters, e.g., representing the memory of a computer, in compressed form while achieving asymptotically almost-optimal bounds...
Jurek Czyzowicz, Stefan Dobrev, Leszek Gąsieniec, David Ilcinkas, Jesper Jansson, Ralf Klasing, Ioannis Lignos, Russell Martin, Kunihiko Sadakane, Wing-Kin Sung
We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that ...
Journal of Computer and System Sciences 78(2) 619-631 Mar 2012 [Refereed]
There exist two well-known succinct representations of ordered trees: BP (balanced parenthesis) [Munro, Raman 2001] and DFUDS (depth first unary degree sequence) [Benoit et al. 2005]. Both have size 2n+o(n) bits for n-node trees, which asymptotica...
Diego Arroyuelo, Gonzalo Navarro, Kunihiko Sadakane
Algorithmica 62(1-2) 54-101 Feb 2012 [Refereed]
Given a text T[1..u] over an alphabet of size σ, the full-text search problem consists in finding the occ occurrences of a given pattern P[1..m] in T. In indexed text searching we build an index on T to improve the search time, yet increasing the ...
Ei Ando, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita
International Journal of Foundations of Computer Science (IJFCS) 21(3) 427-440 Jun 2010 [Refereed]
The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates t...
Jurek Czyzowicz, Stefan Dobrev, Leszek Gasieniec, David Ilcinkas, Jesper Jansson, Ralf Klasing, Ioannis Lignos, Russell A. Martin, Kunihiko Sadakane, Wing-Kin Sung
Structural Information and Communication Complexity, 16th International Colloquium, SIROCCO 2009 LNCS 5869 167-181 May 2009 [Refereed]
IEICE technical report. Theoretical foundations of Computing 111(256) 39-46 Oct 2011
This paper proposes a new dynamic data-structure for compressed random access memory. A memory (or string) T[1..n], where each character T[i] consists of logσ bits, can be stored in nH_k(T) + O [numerical formula] bits, where H_k(T) is the κ-th or...
To take large-scale data efficiently, succinct data structures that support highspeed operations on compressed data have been developed. In this paper, we focus on full binary trees which are used as patricia tries. We propose for a succinct data ...
String pattern matching for large-scale data is efficiently achieved by suffix array (SA), but SA requires a large space. Therefore, various methods to compress SA have been proposed. In this paper, we combine SA and Inverted index. As a result, p...
Second Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP 2011) Dec 2011
Trees are one of the most fundamental data structures. Many succinct representations of ordered and labeled trees and succinct indices for queries have been proposed. In this talk, I will discuss how these were extended and simplified. I will also...
Following
