Pattern matching algorithms for streaming data

流数据的模式匹配算法

• 批准号: EP/H028056/2
• 负责人: Benjamin Sach
• 金额: $ 5.46万
• 依托单位: University of Bristol
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2013
• 资助国家: 英国
• 起止时间: 2013 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FH028056%2F2
• 关键词: Pattern; matching; algorithms; streaming; data

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.

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