Kunihiko Sadakane

Last updated: Oct 29, 2014 at 10:25
 
Avatar
Name
Kunihiko Sadakane
Affiliation
The University of Tokyo
Section
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.

What's new

 
 
11/25 12:43
 
11/17 16:55
 
11/11 17:06
 
11/03 17:36
 
10/28 11:53
 

Academic & Professional Experience

 
Apr 2014
 - 
Today
Professor, Graduate School of Information Science and Technology, The University of Tokyo
 

Published Papers

 
An Tex-time algorithm for detecting superbubbles
Wing-Kin Sung, Kunihiko Sadakane, Tetsuo Shibuya, Abha Belorkar, Iana Pyrogova
Proceedings of GIW/ISCB-Asia 2014      Dec 2014   [Refereed]
An Tex-time algorithm for detecting superbubbles
Wing-Kin Sung, Kunihiko Sadakane, Tetsuo Shibuya, Abha Belorkar, Iana Pyrogova
IEEE/ACM Transactions on Computational Biology and Bioinformatics      [Refereed]
Erik D. Demaine, Yamming Huang, Chung-Shou Liao, Kunihiko Sadakane
Proceedings of ICALP   LNCS(8572) 380-391   Jul 2014   [Refereed]
Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-Ichi Minato and Kunihiko Sadakane
Proceedings of SEA   LNCS(8504) 187-198   Jul 2014   [Refereed]
Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira, Kunihiko Sadakane
Algorithmica      Aug 2014   [Refereed]
A Novel Computational Model for GPUs with Application to I/O Optimal Sorting Algorithms
Atsushi Koike, Kunihiko Sadakane
Proceedings of APDCM      May 2014   [Refereed]
Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung
Algorithmica      Sep 2013   [Refereed]
Taku Onodera, Kunihiko Sadakane, Tetsuo Shibuya
Proceedings of WABI   LNCS 8126 338-348   Sep 2013   [Refereed]
Shirou Maruyama, Yasuo Tabei, Hiroshi Sakamoto, Kunihiko Sadakane
Proceedings of SPIRE   LNCS 8214 218-229   Sep 2013   [Refereed]
Wing-Kai Hon, Lap-Kei Lee, Kunihiko Sadakane, Konstantinos Tsakalidis
Proceedings of WADS   LNCS 8037 402-414   Aug 2013   [Refereed]
Huy Hoang Do, Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung
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...
Chuan Xiao, Jianbin Qin, Wei Wang, Yoshiharu Ishikawa, Koji Tsuda, Kunihiko Sadakane
Proceedings of the VLDB Endowment   6(6)    Jun 2013   [Refereed]
Hoa Vu, Francis Chin, W.K. Hon, Henry Leung, K. Sadakane, W.K. Sung, S.M. Yiu
Proceedings of ISBRA   LNCS 7875 112-124   May 2013   [Refereed]
Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira, Kunihiko Sadakane
Proceedings of STACS   LIPIcs(20) 281-292   Feb 2013   [Refereed]
Christopher Ma, King-Fung Wong, Tak-Wah Lam, Wing-Kai Hon, Kunihiko Sadakane, Siu-Ming Yiu
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   LNCS 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...
Gonzalo Navarro, Kunihiko Sadakane
ACM Transactions on Algorithms   10(3) Article No. 16   May 2014   [Refereed]
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...
Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung
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
Theoretical Computer Science   444(27) 60-76   Jul 2012   [Refereed]
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 ...

Misc

 
Abstract Computation Model for Analyzing Complexity of GPU-based Algorithms
Atsushi Koike, Kunihiko Sadakane
Proceedings of AAAC      Apr 2013   [Refereed]
A New Implementation of Succinct de Bruijn Graphs
Alexander Bowe, Taku Onodera, Kunihiko Sadakane, Tetsuo Shibuya
Proceedings of AAAC      Apr 2013   [Refereed]
Implementation of Succinct de Bruijn Graphs
Alexander Bowe, Taku Onodera, Kunihiko Sadakane, Tetsuo Shibuya
Proceedings of ALSIP      Nov 2012   [Refereed]
A Novel Computation Model for GPU
Atsushi Koike, Kunihiko Sadakane
Technical Committee on Theoretical Foundations of Computing (COMP)      Oct 2012
Compressing de Bruijn Graphs
Alexander Bowe, Taku Onodera, Kunihiko Sadakane, Tetsuo Shibuya
Technical Committee on Theoretical Foundations of Computing (COMP)      Sep 2012
SUNG Wing-Kin, SADAKANE Kunihiko, JANSSON Jesper
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...
Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi
9(1) 205-206   Aug 2010
Baba Masahiro, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi
9(1) 207-208   Aug 2010
TANAKA Yosuke, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi
The IEICE transactions on information and systems (Japanese edetion)   93(8) 1567-1575   Aug 2010
Masahiro Baba, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita
IPSJ SIG Notes   2010(1) 1-8   Feb 2010
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 ...
Yosuke Tanaka, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita
IPSJ SIG Notes   2010(1) 1-6   Jan 2010
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...
Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi
8(1) 43-50   Aug 2009

Books etc

 
Algorithms and Computation - 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings
Sudebkumar Prasant Pal, Kunihiko Sadakane (Eds.) (Part:Editor)
Feb 2014   ISBN:978-3-319-04657-0
http://link.springer.com/book/10.1007%2F978-3-319-04657-0

Conference Activities & Talks

 
Kunihiko Sadakane
Workshop on Algorithms in Bioinformatics (WABI)   11 Sep 2012   
Kunihiko Sadakane
Technical Committee on Theoretical Foundations of Computing (COMP)   3 Sep 2012   IEICE
Kunihiko Sadakane
Technical Committee on Theoretical Foundations of Computing (COMP)   Mar 2012   IEICE
Kunihiko Sadakane
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...
Kunihiko Sadakane
Technical Committee on Theoretical Foundations of Computing (COMP)   Oct 2011   IEICE
Online Prediction on Labeled Graphs
Koji Kobayashi, Kunihiko Sadakane
The 4th Annual Meeting of the AAAC   Apr 2011   
Fully-Functional Succinct Trees
Kunihiko Sadakane
ACM-SIAM Symposium on Discrete Algorithms (SODA)   Jan 2010