Next generation pattern matching

该奖学金提案是一个基础研究计划，以发展下一代模式匹配算法所需的知识。其目的是在搜索、操作和处理大量数据集的理论和实践方面取得重大进展，这些数据集目前在高科技行业中很常见，并为更广泛的社区提供最先进的工具。该方案不仅将开发新的算法，而且将显示时间和空间下界。在算法社区开发出更快、更高效的算法的地方，我们对可以实现的极限的理解目前处于更基本的水平。这样的下界，如果它们是可用的，不仅对它们提供的重要理论兴趣和洞察力很重要，而且对于防止对不存在的算法进行无果搜索的实际目的也很重要。在一般的计算机科学中，下界在历史上被证明是很难发展的（例如考虑著名的P vs 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.