Pattern matching algorithms for streaming data

想象一下，我给你以下任务：阅读莎士比亚全集，写下所有出现的短语我的好主。这个任务在计算机科学中被称为精确模式匹配;这里的短语my good lord就是模式。如果我让你找出所有与my good lord相似的短语，你可以决定写下my noble lord，my gracious lord和simply my lord。这就是近似模式匹配，当然，这个问题的复杂性取决于我们如何定义相似这个词。我们所考虑的定义取决于具体的应用，这个领域的广度和深度都来源于此。现在想象一下，我将给你读《莎士比亚全集》，并希望你在听到这些短语时写下类似的短语。这是在线近似模式匹配，是本提案的重点。该建议适用于与互联网相关的应用，其中大量数据不断通过计算机-称为数据流的领域。这里的数据太大，无法存储，结果必须在数据到达时进行计算。在阅读的类比中，如果你听错了一段话，我不会重读给你听，这个建议的目的是把这些领域结合在一起，在流数据中快速搜索模式。继续类比，我们将考虑在一些情况下找到模式：1。像以前一样，我会给你读一本书，但这次要快得多。我知道你不可能很快地把所有发生的事情都写下来，但我希望你能保证你能抓住大部分。很多人会同时大声地给你读这些书。任何时候他们中的任何一个说你正在寻找的模式，因为你必须把它写下来。我要给你读一本书，但我不能保证按顺序读：第6页第3行第6个字是好的，第39页第1行第2个字是快乐的，第6页第3行第5个字是我的。当然，这些问题听起来很奇怪，用简单的英语来说是违反直觉的，但潜在的计算机科学问题对于许多新兴应用来说非常重要，例如流量整形，防火墙，互联网监控和恶意内容检测。

Imagine that I give you the following task: read the Complete Works of Shakespeare and write down all occurrences of the phrase my good lord . The task is known in Computer Science as exact pattern matching; here the phrase my good lord is the pattern. If I asked you to find all phrases similar to the phrase my good lord , you may decide write down the phrases my noble lord , my gracious lord and simply my lord . This is approximate pattern matching, a problem whose complexity is, of course, dependent on how we define the word similar. The definition considered depends on the application and much of the breadth and depth of the field arises from this.Now imagine that I am going to read the Complete Works of Shakespeare to you and expect you to write down similar phrases as you hear them. This is online approximate pattern matching and is the focus of this proposal. The proposal is applicable to Internet related applications where a vast quantity of data passes though a computer constantly - a field known as data streaming. Here the data is far too large to be stored and results must be computed on the fly as the data arrives. In the reading analogy, if you mishear a paragraph, I'm not going to reread it to you.The aim of this proposal is to bring these fields together to search for patterns quickly in streaming data. Continuing the analogy, we will be considering finding patterns in a number of circumstances:1. As before I am going to read you a book but this time much faster. I know that you can't write down all the occurrences fast enough but I want you to guarantee you will catch most of them.2. Many people will read books out loud to you at the same time. Any time any of them say the pattern you are looking, for you have to write it down.3. I am going to read you a book but I make no promise to read the words in order: page 6 line 3 word 6 is good , page 39 line 1 word 2 is happy , page 6 line 3 word 5 is my ...Of course, these problems sound strange and counter-intuitive phrased in plain English, but the underlying Computer Science problems are highly significant for many emerging applications such as traffic shaping, firewalls, Internet monitoring and malicious content detection.