MENU

データ科学アルゴリズム設計・解析部門

データ科学アルゴリズム設計・解析分野

大規模データを迅速に処理・分析・活用するためのアルゴリズムとデータ構造の研究を行っています。

メンバー

研究内容

M&D分野データの処理のためのアルゴリズム設計・解析

M&D分野において生成される各種シーケンスデータ・センサデータ等の大規模データを迅速に処理・分析・活用するための手法を研究しています。主に文字列・系列データに対して、パターン照合・検索、特徴抽出・発見、データ圧縮・圧縮データ処理等、様々な処理を高速かつ省領域に行うアルゴリズムとデータ構造の設計やその性能解析を行っています。また、それらの手法の理論的基盤となる文字列組合せ論の研究も行っています。

最近の主な研究業績

2020

査読付き国際雑誌論文

  1. Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings, Theory of Computing Systems, 2020. https://doi.org/10.1007/s00224-020-09980-x
  2. Hideo Bannai, Travis Gagie, Tomohiro I, Refining the r-index, Theoretical Computer Science, 812:96-108, 2020. https://doi.org/10.1016/j.tcs.2019.08.005
  3. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic index and LZ factorization in compressed space. Discrete Applied Mathematics, 274: 116-129, 2020. https://doi.org/10.1016/j.dam.2019.01.014
  4. Jarno Alanko, Hideo Bannai, Bastien Cazaux, Pierre Peterlongo, Jens Stoye, Finding all maximal perfect haplotype blocks in linear time, Algorithms for Molecular Biology, 15:2, 2020. https://doi.org/10.1186/s13015-020-0163-6
  5. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida, Practical Grammar Compression Based on Maximal Repeats, Algorithms 2020, 13(4), 103, 2020. https://doi.org/10.3390/a13040103

査読付き国際会議論文

  1. Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster STR-EC-LCS Computation, In Proc. 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), LNCS 12011:125-135, 2020. https://doi.org/10.1007/978-3-030-38919-2_11
  2. Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Minimal Unique Substrings and Minimal Absent Words in a Sliding Window, In Proc. 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), LNCS 12011:148-160, 2020. https://doi.org/10.1007/978-3-030-38919-2_13
  3. Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, DAWGs for parameterized matching: online construction and related indexing structures, In Proc. 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), to appear in LIPIcs.
  4. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda and Ayumi Shinohara. Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences, In Proc. 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), to appear in LIPIcs.

2019

査読付き国際雑誌論文

  1. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, On the size of the smallest alphabet for Lyndon trees, Theoretical Computer Science, 792:131-143, 2019. https://doi.org/10.1016/j.tcs.2018.06.044

査読付き国際会議論文

  1. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An improved data structure for left-right maximal generic words problem, In Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), LIPIcs 149, 40:1-40:12, 2019. https://doi.org/10.4230/LIPIcs.ISAAC.2019.40
  2. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets, In Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811:382-391, 2019. https://doi.org/10.1007/978-3-030-32686-9_27
  3. Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomasz Kociumaka, On Longest Common Property Preserved Substring Queries, In Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811:162-174, 2019. https://doi.org/10.1007/978-3-030-32686-9_12
  4. Takuya Mieno, Dominik Koeppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compact Data Structures for Shortest Unique Substring Queries, In Proc/ 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811:107-123, 2019. https://doi.org/10.1007/978-3-030-32686-9_8
  5. Jarno Alanko, Hideo Bannai, Bastien Cazaux, Pierre Peterlongo, Jens Stoye, Finding all maximal perfect haplotype blocks in linear time, In Proc. 19th Workshop on Algorithms in Bioinformatics (WABI 2019), LIPIcs 143, 8:1-8:9, 2019. https://doi.org/10.4230/LIPIcs.WABI.2019.8
  6. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Maximal Palindromes and Distinct Palindromes in a Trie, In Proc. Prague Stringology Conference 2019 (PSC 2019), 3-15, 2019. http://www.stringology.org/event/2019/p02.html
  7. Golnaz Badkobeh, Hideo Bannai, Maxime Crochemore, Tomohiro I, Shunsuke Inenaga, Shiho Sugimoto, k-Abelian pattern matching: Revisited, corrected, and extended, In Proc. Prague Stringology Conference 2019 (PSC 2019), 29-40, 2019. http://www.stringology.org/event/2019/p04.html
  8. Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings, In Proc. 30th International Workshop on Combinatorial Algorithms (IWOCA 2019), LNCS 11638:430-441, 2019. https://doi.org/10.1007/978-3-030-25005-8_35
  9. Hideo Bannai, Juha Karkkainen, Dominik Koeppl, Marcin Piatkowski, Indexing the Bijective BWT, In Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), LIPIcs 128, 17:1-17:14, 2019. https://doi.org/10.4230/LIPIcs.CPM.2019.17
  10. Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Runs on a Trie, In Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), LIPIcs 128, 23:1-23:11, 2019. https://doi.org/10.4230/LIPIcs.CPM.2019.23
  11. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Queries for Longest Substring Palindrome After Block Edit, In Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), LIPIcs 128, 27:1-27:13, 2019. https://doi.org/10.4230/LIPIcs.CPM.2019.27
  12. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations, In Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), LIPIcs 128, 29:1-29:11, 2019. https://doi.org/10.4230/LIPIcs.CPM.2019.29
  13. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, The Parameterized Position Heap of a Trie, In Proc. 11th International Conference on Algorithms and Complexity (CIAC 2019), LNCS 11485: 237-248, 2019. https://doi.org/10.1007/978-3-030-17402-6_20
  14. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida, MR-RePair: Grammar Compression Based on Maximal Repeats. In Proc. Data Compression Conference (DCC 2019), 508-517, 2019. https://doi.org/10.1109/DCC.2019.00059

