Anonymous Authentication Systems Based on Private Information Retrieval (2009)
Nakamura, Toru, Inenaga, Shunsuke, Ikeda, Daisuke, Baba, Kensuke, Yasuura, Hiroto, 中村, 徹, ...
Networked Digital Technologies (NDT 2009) : July 29-31, 2009 : Ostrava, The Czech Republic
Modeling Costs of Access Control with Various Key Management Systems (2009)
Yamasaki, Tomomi, Inenaga, Shunsuke, Ikeda, Daisuke, Yasuura, Hiroto, 山崎, 知美, 稲永, 俊介, ...
The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'09) : July 13-16, 2009 : Monte Carlo Resort, Las Vegas, Nevada, USA
Acyclic Word Graphs (DAWGs), and Compact Directed Acyclic Word Graphs (2009)
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. Trie is a tree structure to represent a set of strings. When the strings have many common prefixes, the number of nodes in the trie is much less than the total length of the strings. In...
マルチサービス環境における署名手法のリンク不能性に関する研究 (2009)
中村, 徹, 稲永, 俊介, 馬場, 謙介, 池田, 大輔, 安浦, 寛人, Nakamura, Toru, ...
2009年 暗号と情報セキュリティシンポジウム（SCIS2009） : 2009年1月20日(火)～ 1月23日(金) : 大津プリンスホテル
Composite Pattern Discovery for PCR Application (2008)
Stanislav Angelov, Shunsuke Inenaga
Abstract. We consider the problem of finding pairs of short patterns such that, in a given input sequence of length n, the distance between each pair’s patterns is at least α. The problem was...
An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars (2008)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
Abstract. There is a close relationship between formal language theory and data compression. Since 1990’s various types of grammar-based text compression algorithms have been introduced. Given an...
Practical Algorithms for Pattern Based Linear Regression (2008)
Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda
Abstract. We consider the problem of discovering the optimal pattern from a set of strings and associated numeric attribute values. The goodness of a pattern is measured by the correlation between...
Ternary Directed Acyclic Word Graphs (2008)
Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara
Abstract. Given a set S of strings, a DFA accepting S offers a very time-efficient solution to the pattern matching problem over S. Thekey is how to implement such a DFA in the trade-off between time...
Reachability on Suffix Tree Graphs (2008)
Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda
Abstract. We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links....
A New Family of String Classifiers Based on Local Relatedness (2008)
Yasuto Higa, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Abstract. This paper introduces a new family of string classifiers based on local relatedness. We use three types of local relatedness measurements, namely, longest common substrings (LCStr’s),...
A Provably Secure and Unlinkable Authentication System with Smart Cards (2008)
Nakamura, Toru, Inenaga, Shunsuke, Ikeda, Daisuke, Baba, Kensuke, Yasuura, Hiroto, 中村, 徹, ...
This paper proposes an identification scheme realizing an authentication system with smart cards. The proposed scheme satisfies the following properties simultaneously: security, unlinkability in...
プライバシ保護とメモリ効率性の両立を実現するマルチサービス環境向け認証方式 (2008)
中村, 徹, 稲永, 俊介, 馬場, 謙介, 池田, 大輔, 安浦, 寛人, Nakamura, Toru, ...
コンピュータセキュリティシンポジウム 2008 (Computer Security Symposium 2008, CSS 2008) : 2008年10月8日(水)～10日(金) : 沖縄コンベンションセンター
Inferring strings from graphs and arrays (2008)
Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
Abstract. This paper introduces a new problem of inferring strings from graphs, and inferring strings from arrays. Given a graph G or an array A, we infer a string that suits the graph, or the array,...
Efficient Computation of Substring Equivalence Classes with Suffix Arrays (2008)
Kazuyuki Narisawa, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Abstract. This paper considers enumeration of substring equivalence classes introduced by Blumer et al. [1]. They used the equivalence classes to define an index structure called compact directed...
Reachability on Suffix Tree Graphs (2008)
Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda
Abstract. We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links....
Practical Algorithms for Pattern Based Linear Regression (2008)
Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, Masayuki Takeda
Abstract. We consider the problem of discovering the optimal pattern from a set of strings and associated numeric attribute values. The goodness of a pattern is measured by the correlation between...
Nordic Journal of Computing BIDIRECTIONAL CONSTRUCTION OF SUFFIX TREES (2008)
Abstract. String matching is critical in information retrieval since in many cases information is stored and manipulated as strings. Constructing and utilizing a suitable data structure for a text...
Yasuto Higa, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
A new family of string classifiers
Simple Linear-Time Off-Line Text Compression by Longest-First Substitution (2008)
Ryosuke Nakamura, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda
We consider grammar based text compression with longest first substitution, where non-overlapping occurrences of a longest repeating substring of the input text are replaced by a new non-terminal...
A Framework for Evaluating Privacy Protection of Authentication Systems (2008)
Nakamura, Toru, Inenaga, Shunsuke, Ikeda, Daisuke, Baba, Kensuke, Yasuura, Hiroto, 中村, 徹, ...
SCIS 2008, The 2008 Symposium on Cryptography and Information Security : Jan. 22-25, 2008 : Miyazaki, Japan
Matsubara, Wataru, Inenaga, Shunsuke, Shinohara, Ayumi
In this paper we study the problem of deciding whether a given compressed string contains a square. A string x is called a square if x = zz and z = u^k implies k = 1 and u = z. A string w is said to...
Inferring strings from graphs and arrays (2007)
Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
Abstract. This paper introduces a new problem of inferring strings from graphs, and inferring strings from arrays. Given a graph G or an array A, we infer a string that suits the graph, or the array,...
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi
2 1
Acyclic Word Graphs (DAWGs), and Compact Directed Acyclic Word Graphs (2007)
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. Trie is a tree structure to represent a set of strings. When the strings have many common prefixes, the number of nodes in the trie is much less than the total length of the strings. In...
Acyclic Word Graphs (DAWGs), and Compact Directed Acyclic Word Graphs (2007)
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. Trie is a tree structure to represent a set of strings. When the strings have many common prefixes, the number of nodes in the trie is much less than the total length of the strings. In...
Nordic Journal of Computing (2007)
Bidirectional Construction Of, Shunsuke Inenaga
String matching is critical in information retrieval since in many cases information is stored and manipulated as strings. Constructing and utilizing a suitable data structure for a text string, we...
Shunsuke Inenaga, Masayuki Takeda
Abstract. Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text compression techniques of this type. Each compression scheme is...
プライバシ保護技術の評価のための権限認証モデル (2007)
中村, 徹, 稲永, 俊介, 馬場, 謙介, 池田, 大輔, 安浦, 寛人, Nakamura, Toru, ...
コンピュータセキュリティシンポジウム CSS2007 (Computer Security Symposium 2007) : 平成19年10月31日(水)～11月02日(金) : 奈良新公会堂, 奈良
M.: Sparse Directed Acyclic Word Graphs (2006)
Shunsuke Inenaga, Masayuki Takeda
Abstract. The suffix tree of string w is a text indexing structure that represents all suffixes of w. A sparse suffix tree of w represents only a subset of suffixes of w. An application to sparse...
On-line linear-time construction of word suffix trees (2006)
Shunsuke Inenaga, Masayuki Takeda
Abstract. Suffix trees are the key data structure for text string matching, and are used in wide application areas such as bioinformatics and data compression. Sparse suffix trees are kind of suffix...
M.: Sparse compact directed acyclic word graphs (2006)
Shunsuke Inenaga, Masayuki Takeda
Abstract. The suffix tree of string w represents all suffixes of w, and thus it supports full indexing of w for exact pattern matching. On the other hand, a sparse suffix tree of w represents only a...
M.: Sparse Directed Acyclic Word Graphs (2006)
Shunsuke Inenaga, Masayuki Takeda
Abstract. The suffix tree of string w is a text indexing structure that represents all suffixes of w. A sparse suffix tree of w represents only a subset of suffixes of w. An application to sparse...
M.: Sparse compact directed acyclic word graphs (2006)
Shunsuke Inenaga, Masayuki Takeda
Abstract. The suffix tree of string w represents all suffixes of w, and thus it supports full indexing of w for exact pattern matching. On the other hand, a sparse suffix tree of w represents only a...
On-line linear-time construction of word suffix trees (2006)
Shunsuke Inenaga, Masayuki Takeda
Abstract. Suffix trees are the key data structure for text string matching, and are used in wide application areas such as bioinformatics and data compression. Sparse suffix trees are kind of suffix...
Fully incremental LCS computation (2005)
Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
Abstract. Sequence comparison is a fundamental task in pattern matching. Its applications include file comparison, spelling correction, information retrieval, and computing (dis)similarities between...
Fully incremental LCS computation (2005)
Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
Abstract. Sequence comparison is a fundamental task in pattern matching. Its applications include file comparison, spelling correction, information retrieval, and computing (dis)similarities between...
S.: Finding optimal pairs of cooperative and competing patterns with bounded distance (2004)
Shunsuke Inenaga, Hideo Bannai, Heikki Hyyrö, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, ...
Abstract. We consider the problem of discovering the optimal pair of substring patterns with bounded distance α, from a given set S of strings. We study two kinds of pattern classes, one is in form...
S.: Finding optimal pairs of cooperative and competing patterns with bounded distance (2004)
Shunsuke Inenaga, Hideo Bannai, Heikki Hyyrö, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano
Abstract. We consider the problem of discovering the optimal pair of substring patterns with bounded distance α,fromagivensetS of strings. We study two kinds of pattern classes, one is in form p...
String Processing Algorithms (2003)
The thesis describes extensive studies on various algorithms for efficient string processing. Data available in/via computers are often of enormous size, and thus, it is significantly important and...
Linear-time off-line text compression by longest-first substitution (2003)
Shunsuke Inenaga, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara
Abstract. Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text compression techniques of this type. Each compression scheme is...
Linear-time off-line text compression by longest-first substitution (2003)
Shunsuke Inenaga, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara
Abstract. Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text compression techniques of this type. Each compression scheme is...
Discovering Most Classificatory Patterns for Very Expressive Pattern Classes (2003)
Masayuki Takeda, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Setsuo Arikawa
The classificatory power of a pattern is measured by how well it separates two given sets of strings. This paper gives practical algorithms to find the fixed/variable-length-don't-care pattern...
Discovering Most Classificatory Patterns for (2003)
Masayuki Takeda, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Setsuo Arikawa
The classificatory power of a pattern is measured by how well it separates two given sets of strings. This paper gives practical algorithms to find the fixed/variable-length-don't-care pattern...
Inferring Strings from Graphs and Arrays (2003)
Hideo Bannai Shunsuke, Shunsuke Inenaga, Ayumi Shinohara
This paper introduces a new problem of inferring strings from graphs, and inferring strings from arrays. Given a graph G or an array A, we infer a string that suits the graph, or the array, under...
String Processing Algorithms (2003)
The thesis describes extensive studies on various algorithms for efficient string processing. Data available in/via computers are often of enormous size, and thus, it is significantly important and...
Ternary Directed Acyclic Word Graphs (2003)
Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara
Given a set S of strings, a DFA accepting S o#ers a very time-e#cient solution to the pattern matching problem over S. The key is how to implement such a DFA in the trade-o# between time and space,...
A Note on Randomized Algorithm for String Matching with Mismatches (2002)
Baba, Kensuke, Shinohara, Ayumi, Takeda, Masayuki, Inenaga, Shunsuke, Arikawa, Setsuo, 馬場, 謙介, ...
Prague Stringology Conference '02 (PSC '02) : September 23-24, 2002 : Czech Technical University in Prague
Bidirectional construction of suffix trees (2002)
Abstract. String matching is critical in information retrieval since in many cases information is stored and manipulated as strings. Constructing and utilizing suitable data structures for text...
Compact directed acyclic word graphs for a sliding window (2002)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length...
Compact directed acyclic word graphs for a sliding window (2002)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. The suffix tree is a well-known and widely-studied data structure that is highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n...
The minimum dawg for all suffixes of a string and its applications (2002)
Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, Setsuo Arikawa
Abstract. For a string w over an alphabet Σ, we consider a composite data structure called the all-suffixes directed acyclic word graph (ASDAWG). ASDAWG(w) has |w | + 1 initial nodes, and the dag...
Compact directed acyclic word graphs for a sliding window (2002)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. The suffix tree is a well-known and widely-studied data structure that is highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n...
Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano
We present a new approach to pattern discovery called string pattern regression, where we are given a data set that consists of a string attribute and an objective numerical attribute. The problem is...
Finding Best Patterns Practically (2002)
Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Masahiro Hirao, Hiromasa Hoshino, Shunsuke Inenaga
Finding a pattern which separates two sets is a critical task in discovery. Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the...
Compact Directed Acyclic Word Graphs for a Sliding Window (2002)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
The suffix tree is a well-known and widely-studied data structure that is highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes...
Genome Informatics 13: 3--11 (2002) 3 A String Pattern Regression Algorithm and Its (2002)
Application To Pattern, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano
We present a new approach to pattern discovery called string pattern regression, where we are given a data set that consists of a string attribute and an objective numerical attribute. The problem is...
Bidirectional Construction of Suffix Trees (2002)
String matching is critical in information retrieval since in many cases information is stored and manipulated as strings. Constructing and utilizing suitable data structures for text strings, we can...
Discovering Best Variable-Length-Don't-Care Patterns Shunsuke (2002)
Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
A variable-length-don't-care pattern (VLDC pattern) is an element of set # = (# #{#}) # , where # is an alphabet and # is a wildcard matching any string in # # . Given two sets of strings, we...
Finding Best Patterns Practically (2002)
Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Masahiro Hirao, Hiromasa Hoshino, Shunsuke Inenaga
Finding a pattern which separates two sets is a critical task in discovery. Given two setsof strings, consider the problem to find a subsequence that is common to one set but never appears in the...
A Note on Randomized Algorithm for String Matching with Mismatches (2002)
Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, Setsuo Arikawa
Atallah et al. [ACD01] introduced a randomized algorithm for string matching with mismatches, which utilized fast Fourier transformation (FFT) to compute convolution. It estimates the score vector of...
Space-economical construction of index structures for all suffixes of a string (2002)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Hideo Bannai, Setsuo Arikawa
The minimum all-suffixes directed acyclic word graph (MAS-DAWG) of a string w has
S.: Discovering best variable-length-don’t-care patterns (2002)
Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. A variable-length-don’t-care pattern (VLDC pattern) is an element of set Π =(Σ ∪{⋆}) ∗ , where Σ is an alphabet and ⋆ is a wildcard matching any string in Σ ∗. Given two...
The Minimum DAWG for All Suffixes of a String and Its Applications (2002)
Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, Setsuo Arikawa
For a string w over an alphabet #, we consider a composite data structure called the all-suffixes directed acyclic word graph (ASDAWG). ASDAWG(w) has |w| + 1 initial nodes, and the dag induced by all...
Space-economical construction of index structures for all su#xes of a string (2002)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Hideo Bannai, Setsuo Arikawa
Abstract. The minimum all-suffixes directed acyclic word graph (MAS-DAWG) of a string w has |w | + 1 initial nodes, where the dag induced by all reachable nodes from the k-th initial node conforms...
S.: Discovering best variable-length-don’t-care patterns (2002)
Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. A variable-length-don’t-care pattern (VLDC pattern) isanelement of set Π =(Σ ∪{⋆}) ∗ , where Σ is an alphabet and ⋆ is a wildcard matching any string in Σ ∗. Given two sets...
A practical algorithm to find the best episode patterns (2001)
Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded. Given two sets of strings, consider an optimization...
A practical algorithm to find the best episode patterns (2001)
Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded. Given two sets of strings, consider an optimization...
On-line construction of symmetric compact directed acyclic word graphs (2001)
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
The Compact Directed Acyclic Word Graph (CDAWG) is a space efficient data structure that supports indices of a string. The Symmetric Directed Acyclic Word Graph (SCDAWG) for a string w is a dual...
On-line construction of compact directed acyclic word graphs (2001)
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa
Abstract. Directed Acyclic Word Graph (DAWG) is a space e#cient data structure that supports indices of a string. Compact Directed Acyclic Word Graph (CDAWG) is a more space e#cient variant of DAWG....
On-line construction of compact directed acyclic word graphs (2001)
Shunsuke Inenaga, Shunsuke Inenaga, Hiromasa Hoshino, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, ...
Directed Acyclic Word Graph (DAWG) is a space e#cient data structure that supports indices of a string. Compact Directed Acyclic Word Graph (CDAWG) is a more space e#cient variant of DAWG. Crochemore...
On-Line Construction of Compact Directed Acyclic Word Graphs (2001)
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, ...
A Compact Directed Acyclic Word Graph (CDAWG) is a space--e#cient text indexing structure, that can be used in several di#erent string algorithms, especially in the analysis of biological sequences.
Faster fully compressed pattern matching algorithm for balanced straight-line programs (2000)
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
Abstract. We study the fully compressed pattern matching problem (FCPM problem): Given T and P which are descriptions of text T and pattern P respectively, find the occurrences of P in T without...