AF: DC: Collaborative Research: Pattern Matching for Massive Data Sets

AF：DC：协作研究：海量数据集的模式匹配

• 批准号: 1017623
• 负责人: Rahul Shah
• 金额: $ 50万
• 依托单位: Louisiana State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017623&HistoricalAwards=false
• 关键词: AF; DC; Collaborative; Research; Pattern

Pattern matching is a fundamental research field with applications in domains such as biological sequence alignment, web search engines and network intrusion detection. Given a pattern P and a text string T, the central problem is to find occurrences of P in T. When data becomes massive, we cannot assume that text can be stored in RAM. Pattern matching problems must now be considered with more appropriate models like external memory model, cache-oblivious model, streaming models, MapReduce paradigm and multi-core models. In many cases, a blend of models or newer, more appropriate models need to be developed keeping the practical aspects of the application in sight.The focus of this project is to develop efficient search algorithms and indexes when a data set resides on disks, on network storage, or is accessible only as an online stream. The data must be efficiently searchable even though it may be in compressed format. The project considers traditional pattern matching problem, as well as variants such as (i) approximate matching -- where the pattern may not exactly match a substring in T, (ii) online matching -- where the pattern(s) are known in advance and text comes as a stream, and (iii) string retrieval -- where instead of finding all the occurrences, the focus is on retrieving high ranking documents which contain one or more occurences of the query pattern. Issues of I/O efficiency and space utilization are central to this project. This involves developing suitable massive data set models, deriving optimal theoretical bounds and implementing practical tools. Methodologies include combinatorial and randomized methods in pattern matching, succinct data structures, top-k query processing and I/O efficient indexes.The project will build new, solid theoretical foundations in pattern matching, with direct applications to fields like databases and information retrieval. It will significantly drive forward current state of the art in web search engine technology (by impacting the way inverted indexes are used) and genome sequence alignment tools (e.g., BLAST). Tools and software developed during this project will be widely distributed to the research community. Some components will be incorporated into undergraduate and graduate algorithms course curricula as implementation projects.

模式匹配是生物序列比对、网络搜索引擎和网络入侵检测等领域的基础研究领域。 给定一个模式P和一个文本串T，中心问题是找到P在T中的出现。 当数据变得庞大时，我们不能假设文本可以存储在RAM中。 模式匹配问题现在必须考虑更合适的模型，如外部内存模型，缓存无关模型，流模型，MapReduce范式和多核模型。 在许多情况下，需要开发混合模型或更新，更合适的模型，以保持应用程序的实际方面。本项目的重点是开发高效的搜索算法和索引，当数据集驻留在磁盘上，网络存储上，或只能作为在线流访问时。 即使数据可能是压缩格式的，也必须能够有效地搜索。 该项目考虑了传统的模式匹配问题，以及变体，如（i）近似匹配-其中模式可能不完全匹配T中的子串，（ii）在线匹配-其中模式是预先已知的，文本作为流出现，以及（iii）字符串检索-其中不是找到所有出现的情况，重点在于检索包含查询模式的一个或多个占位符的高排名文档。 I/O效率和空间利用率问题是该项目的核心。 这涉及开发合适的海量数据集模型，推导最佳理论界限和实施实用工具。 方法论包括模式匹配中的组合和随机方法、简洁的数据结构、top-k查询处理和I/O高效索引。该项目将为模式匹配建立新的坚实的理论基础，并直接应用于数据库和信息检索等领域。 它将大大推动当前网络搜索引擎技术（通过影响倒排索引的使用方式）和基因组序列比对工具（例如，BLAST）。 该项目期间开发的工具和软件将广泛分发给研究界。 一些组件将被纳入本科和研究生算法课程作为实施项目。