2018

査読付き国際雑誌論文

  1. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Karkkainen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, International Journal of Foundations of Computer Science. 29(2): 143-164, 2018. https://doi.org/10.1142/S0129054118400014
  2. Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Algorithms and combinatorial properties on shortest unique palindromic substrings, Journal of Discrete Algorithms 52-53: 122-132, 2018. https://doi.org/10.1016/j.jda.2018.11.009

査読付き国際会議論文

  1. Keisuke Goto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Block Palindromes: A New Generalization of Palindromes, In Proc. 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), LNCS 11147: 183-190, 2018. https://doi.org/10.1007/978-3-030-00479-8_15
  2. Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays, In Proc. 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), LNCS 11147: 254-267, 2018. https://doi.org/10.1007/978-3-030-00479-8_21
  3. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, O(n log n)-time Text Compression by LZ-style Longest First Substitution, In Proc. Prague Stringology Conference 2018 (PSC 2018), 12-26, 2018. http://www.stringology.org/event/2018/p03.html
  4. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai Masayuki Takeda, Right-to-left Online Construction of Parameterized Position Heaps, In Proc. Prague Stringology Conference 2018 (PSC 2018), 91-102, 2018. http://www.stringology.org/event/2018/p09.html
  5. Rui Henriques, Alexandre Francisco, Luis Russo, Hideo Bannai, Order-Preserving Pattern Matching Indeterminate Strings, In Proc. 29th Annual Symposium on Combinatorial Pattern matching (CPM 2018), LIPIcs 105, 2:1-2:15, 2018. https://doi.org/10.4230/LIPIcs.CPM.2018.2
  6. Hideo Bannai, Travis Gagie, and Tomohiro I, Online LZ77 Parsing and Matching Statistics with RLBWTs, In Proc. 29th Annual Symposium on Combinatorial Pattern matching (CPM 2018), LIPIcs 105, 7:1-7:12, 2018. https://doi.org/10.4230/LIPIcs.CPM.2018.7
  7. Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Online Elastic Degenerate String Matching, In Proc. 29th Annual Symposium on Combinatorial Pattern matching (CPM 2018), LIPIcs 105, 9:1-9:10, 2018. https://doi.org/10.4230/LIPIcs.CPM.2018.9
  8. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest substring palindrome after edit, In Proc. 29th Annual Symposium on Combinatorial Pattern matching (CPM 2018), LIPIcs 105, 12:1-12:14, 2018. https://doi.org/10.4230/LIPIcs.CPM.2018.12
  9. Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyro, Hideo Bannai, and Masayuki Takeda, Computing longest common square subsequences, In Proc. 29th Annual Symposium on Combinatorial Pattern matching (CPM 2018), LIPIcs 105, 15:1-15:13, 2018. https://doi.org/10.4230/LIPIcs.CPM.2018.15
  10. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest Lyndon Substring After Edit, In Proc. 29th Annual Symposium on Combinatorial Pattern matching (CPM 2018), LIPIcs 105, 19:1-19:10, 2018. https://doi.org/10.4230/LIPIcs.CPM.2018.19
  11. Isamu Furuya, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Lyndon Factorization of Grammar Compressed Texts Revisited, In Proc. 29th Annual Symposium on Combinatorial Pattern matching (CPM 2018), LIPIcs 105, 24:1-24:10, 2018. https://doi.org/10.4230/LIPIcs.CPM.2018.24