Keisuke Goto

Dr. Keisuke Goto


Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
8 March 2022 in Theoretical Computer Science
Verified
Journal Article
Closed access
TKTakashi Katoh
Takashi Katoh
KGKeisuke Goto
Keisuke Goto

16 May 2015
Verified
Book Chapter
Closed access
PDF file
YTYuya Tamakoshi
Yuya Tamakoshi
KGKeisuke Goto
Keisuke Goto
Shunsuke InenagaShunsuke Inenaga
Shunsuke Inenaga
HBHideo Bannai
Hideo Bannai
MTMasayuki Takeda
Masayuki Takeda

6 February 2026 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
HBHideo Bannai
Hideo Bannai
KGKeisuke Goto
Keisuke Goto
MIMasakazu Ishihata
Masakazu Ishihata
SKShunsuke Kanda
Shunsuke Kanda
Dominik KöpplDominik Köppl
Dominik Köppl
BSBernardo Subercaseaux
Bernardo Subercaseaux
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation of some of these measures is NP-hard, and straight-forward computation is infeasible for datasets of even small sizes. Three such measures are the smallest size of a string attractor, the smallest size of a bidirectional macro scheme, and the smallest size of a straight-line program. While a vast variety of implementations for heuristically computing approximations exist, exact computation of these measures has received little to no attention. In this article, we present MAX-SAT formulations that provide the first non-trivial implementations for exact computation of smallest string attractors, smallest bidirectional macro schemes, and smallest straight-line programs. Computational experiments show that our implementations work for texts of length up to a few hundred for straight-line programs and bidirectional macro schemes, and texts even over a million for string attractors.

17 April 2020 in arXiv
Verified
Preprint
Open access
PDF file
HIHiroaki Iwashita
Hiroaki Iwashita
TTTakuya Takagi
Takuya Takagi
HSHirofumi Suzuki
Hirofumi Suzuki
KGKeisuke Goto
Keisuke Goto
KOKotaro Ohori
Kotaro Ohori
HAHiroki Arimura
Hiroki Arimura
Learning of interpretable classification models has been attracting much attention for the last few years. Discovery of succinct and contrasting patterns that can highlight the differences between the two classes is very important. Such patterns are useful for human experts, and can be used to construct powerful classifiers. In this paper, we consider mining of minimal emerging patterns from high-dimensional data sets under a variety of constraints in a supervised setting. We focus on an extension in which patterns can contain negative items that designate the absence of an item. In such a case, a database becomes highly dense, and it makes mining more challenging since popular pattern mining techniques such as fp-tree and occurrence deliver do not efficiently work. To cope with this difficulty, we present an efficient algorithm for mining minimal emerging patterns by combining two techniques: dynamic variable-ordering during pattern search for enhancing pruning effect, and the use of a pointer-based dynamic data structure, called dancing links, for efficiently maintaining occurrence lists. Experiments on benchmark data sets showed that our algorithm achieves significant speed-ups over emerging pattern mining approach based on LCM, a very fast depth-first frequent itemset miner using static variable-ordering.

25 December 2020 in Algorithms
Verified
Journal Article
Open access
PDF file
Dominik KöpplDominik Köppl
Dominik Köppl
TITomohiro I
Tomohiro I
IFIsamu Furuya
Isamu Furuya
YTYoshimasa Takabatake
Yoshimasa Takabatake
KSKensuke Sakai
Kensuke Sakai
KGKeisuke Goto
Keisuke Goto
Re-Pairis a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large-scale data sets. As a solution for this problem, we present, given a text of length n whose characters are drawn from an integer alphabet with size σ=nO(1), an O(min(n2,n2lglogτnlglglgn/logτn)) time algorithm computing Re-Pair with max((n/c)lgn,nlgτ)+O(lgn) bits of working space including the text space, where c≥1 is a fixed user-defined constant and τ is the sum of σ and the number of non-terminals. We give variants of our solution working in parallel or in the external memory model. Unfortunately, the algorithm seems not practical since a preliminary version already needs roughly one hour for computing Re-Pair on one megabyte of text.

13 July 2019 in arXiv
Verified
Preprint
Open access
PDF file
KGKeisuke Goto
Keisuke Goto
Suffix arrays and LCP arrays are one of the most fundamental data structures widely used for various kinds of string processing. We consider two problems for a read-only string of length $N$ over an integer alphabet $[1, \dots, \sigma]$ for $1 \leq \sigma \leq N$, the string contains $\sigma$ distinct characters, the construction of the suffix array, and a simultaneous construction of both the suffix array and LCP array. For the word RAM model, we propose algorithms to solve both of the problems in $O(N)$ time by using $O(1)$ extra words, which are optimal in time and space. Extra words means the required space except for the space of the input string and output suffix array and LCP array. Our contribution improves the previous most efficient algorithms, $O(N)$ time using $\sigma+O(1)$ extra words by [Nong, TOIS 2013] and $O(N \log N)$ time using $O(1)$ extra words by [Franceschini and Muthukrishnan, ICALP 2007], for constructing suffix arrays, and it improves the previous most efficient solution that runs in $O(N)$ time using $\sigma + O(1)$ extra words for constructing both suffix arrays and LCP arrays through a combination of [Nong, TOIS 2013] and [Manzini, SWAT 2004].