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, and an associate professor at Faculty of Information Science and Electrical Engineering, Kyushu University from 2003 to 2009. Since 2009, he has been an associate professor at National Institute of Informatics. His research interest includes information retrieval, data structures, and data compression. He is a member of IPSJ and IEICE.
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 Feb 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 is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v , the endpoints of the ed...
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 space requirement. The current trend in indexed text searching is that of compressed full-text self-indices, which replace the text with a more space-...
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 the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) o...
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]
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 asymptotically matches the information-theoretic lower bound. Importantly, many fundamental operations on trees can be done in constant time on the word RAM when...
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 Robinson–Foulds distance measures the number of clusters of descendant leaves not shared by N1 and N2. The fastest known algorithm for computing the Robinso...
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 order empirical entropy of T and ∈ > 0 is any fixed constant, such that (1) accessing T[i..i + logσ n-1] (one machine word) takes O(1) time and (2) repl...
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 structure whose size is n+o(n) bits. This representation enables constant time operations such as traversing from a internal node to its right child n...
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, performance of the proposed method is better than existing ones when searching frequent phrases. Experiments show that the proposed method is similar t...
