SPIRE 2019 採択情報(1)

SPIRE 2019 に採択されました。

文字列情報学研究室の三重野琢也さん (D1) の論文

"Compact Data Structures for Shortest Unique Substring Queries",
Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

が国際会議 SPIRE 2019 に採択されました。
この論文では、入力文字列中の Shortest Unique Substring (SUS) を見つける問題 (SUS問題) を高速に解く省領域なデータ構造を提案しました。提案データ構造と同等の時間で SUS 問題を解くことができる既存のデータ構造のサイズはいずれも O(n log n) ビット領域でしたが、本論文の提案データ構造はおよそ 2.6 n + o(n) ビットであり、大幅な省領域化を達成しています。

SPIRE 2019 は、10月7日~10月9日に、スペインのセゴビアにて開催されます。