文献

J-GLOBAL ID：202102217682657780   整理番号：21A0568673

範囲最短ユニークサブストリングクエリーのための効率的なデータ構造【JST・京大機械翻訳】

Efficient Data Structures for Range Shortest Unique Substring Queries

著者 (5件)： Abedin Paniz (Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA) ,  Ganguly Arnab (Department of Computer Science, University of Wisconsin - Whitewater, Whitewater, WI 53190, USA) ,  Pissis Solon P. (Life Sciences and Health, CWI, 1098 XG Amsterdam, The Netherlands) ,  Pissis Solon P. (Center for Integrative Bioinformatics, Vrije Universiteit, 1081 HV Amsterdam, The Netherlands) ,  Thankachan Sharma V. (Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA)
資料名： Algorithms (Web)  (Algorithms (Web))
巻： 13  号： 11  ページ： 276  発行年： 2020年 
JST資料番号： U7130A  ISSN： 1999-4893  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： スイス (CHE)  言語： 英語 (EN)

抄録/ポイント： T[1,n]は長さnのストリングであり,T[i,j]は位置iで始まり,位置jで終わるTのサブストリングである。TのサブストリングT[i,j]は,それがTで一度以上発生するならば,反復である。そうでなければ,それはTのユニークなサブストリングである。反復と独特のサブストリングは,計算生物学と情報検索において大きな関心事である。入力としてストリングTを与えられた場合,最短のユニークなサブストリング問題は,Tのどこでも生じないTの最短サブストリングを見つけることである。本論文では,この問題の範囲変化を導入し,ここでは,範囲最短の一意的サブストリング問題と呼ぶ。タスクは,オンラインクエリーの次のタイプを効率的に回答するT上のデータ構造を構築することである。範囲[,]を考えると,Tの最短サブストリングT[i,j]を,[,]で正確に1つの発生で戻した。w=Ω(logn)が単語サイズであるO(logwn)クエリ時間を有するO(nlogn)語データ構造を提示した。この構築は,最近導入された最適幾何学的データ構造[Chan et al.,ICALP 2018]の適用を可能にする自明でない削減に基づいている。さらに,O(nlogεn)クエリ時間を有するO(n)-単語データ構造を提示し,ここで,||0は任意に小さい定数である。後者のデータ構造は,他の幾何学的データ構造[NekrichとNavarro,SWAT2012]に大きく依存する。Copyright 2021 The Author(s) All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 情報検索 ,  *データ構造 ,  単語
準シソーラス用語： 計算生物学 ,  *クエリー ,  オンライン , 【Automatic Indexing@JST】

著者キーワード (5件)： 最短のユニークなサブストリング ,  サフィックスツリー ,  重光分解 ,  範囲質問 ,  幾何学的データ構造

分類 (3件)： 人工知能  (JE08000Z) ,  遺伝子の構造と化学  (EC02020U) ,  構造動力学  (HD02000E)

引用文献 (41件)：

• Lothaire, M. Applied Combinatorics on Words; Cambridge University Press: Cambridge, UK, 2005.
• Schleiermacher, C.; Ohlebusch, E.; Stoye, J.; Choudhuri, J.V.; Giegerich, R.; Kurtz, S. REPuter: The manifold applications of repeat analysis on a genomic scale. Nucleic Acids Res. 2001, 29, 4633-4642.
• Haubold, B.; Pierstorff, N.; Möller, F.; Wiehe, T. Genome comparison without alignment using shortest unique substrings. BMC Bioinform. 2005, 6, 123.
• Pei, J.; Wu, W.C.; Yeh, M. On shortest unique substring queries. In Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE 2013), Brisbane, Australia, 8-12 April 2013; pp. 937-948.
• Khmelev, D.V.; Teahan, W.J. A Repetition Based Measure for Verification of Text Collections and for Text Categorization. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, Toronto, ON, Canada, 28 July-1 August 2003; pp. 104-110.

タイトルに関連する用語 (1件)： データ構造