Dynamic pattern matching: Faster Algorithms and New Bounds

该项目旨在提供必要的工具，以解决处理大量动态数据集所带来的挑战。也就是说，随着时间的推移，数据可能会非常迅速地发生变化。传统的想法已经找到了复杂的方法来索引和搜索非常大的静态信息集，而今天的许多应用，从高频金融到万维网的索引，都要求我们能够应对动态变化。模式匹配算法是现代数字世界的核心。从文字处理和网络搜索到计算遗传学和高级金融，高效准确地发现模式的能力对现代工业至关重要。然而，我们现在目睹了一个根本性的变化，不仅是在数据处理的方式上，而且在通常持有的数据集的绝对规模上。例如，公共基因组测序项目已经产生了数百gb的序列和相关元数据，网络搜索工具每天必须回答数十亿个查询，每个查询都在不到一秒的时间内。电信公司每天收集数兆字节的数据，这本身只是通过其网络传输的数据的一小部分。在线存储的海量数据类型也在不断增加，从音频到静态图像，从流媒体视频到整个图书馆馆藏。作为我们所面临的挑战的例子，在电信行业，不仅数据总量巨大，而且数据流的速度如此之快，以至于我们只能在任何时候存储输入的一小部分草图，但仍然必须尽快回答数据的复杂查询。在网络搜索中，以及新页面的到来，现有数据的任何部分都可能在不通知的情况下发生变化。在所有情况下，我们都必须能够以最小的成本快速、有效地处理这些变化。这个建议将允许我们开发快速算法来执行模式匹配在这些新的条件下。我们将考虑一系列场景，甚至考虑到多个同时发生的数据流，或者之前成功处理的数据可以在任何时间、任何地点被修改的情况。本项目的第二个和补充主题是显示我们所讨论的问题的时间和空间下界。在算法社区开发出更快、更高效的算法的地方，我们对可以实现的限制的理解，即使在原则上，目前也处于更基本的水平。这样的下界，如果它们是可用的，不仅对它们提供的重要理论兴趣和洞察力很重要，而且对于防止对不存在的算法进行无果搜索的实际目的也很重要。在一般的计算机科学中，下界在历史上被证明是很难发展的，但在流和动态计算的背景下，现在可以应用新的想法。这些结果将提供一个框架，未来的算法研究可以在其中进行，因此节省了许多小时的潜在无果的搜索方法，我们已经证明不存在。

This project aims to provide the tools necessary to address the challenges that arise from processing massive datasets which are themselves dynamic. That is to say the data changes, perhaps very rapidly, over time. Where traditional ideas have found sophisticated methods for indexing and searching very large sets of static information, much of today's applications, from high frequency finance to the indexing of the world wide web, requires us to be able to cope with dynamic change.Pattern matching algorithms are central to the modern digital world. From word processing and web search to computational genetics and high finance, the ability to find patterns efficiently and accurately is of fundamental importance to modern industry. However, we are now witnessing a fundamental change not only in the ways data are being processed but also in the sheer size of commonly held datasets. The public genome sequencing projects, for example, have produced hundreds of gigabytes of sequence and related meta data and web search tools must answer billions of queries a day, each within a fraction of a second. Telecommunication companies collect terabytes of data every day which is itself only a tiny proportion of the data that travels over their networks. The types of data that are being stored in massive volumes online are also increasing, from audio to still images, streaming video and entire library collections.As examples of the challenge we face, in telecommunications not only is the total data size massive, it streams at such a rate that we can only afford to store a small sketch of the input at any time and yet must still answer sophisticated queries of the data as quickly as possible. In web search, as well as the arrival of new pages, any part the existing data may change without notice. In all cases, we must be able handle such changes quickly, efficiently and with minimum cost. This proposal will allow us to develop fast algorithms to perform pattern matching under these new conditions. We will consider a range of scenarios, even taking into account multiple simultaneous streams of data or situations where previously successfully processed data can be modified at any point and at any time.The second and complementary topic for this project is that of showing time and space lower bounds for the problems we have discussed. Where ever faster and more efficient algorithms are developed by the algorithms community, our understanding of the limits of what can be achieved, even in principle, 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 purposes of preventing fruitless search for algorithms which cannot exist. Within computer science in general, lower bounds have historically proven hard to develop but in the context of streaming and dynamic computation new ideas can now be applied. These results will provide a framework within which future algorithmic research can be carried out, therefore saving many hours of potentially fruitless search for methods we have shown cannot exist.