文字列組合せ論に基づく大規模データ処理基盤技術
基于串组合学的大规模数据处理平台技术
基本信息
- 批准号：18J10967
- 负责人：
- 金额：$ 0.96万
- 依托单位：
- 依托单位国家：日本
- 项目类别：Grant-in-Aid for JSPS Fellows
- 财政年份：2018
- 资助国家：日本
- 起止时间：2018-04-25 至 2020-03-31
- 项目状态：已结题
- 来源：
- 关键词：
项目摘要
文字列の新たな組合せ的性質の究明および，それを用いたアルゴリズムの開発を目標に，文字列データ構造に着目して研究を行った．本研究では特に文字列パタン列挙のための索引構造の省領域化に取り組んだ．一つ目の成果は頻出部分文字列パタン列挙問題の変種のための索引構造の省領域化に成功した．頻出部分文字列パタン列挙問題とは，文書(文字列)の有限集合 D と正整数 d が与えられて， d 個以上の文書に生起する文字列をすべて列挙する問題である．本研究では，その変種として，クエリ文字列 p を部分文字列として含み，かつ，文字列の包含関係に関して極大な文字列のみを列挙する問題に取り組み，O(nlog|D|) 領域・O(|p| + o loglog|D|) クエリ応答時間の索引構造を開発した．ここで，n は D 中の文字列長の総和，o は解のサイズであり，この結果は，Nishimoto らの先行研究を，領域・クエリ応答時間ともに大幅に改善している．この内容はISSAC2019に採択され，発表済みである．またMFCS2016に採択されたDAWGの線形時間構築アルゴリズム及びSPIRE2019に採択されたtruncated DAWGの内容に関して，新たに得られた知見を加筆した論文をそれぞれ国際論文誌に投稿中である．
我们的研究重点是字符串数据结构，目的是研究字符串的新组合属性并开发使用它们的算法。在这项研究中，我们特别关注节省索引结构中用于枚举字符串模式的空间。第一个结果是针对频繁子串模式枚举问题的变体的节省空间的索引结构。枚举频繁子串模式问题是给定文档（字符串）的有限集 D 和正整数 d，枚举 d 个或更多文档中出现的所有字符串的问题。在本研究中，作为其变体，我们解决了仅枚举包含查询字符串 p 作为子字符串且在字符串包含关系方面最大的字符串的问题，并在 O(nlog|D| 中解决了该问题。 ) domain/O( |p| + o loglog|D|) 我们为查询响应时间开发了一个索引结构。这里，n是D中字符串的总长度，o是解决方案的大小。这个结果在面积和查询响应时间方面显着改善了Nishimoto等人之前的研究。该内容已在 ISSAC2019 上通过并公布。此外，我们目前正在向国际期刊提交论文，其中包括有关 MFCS2016 采用的 DAWG 线性时间构造算法和 SPIRE2019 采用的截断 DAWG 的新知识。
项目成果
期刊论文数量（5）
专著数量（0）
科研奖励数量（0）
会议论文数量（0）
专利数量（0）
Truncated DAWGs and their application to minimal absent word problem
截断的 DAWG 及其在最小缺席单词问题中的应用
- DOI：
- 发表时间：2018
- 期刊：
- 影响因子：0
- 作者：Yuta Fujishige;藤重雄大;藤重雄大;Yuta Fujishige
- 通讯作者：Yuta Fujishige
Improving an upper bound on suffix tree breadth
提高后缀树宽度的上限
- DOI：
- 发表时间：2019
- 期刊：
- 影响因子：0
- 作者：Yuta Fujishige;藤重雄大
- 通讯作者：藤重雄大
An improved data structure for left-right maximal generic words problem
左右最大通用词问题的改进数据结构
- DOI：
- 发表时间：2019
- 期刊：
- 影响因子：0
- 作者：Yuta Fujishige;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
- 通讯作者：Masayuki Takeda
{{
item.title }}
{{ item.translation_title }}
- DOI：
{{ item.doi }} - 发表时间：
{{ item.publish_year }} - 期刊：
- 影响因子：{{ item.factor }}
- 作者：
{{ item.authors }} - 通讯作者：
{{ item.author }}
数据更新时间：{{ journalArticles.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ monograph.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ sciAawards.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ patent.updateTime }}
藤重 雄大其他文献
藤重 雄大的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI：
{{ item.doi }} - 发表时间：
{{ item.publish_year }} - 期刊：
- 影响因子：{{ item.factor }}
- 作者：
{{ item.authors }} - 通讯作者：
{{ item.author }}
相似海外基金
広義文字列のアルゴリズムと組合せ論
宽字符串算法和组合数学
- 批准号：
22H03551 - 财政年份：2022
- 资助金额：
$ 0.96万 - 项目类别：
Grant-in-Aid for Scientific Research (B)
動的文字列処理に対するアルゴリズム技法の開発と計算限界の解明
动态字符串处理算法技术的开发和计算限制的阐明
- 批准号：
22K21273 - 财政年份：2022
- 资助金额：
$ 0.96万 - 项目类别：
Grant-in-Aid for Research Activity Start-up
文字列圧縮と組合せ論による大規模データ管理・処理技法の開発
使用字符串压缩和组合学开发大规模数据管理和处理技术
- 批准号：
18F18120 - 财政年份：2018
- 资助金额：
$ 0.96万 - 项目类别：
Grant-in-Aid for JSPS Fellows
Analysis of upper and lower bounds on string processing problems via advanced data structures
通过高级数据结构分析字符串处理问题的上限和下限
- 批准号：
17H01697 - 财政年份：2017
- 资助金额：
$ 0.96万 - 项目类别：
Grant-in-Aid for Scientific Research (B)
Research on Algorithms to Process Directed Acyclic Graph Based on Binary Decision Diagrams
基于二元决策图的有向无环图处理算法研究
- 批准号：
15H06101 - 财政年份：2015
- 资助金额：
$ 0.96万 - 项目类别：
Grant-in-Aid for Research Activity Start-up