論文

査読有り 本文へのリンクあり
2014年3月

Order-preserving matching

THEORETICAL COMPUTER SCIENCE
ダウンロード
回数 : 123
  • Jinil Kim
  • ,
  • Peter Eades
  • ,
  • Rudolf Fleischer
  • ,
  • Seok-Hee Hong
  • ,
  • Costas S. Iliopoulos
  • ,
  • Kunsoo Park
  • ,
  • Simon J. Puglisi
  • ,
  • Takeshi Tokuyama

525
開始ページ
68
終了ページ
79
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1016/j.tcs.2013.10.006
出版者・発行元
ELSEVIER SCIENCE BV

We introduce a new string matching problem called order-preserving matching on numeric strings, where a pattern matches a text if the text contains a substring of values whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching is closely related to the representation of order relations of a numeric string. We define the prefix representation and the nearest neighbor representation of the pattern, both of which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O(n logm) time algorithm and optimize it further to obtain O(n+m logm) time. For the multiple pattern case, we give an O(n logm) time algorithm. (C) 2013 Elsevier B.V. All rights reserved.

リンク情報
DOI
https://doi.org/10.1016/j.tcs.2013.10.006
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000334007300009&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.tcs.2013.10.006
  • ISSN : 0304-3975
  • eISSN : 1879-2294
  • Web of Science ID : WOS:000334007300009

エクスポート
BibTeX RIS