首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:Parameterized Matching in the Streaming Model
  • 本地全文:下载
  • 作者:Markus Jalsenius ; Benny Porat ; Benjamin Sach
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2013
  • 卷号:20
  • 页码:400-411
  • DOI:10.4230/LIPIcs.STACS.2013.400
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study the problem of parameterized matching in a stream where we want to output matches between a pattern of length m and the last m symbols of the stream before the next symbol arrives. Parameterized matching is a natural generalisation of exact matching where an arbitrary one-to-one relabelling of pattern symbols is allowed. We show how this problem can be solved in constant time per arriving stream symbol and sublinear, near optimal space with high probability. Our results are surprising and important: it has been shown that almost no streaming pattern matching problems can be solved (not even randomised) in less than Theta(m) space, with exact matching as the only known problem to have a sublinear, near optimal space solution. Here we demonstrate that a similar sublinear, near optimal space solution is achievable for an even more challenging problem.
  • 关键词:Pattern matching; streaming algorithms; randomized algorithms
国家哲学社会科学文献中心版权所有