AF: III: Small: Space-efficient Frameworks for Multi-pattern Matching in Text Streams

多模式匹配是找出一组模式是否出现在数据流中以及出现在哪里的问题。此类问题的一个例子是扫描互联网流量中的恶意软件签名模式。多模式匹配中的重要注意事项是存储模式所需的内存量以及扫描数据流的速度。存储空间可以通过压缩图案或大致‘绘制’它们来减少。该项目旨在通过寻找能够以(1)最小可能空间、(2)尽可能快的时间和(3)高精度实现多模式搜索的方法来推动该领域的发展。该项目将理论进步与实际实施相结合。理论方法包括勾画、串流、散列和简洁的数据结构。实际目标包括开发更快的基于硬件的实现和支持缓存的实现。多模式匹配是计算机病毒检测、网络入侵检测和信息提取等应用的核心。它横跨计算机科学的几个领域，包括理论、网络、数据库和生物信息学。模式匹配工具的最新发展，如简洁的数据结构和流算法，使现在成为推动该领域最先进技术的令人兴奋的时刻。这个项目将为本科生提供几个研究机会。结果将通过会议和期刊上的出版物传播。

Multi-pattern matching is the problem of finding whether and where a set of patterns appear in a data stream. An example of such a problem is scanning Internet traffic for malware signature patterns. Important considerations in multi-pattern matching are the amount of memory required to store the patterns and the speed with which the stream can be scanned through. Storage space can be reduced either by compressing the patterns or by approximately 'sketching' them. This project aims to advance this field by seeking ways to enable multi-pattern search with (1) minimum possible space, (2) fastest possible time, and (3) high accuracy. The project combines theoretical advances with practical implementations. Theoretical approaches involve sketching, streaming, hashing and succinct data structures. Practical goals include developing faster hardware-based implementations and cache-aware implementations. Multi-pattern matching is central to applications such as computer virus detection, network intrusion detection and information extraction. It resides at the cross-section of several fields of computer science, including theory, networking, databases and bioinformatics. Recent development of tools in pattern matching such as succinct data structures and streaming algorithms make this an exciting time to advance the state-of-the-art in this field. Several research opportunities for undergraduate students will evolve from this project. Results will be disseminated through publications in conferences and journals.