Yoshimasa Takabatake

Dr. Yoshimasa Takabatake

Kyushu Institute of Technology
orcid

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

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

Representative Publications

View All Publications
1 September 2018 in Journal of Discrete Algorithms
Verified
Journal Article
Open access
TOTatsuya Ohno
Tatsuya Ohno
KSKensuke Sakai
Kensuke Sakai
YTYoshimasa Takabatake
Yoshimasa Takabatake
TITomohiro I
Tomohiro I
HSHiroshi Sakamoto
Hiroshi Sakamoto

17 September 2020
Verified
Book Chapter
Closed access
PDF file
Travis GagieTravis Gagie
Travis Gagie
TITomohiro I
Tomohiro I
GMGiovanni Manzini
Giovanni Manzini
Gonzalo NavarroGonzalo Navarro
Gonzalo Navarro
Hiroshi SakamotoHiroshi Sakamoto
Hiroshi Sakamoto
YTYoshimasa Takabatake
Yoshimasa Takabatake

15 April 2016 in Algorithms
Verified
Journal Article
Open access
PDF file
YTYoshimasa Takabatake
Yoshimasa Takabatake
KNKenta Nakashima
Kenta Nakashima
TKTetsuji Kuboyama
Tetsuji Kuboyama
YTYasuo Tabei
Yasuo Tabei
Hiroshi SakamotoHiroshi Sakamoto
Hiroshi Sakamoto
Although several self-indexes for highly repetitive text collections exist, developing an index and search algorithm with editing operations remains a challenge. Edit distance with moves (EDM) is a string-to-string distance measure that includes substring moves in addition to ordinal editing operations to turn one string into another. Although the problem of computing EDM is intractable, it has a wide range of potential applications, especially in approximate string retrieval. Despite the importance of computing EDM, there has been no efficient method for indexing and searching large text collections based on the EDM measure. We propose the first algorithm, named string index for edit distance with moves (siEDM), for indexing and searching strings with EDM. The siEDM algorithm builds an index structure by leveraging the idea behind the edit sensitive parsing (ESP), an efficient algorithm enabling approximately computing EDM with guarantees of upper and lower bounds for the exact EDM. siEDM efficiently prunes the space for searching query strings by the proposed method, which enables fast query searches with the same guarantee as ESP. We experimentally tested the ability of siEDM to index and search strings on benchmark datasets, and we showed siEDM’s efficiency.

5 September 2015
Verified
Book Chapter
Closed access
PDF file
YTYoshimasa Takabatake
Yoshimasa Takabatake
YTYasuo Tabei
Yasuo Tabei
HSHiroshi Sakamoto
Hiroshi Sakamoto

4 July 2018
Verified
Book Chapter
Closed access
PDF file
TOTatsuya Ohno
Tatsuya Ohno
KGKeisuke Goto
Keisuke Goto
YTYoshimasa Takabatake
Yoshimasa Takabatake
TITomohiro I
Tomohiro I
Hiroshi SakamotoHiroshi Sakamoto
Hiroshi Sakamoto

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.