Next generation pattern matching

这项研究金提案是为了一个基础研究方案，以发展下一代模式匹配算法所需的知识。其目的是在搜索、操作和处理目前高科技行业中常见的海量数据集的理论和实践方面取得重大进展，并向更广泛的社区提供最先进的工具。这一提议不仅将开发新的算法，而且还将显示出时间和空间的下限。在算法社区开发出更快、更高效的算法时，我们对所能实现的极限的理解目前处于更基本的水平。这样的下限，如果有的话，不仅对于它们提供的重大理论兴趣和洞察力来说是重要的，而且对于防止对不存在的算法的徒劳搜索也是重要的。在一般的计算机科学中，下限在历史上被证明是很难开发的(例如，考虑著名的P与NP的问题)，但在流和动态计算的背景下，新的想法现在可以第一次被应用。为了给出一个真正完整的图景，我们还将提供新的和一些旧的想法的最新实现，以检验已经做出的假设，并发现需要整个社区解决的新问题。实现模式匹配算法，特别是那些被证明在理论上有效的算法，通常是一项具有挑战性的任务，需要相当多的算法和工程专业知识。为了确保开发的想法产生最大影响，我们将产生新开发的模式匹配算法以及其他实际性能尚不清楚的实现的免费、公开访问和最先进的实现。

This fellowship proposal is for a programme of fundamental research to develop the knowledge required for the next generation of pattern matching algorithms. The aim is to make significantadvances in both the theory and practice of searching, manipulating and processing massive datasets of the sorts that are now common in high technology industries and to make state of the art tools available to the wider community. This proposal will not only develop new algorithms but will also show time and space lower bounds. Where ever faster and more efficient algorithms are developed by the algorithms community, our understanding of the limits of what can be achieved is currently at a much more basic level. Such lower bounds, were they available, would not only be important for the significant theoretical interest and insight they provide, but also for the practical purpose of preventing fruitless search for algorithms which cannot exist. Within computer science in general, lower bounds have historically proven hard to develop (consider for example the famous question of P vs NP) but in the context of streaming and dynamic computation new ideas can now be applied for the first time.In order to give a truly complete picture, we will also provide state of the art implementations of both new and some old ideas to test assumptions that have been made and to discover new problems which need to be tackled by the whole community. Implementing pattern matching algorithms, especially those proven to be theoretically efficient, can often be a challenging task requiring both considerable algorithmic and engineering expertise. To ensure maximum impact for the ideas developed we will produce freely available, publicly accessible, state of the art implementations of the newly developed pattern matching algorithms as well as others whose practical performance is still unknown.